分离轴算法
1) 英文名Separating Axis Theorem,简称SAT
2) 就是利用投影法将多边形所有点都投影到分离轴上,如果在分离轴上的投影不重叠,则两凸多边形不相交。
那将哪个轴作为分离轴呢?
多边形的每条边的法线都分别作为分离轴来计算一次,在所有分离轴上都测试通过,则两个多边形相交;否则不相交。
//两多边形是否相交 public static bool IsPolygonIntersect(Vector2[] polygon1, Vector2[] polygon2) { //多边形1的所有边的法向量作为分离轴 int edgeCount1 = polygon1.Length; for (int i = 0; i < edgeCount1; ++i) { var edge = polygon1[(i + 1) % edgeCount1] - polygon1[i]; var sepAxis = new Vector2(-edge.y, edge.x); //将边的法向量(左)作为分离轴 ProjOnSeparatingAxis(polygon1, sepAxis, out var minA, out var maxA); ProjOnSeparatingAxis(polygon2, sepAxis, out var minB, out var maxB); if (!IsProjIntersect(minA, maxA, minB, maxB)) return false; } //多边形2的所有边的法向量作为分离轴 int edgeCount2 = polygon2.Length; for (int i = 0; i < edgeCount2; ++i) { var edge = polygon2[(i + 1) % edgeCount2] - polygon2[i]; var sepAxis = new Vector2(-edge.y, edge.x); //将边的法向量(左)作为分离轴 ProjOnSeparatingAxis(polygon1, sepAxis, out var minA, out var maxA); ProjOnSeparatingAxis(polygon2, sepAxis, out var minB, out var maxB); if (!IsProjIntersect(minA, maxA, minB, maxB)) return false; } return true; } //多边形的所有点在分离轴上投影, 找出最小和最大投影距离 public static void ProjOnSeparatingAxis(Vector2[] polygon, Vector2 sepAxis, out float min, out float max) { min = float.MaxValue; max = float.MinValue; for (int i = 0; i < polygon.Length; ++i) { var vert = polygon[i]; float dot = Vector2.Dot(sepAxis, vert); min = Mathf.Min(min, dot); max = Mathf.Max(max, dot); } } //在分离轴的投影是否相交 public static bool IsProjIntersect(float minA, float maxA, float minB, float maxB) { if (minA < minB) return maxA > minB; return maxB > minA; }
参考
碰撞检测算法——分离轴算法在Unity中实现(二)-CSDN博客
Planning-碰撞检测之分离轴定理(SAT)-CSDN博客
2D凸多边形碰撞检测算法(一) - SAT - 知乎 (zhihu.com)