信息流广告代理商的盈利模式榜单优化

一、介绍

       分离轴算法（简称SAT）通常用于检查两个简单多边形（凸边形）之间或多边形与圆之间的碰撞。本质上，如果您能够绘制一条线来分隔两个多边形，则它们不会发生碰撞，如果找不到一条线来分割两个多边形，则它们发生碰撞。

如图：

 

 

        具体做法是遍历两个多边形的所有边，求得每条边的法向轴，再求出每个多边形在法向轴上的投影，求出投影的最大值点和最小值点，通过比较两个多边形的最值点的关系得出是否碰撞。

演示：

 

 

 

 

 

 

 

 运行代码：

获取在法向轴上投影的函数：

public void ProjectPolygon(Vector2 axis, Polygon polygon, ref float min, ref float max)
{//要在轴上投影一个点，使用点积float dotProduct = Vector2.Dot(axis, polygon.Points[0]);min = dotProduct;max = dotProduct;for (int i = 0; i < polygon.Points.Count; i++){dotProduct = Vector2.Dot(polygon.Points[i], axis);if (dotProduct < min){min = dotProduct;}else{if (dotProduct > max){max = dotProduct;}}}
}

 判断是否相交函数：、

  public float IntervalDistance(float minA, float maxA, float minB, float maxB){if (minA < minB){return minB - maxA;}else{return minA - maxB;}}

检测函数：

    public bool CollisionDetection(Polygon polygonA, Polygon polygonB){int edgeCountA = polygonA.Edges.Count;int edgeCountB = polygonB.Edges.Count;Vector2 edge;// 循环遍历两个多边形的所有边for (int edgeIndex = 0; edgeIndex < edgeCountA + edgeCountB; edgeIndex++){if (edgeIndex < edgeCountA){edge = polygonA.Edges[edgeIndex];}else{edge = polygonB.Edges[edgeIndex - edgeCountA];}//查找多边形当前是否相交// 找出垂直于当前边的轴Vector2 axis = new Vector2(-edge.y, edge.x);axis.Normalize();// 求多边形在当前轴上的投影float minA = 0; float minB = 0; float maxA = 0; float maxB = 0;ProjectPolygon(axis, polygonA, ref minA, ref maxA);ProjectPolygon(axis, polygonB, ref minB, ref maxB);// 检查多边形投影当前是否相交if (IntervalDistance(minA, maxA, minB, maxB) > 0)return false;}return true;}

结果演示：

参考链接：

https://code.tutsplus.com/collision-detection-using-the-separating-axis-theorem--gamedev-169t

How 2D Game Collision Works (Separating Axis Theorem) - YouTube

Collision Detection with SAT (Math for Game Developers) - YouTube