如何确定两个凸多边形是否相交？

Question

假设平面上有许多凸多边形,也许是地图.这些多边形可以相互碰撞并共享边缘,但不能重叠.

为了测试两个多边形P和Q是否重叠,首先我可以测试P中的每个边缘以查看它是否与Q中的任何边相交.如果找到了交叉点,我声明P和Q相交.如果没有相交,那么我必须测试P完全被Q包含的情况,反之亦然.接下来,有P == Q的情况.最后,情况是共享一些边缘,但不是全部.(最后两种情况可能被认为是相同的一般情况,但这可能并不重要.)

我有一个算法,可以检测两个线段相交的位置.如果这两个段是共线的,则不会认为它们与我的目的相交.

我是否正确列举了这些案例？有关这些案件的测试建议吗？

请注意,我不是要找到交叉的新凸多边形,我只想知道交叉是否存在.有许多记录良好的算法可以找到交集,但我不需要经过所有的努力.

Answer 1

您可以使用此碰撞算法:

为了能够确定两个凸多边形是否相交(相互接触),我们可以使用分离轴定理.实质上:

• 如果两个凸多边形不相交,则存在在它们之间穿过的线.
• 只有当一个多边形中的一个边形成这样的直线时,才存在这样的直线.

第一个陈述很容易.由于多边形都是凸的,因此除非它们相交,否则您将能够在一侧绘制一条多边形而另一侧绘制另一条多边形的线条.第二个稍微不那么直观.请看图1.除非多边形的最近边彼此平行,否则它们彼此最接近的点是一个多边形的一个角最接近另一个多边形的一侧的点.然后,该侧将在多边形之间形成分离轴.如果两侧是平行的,它们都是分离轴.

那么具体如何帮助我们决定多边形A和B是否相交？好吧,我们只是越过每个多边形的每一边,检查它是否形成一个分离轴.为此,我们将使用一些基本的矢量数学将两个多边形的所有点压缩到垂直于潜在分离线的直线上(见图2).现在整个问题很方便一维.我们可以确定每个多边形的点所在的区域,如果这些区域不重叠,则该线是分离轴.

如果在检查两个多边形的每条线之后没有找到分离轴,则已经证明多边形相交并且必须对其进行某些操作.

Answer 2

有多种方法可以检测凸多边形之间的相交和/或包含。这完全取决于您希望算法的效率如何。考虑两个分别具有 r 和 b 顶点的凸多边形 R 和 B：

1. 基于扫描线的算法。正如您所提到的，您可以执行扫描线过程并保留多边形与扫描线相交所产生的间隔。如果任何时候间隔重叠，则多边形相交。复杂度为 O((r + b) log (r + b)) 时间。
2. 基于旋转卡尺的算法。请参阅此处和此处了解更多详细信息。复杂度为 O(r + b) 时间。
3. 最有效的方法可以在这里和这里找到。这些算法需要 O(log r + log b) 时间。