math - 如何检查两个旋转矩形之间的交集？

Question

有人可以解释如何检查一个旋转的矩形是否与其他矩形相交？

Answer 1

1. 对于两个多边形中的每条边，检查它是否可以用作分隔线。如果是这样，你就完成了:没有交集。
2. 如果未找到分隔线，则存在交叉点。

/// Checks if the two polygons are intersecting.
bool IsPolygonsIntersecting(Polygon a, Polygon b)
{
    foreach (var polygon in new[] { a, b })
    {
        for (int i1 = 0; i1 < polygon.Points.Count; i1++)
        {
            int i2 = (i1 + 1) % polygon.Points.Count;
            var p1 = polygon.Points[i1];
            var p2 = polygon.Points[i2];

            var normal = new Point(p2.Y - p1.Y, p1.X - p2.X);

            double? minA = null, maxA = null;
            foreach (var p in a.Points)
            {
                var projected = normal.X * p.X + normal.Y * p.Y;
                if (minA == null || projected < minA)
                    minA = projected;
                if (maxA == null || projected > maxA)
                    maxA = projected;
            }

            double? minB = null, maxB = null;
            foreach (var p in b.Points)
            {
                var projected = normal.X * p.X + normal.Y * p.Y;
                if (minB == null || projected < minB)
                    minB = projected;
                if (maxB == null || projected > maxB)
                    maxB = projected;
            }

            if (maxA < minB || maxB < minA)
                return false;
        }
    }
    return true;
}

有关更多信息，请参阅这篇文章:2D Polygon Collision Detection - Code Project

注意:该算法仅适用于按顺时针或逆时针顺序指定的凸多边形。