当前位置：首页 > article >正文

分离轴定理检测两个凸多边形是否相交

article 2025/1/15 13:03:54

1、什么是分离轴定理？

通过检查两个物体在所有可能的分离轴上的投影是否重叠，来判断它们是否相交。如果存在任何一个分离轴上的投影不重叠，那么两个物体一定不相交。否则，如果所有的分离轴上的投影都重叠，那么两个物体可能相交，需要进一步检查。

如上图，我们可以找到一条分离轴（不唯一），使得三角形的投影线段HI和四边形的投影线段JK不重叠，则两个多边形不相交。

2、怎么确定分离轴

对于每个物体的边界框，确定其边界框的边或面的法线向量。
对于每个法线向量，检查两个物体在该法线上的投影是否重叠。如果所有法线上的投影都重叠，那么两个物体一定相交。如果至少一条法线上的投影不重叠，那么两个物体一定不相交。

3、Unity代码实现

    /// <summary>
    /// 判断是否相交
    /// </summary>
    /// <param name="verShapeA">多边形A</param>
    /// <param name="verShapeB">多边形B</param>
    /// <returns></returns>
    private bool IsCross(List<Vector2Int> verShapeA,List<Vector2Int> verShapeB)
    {
        for (int i = 0; i < verShapeA.Count; i++)
        {
            Vector2Int a, b;
            a = verShapeA[i];
            if (i == verShapeA.Count - 1)
            {
                b = verShapeA[0];
            }
            else
            {
                b = verShapeA[i + 1];
            }

            //求边的单位法向量
            Vector2 normalVector = GetNormalVector(a, b);
            //求shapeA在向量上的最低点和最高点
            Vector2 minShapeAPos, maxShapeAPos=Vector2.zero;
            GetShapeProjectLength(verShapeA,normalVector,out minShapeAPos,out maxShapeAPos);
            //求shapeB在向量上的最低点和最高点
            Vector2 minShapeBPos,maxShapeBPos=Vector2.zero;
            GetShapeProjectLength(verShapeB,normalVector,out minShapeBPos,out maxShapeBPos);
            //检查两段投影是否有交集
            if (Mathf.Min(maxShapeAPos.y, maxShapeBPos.y) - Mathf.Max(minShapeAPos.y, minShapeBPos.y) > 0)
            {
                continue;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
    
    //求边的法向量
    private Vector2 GetNormalVector(Vector2Int pos1, Vector2Int pos2)
    {
        Vector2Int edgeVector = pos2 - pos1;
        return new Vector2(-edgeVector.y, edgeVector.x).normalized;
    }
    
    //求shape在法向量的投影最低点和最高点
    private void GetShapeProjectLength(List<Vector2Int> verShape,Vector2 normal,out Vector2 lowPos,out Vector2 highPos)
    {
        lowPos = new Vector2(0, float.MaxValue);
        highPos = new Vector2(0, float.MinValue);
        for (int i = 0; i < verShape.Count; i++)
        {
            float dotProduct = Vector2.Dot(verShape[i], normal);
            Vector2 projectionPoint = dotProduct*(Vector2)normal;
            if (projectionPoint.y < lowPos.y)
            {
                lowPos = projectionPoint;
            }

            if (projectionPoint.y > highPos.y)
            {
                highPos = projectionPoint;
            }
        }
    }