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

Question

假设在平面上（可能是地图）存在一些凸多边形。这些多边形可以相互挤压并共享一条边，但不能重叠。

为了测试两个多边形P和Q是否重叠，首先我可以测试P中的每条边是否与Q中的任何一条边相交。如果找到交点，则宣布P和Q相交。如果没有相交，那么我就必须测试P完全包含在Q中的情况，以及反之亦然。接下来，还有P == Q的情况。最后，还有共享几条边但不是所有边的情况。（这最后两种情况可能可以视为同一种一般情况，但这可能并不重要。）

我有一个检测两条线段相交的算法。如果这两个线段共线，则对于我的目的，它们不被视为相交。

我正确列出了这些情况吗？有关于如何测试这些情况的建议吗？

请注意，我不想找到新的凸多边形即交集，我只想知道是否存在交集。有很多文档良好的算法可用于查找交集，但我不需要进行所有的努力。

- Scottie T

---

当决定非垂直、非水平线段共线性时，要注意浮点精度问题，如果你选择这样做的话。 - Matt J

请查看来自math.stackexchange的这个答案，它解释了该算法，还在这里有相关引用。 - undefined

Answer 1

你可以使用这个碰撞算法：

为了判断两个凸多边形是否相交（彼此接触），我们可以使用分离轴定理。基本上有以下几点：

• 如果两个凸多边形不相交，则存在一条通过它们之间的线。
• 只有当其中一个多边形的一条边形成这样的线时，才存在这样的线。

第一条很容易理解。由于多边形都是凸的，你可以画一条线，将一个多边形放在一侧，另一个多边形放在另一侧，除非它们相交。第二条略微不太直观。看一下图1。除非多边形最近的边是平行的，否则它们彼此最接近的点是一个多边形的一个角和另一个多边形的一条边最接近的地方。然后，这条边将形成多边形之间的分离轴。如果这些边是平行的，那么它们都是分离轴。 那么，这如何帮助我们具体决定多边形A和B是否相交呢？我们只需检查每个多边形的每条边是否形成分离轴即可。为此，我们将使用一些基本的向量数学，将两个多边形的所有点压缩到与潜在分离线垂直的线上（参见图2）。现在整个问题方便地变成了一维。我们可以确定每个多边形点所在的区域，如果这些区域不重叠，则该线是一个分离轴。 如果在检查来自两个多边形的每条线之后没有找到分离轴，则已经证明多边形相交，需要采取措施。

- MaxVT

---

很不幸，你在回答中引用的网站现已关闭；你可能需要更改链接或从回答中删除它。 - SteJ

幸运的是，这个页面已经被 Wayback Machine 保存了。如果这个答案对您有帮助，请捐赠给互联网档案馆。 - MaxVT

在检查边缘E是否形成分离线时，垂线/投影部分可以用向量积（在2维中为行列式）计算来替代，这样更容易。我的意见是：多边形A的所有顶点都位于E的同一侧（即行列式的相同符号），而多边形B的所有顶点都位于E的另一侧（即行列式的相反符号）。 - ghilesZ

“除非多边形的最近侧面是平行的，否则它们最接近的点是一个多边形的角落与另一个多边形的一条边相接触”——这是不正确的。在A和B中最接近彼此的一对点可能是两个角点。 - HelloGoodbye

如果你有两个四边形，甚至不需要先找到凸包，只需检查每条边，看剩余的四边形点是否在该线的一侧，而另一个四边形的所有点是否在该线的另一侧。 - Waruyama

Answer 2

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

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

- Carlos Alegría

Answer 3

• 如果多边形总是凸的，首先计算从多边形中心到另一个多边形中心的线段的角度。这样你就可以消除需要测试在另一半180度之外的边缘段的多边形的需求。

• 为了消除边缘，从左侧开始处理多边形。取从多边形中心垂直于上一个步骤中的线段并触及多边形两侧的线段，称此线段为p，其顶点为p1和p2。然后，对于所有顶点，如果x坐标小于p1.x和p2.x，则该顶点可以放入“安全桶”中。

• 如果不是，则必须检查以确保它位于线段的“安全”一侧（也只需检查y坐标）

-如果多边形中的线段所有顶点都在“安全桶”中，则可以忽略它。

-反转极性，以使第二个多边形为“正确方向”。

- Zak

---

1. 我如何通过编程消除这些边缘？
2. 那是上面所示的第三种情况。

- Scottie T

你的边缘消除方法似乎在重叠量非常高的情况下可能无法正常工作。 - Scottie T

Answer 4

GJK 碰撞检测算法 应该 有效。

- Matt J

---

它提供了比你需要的更多信息（两个N维凸多面体之间的最小距离，而不仅仅是该距离是否为0（碰撞）），但这样做并没有显著的性能开销。MollyRocket链接中有一个很好的直观解释。 - Matt J

这个回答提供了很好的信息，但你应该将每个链接拆分成单独的句子，或者至少使用项目符号列表。 - Noah May

Answer 5

既然altCognito已经给出了解决方案，那我只想提醒你一下计算几何领域一本很棒的书，也许这会引起你的兴趣。

- avakar

---

谢谢，我在搜索中遇到了这个，我正在考虑购买它。我已经从另一个程序员那里借了另一本计算几何书。 - Scottie T

Answer 6

你的测试用例应该是有效的，因为你检查了多边形完全不相交的情况（完全在外面或完全在里面），以及任何形式的部分相交（如果有重叠，则边缘总是相交）。

对于测试，我会确保测试每个潜在的组合。从我看到的内容中缺少的一个是共享单个边缘，但其中一个多边形包含在另一个多边形中。我还会添加一些更复杂的多边形形状的测试，从三边形到多边形，只是作为预防措施。

此外，如果你有一个U形多边形完全包围多边形，但没有重叠，我相信你的情况会处理它，但我也会将其作为检查添加进来。

- Reed Copsey

---

谢谢。我确实需要使用复杂的形状进行测试，而不是我在这里绘制的矩形。它们只是更容易绘制。但我的所有多边形都是凸的，所以我没有任何U形状。 - Scottie T

你的算法应该可以正常工作。MaxVT提到的算法可能更快，但是你的算法也应该能够正常工作。它也应该同样轻松地处理非凸多边形。 - Reed Copsey

是的，我也喜欢这个算法。我正在测试非常小的形状（四边形和三角形），因此只需测试每条边是否可以成为分离轴即可。可能更快。 - John Henckel

Answer 7

这里有一个想法：

• 找到每个多边形的中心点

• 找到每个多边形最靠近另一个多边形中心点的两个点。它们将是凸多边形中相邻的点。这些定义了每个多边形的最近边缘，我们称之为点 {A, B} 和 {Y, Z}

• 找到线段 AB 和 YZ 的交点。如果线段相交（AB 上的交点位于 A 和 B 之间），则您的多边形相交。如果 AB 和 XY 平行，则忽略此条件，下一步将捕获问题。

• 还有一种情况需要检查，即当多边形相交得足够严重时，AB 和 XY 完全超过彼此并且实际上不相交。 为了捕获这种情况，请计算 AB 和 XY 到每个多边形中心点的垂直距离。如果任何一个中心点更靠近相反多边形的线段，则您的多边形重叠严重。

- JP772

---

我对这个答案进行了负评，因为第二个要点是不正确的，根据以下使用两个凸四边形的具体示例：Quad＃1：{-50, 3} {0, 4} {50, 3} {0, 2}; Quad＃2：{-1, -1} {-1, 1} {1, 1} {1, -1}。Quad＃2的中心是原点，最近的两个点分别是{0, 2}和{0, 4}，它们在Quad＃1中不是相邻的点。 - Jeff G