如何判断两个凸多边形是否相交？
https://stackoverflow.com/questions/753140
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
假设一个平面（也许是一张地图）上有许多凸多边形。这些多边形可以相互碰撞并共享一条边，但不能重叠。
测试是否有两个多边形 磷 和 问 重叠，首先我可以测试每个边缘 磷 查看它是否与任何边相交 问. 。如果发现交叉点，我声明 磷 和 问 相交。如果没有相交，那么我必须测试以下情况 磷 完全包含于 问, ，反之亦然。接下来还有这样的情况 磷==问. 。最后，还有一种情况有一些共同点，但不是全部。（最后两种情况可能被认为是相同的一般情况，但这可能并不重要。）
我有一个算法可以检测两条线段相交的位置。如果这两个线段共线，则出于我的目的，它们不被视为相交。
我是否正确地列举了这些案例？对这些情况进行测试有什么建议吗？
请注意，我并不是要找到作为交点的新凸多边形，我只是想知道是否存在交点。有许多有据可查的算法来寻找交叉点，但我不需要付出所有的努力。
解决方案
你可以使用 这个碰撞算法:
为了能够确定两个凸多边形是否相交（彼此接触），我们可以使用分离轴定理。本质上：
- 如果两个凸多边形不相交，则存在一条线穿过它们之间。
- 仅当多边形之一的一侧形成这样的线时，才存在这样的线。
第一个陈述很简单。由于多边形都是凸的，因此您将能够绘制一条一侧有一个多边形、另一侧有另一个多边形的线，除非它们相交。第二个稍微不太直观。看图1。除非多边形的最近边彼此平行，否则它们彼此最接近的点是一个多边形的角最接近另一个多边形的边的点。然后，该边将形成多边形之间的分离轴。如果两条边平行，则它们都是分离轴。
那么这具体是如何帮助我们判断多边形A和B是否相交的呢？好吧，我们只需检查每个多边形的每一边并检查它是否形成分离轴。为此，我们将使用一些基本的向量数学将两个多边形的所有点压缩到一条垂直于潜在分隔线的线上（见图 2）。现在整个问题很方便地是一维的。我们可以确定每个多边形的点所在的区域，如果这些区域不重叠，则这条线是分离轴。
如果在检查两个多边形的每条线后没有找到分离轴，则已证明多边形相交并且必须对此采取措施。
其他提示
如果多边形总是凸的，首先计算从多边形中心到中心绘制的直线的角度。然后，您就无需测试与其他多边形成 180 度的半个多边形中的边线段。
要消除边缘，请从左侧的多边形开始。从多边形中心取与前一个项目符号的线段垂直的线段，并接触多边形的两侧。将此线段称为 p，其顶点为 p1 和 p2。然后，对于所有顶点，如果x坐标小于p1.x和p2.x，则该顶点可以进入“安全桶”。
如果没有，您必须检查以确保它位于线路的“安全”一侧（也只需检查 y 坐标）
-如果多边形中的线段的所有顶点都在“安全桶”中，则可以忽略它。
-反转极性，以便第二个多边形“向右”。
您的测试用例应该工作，因为你正在检查在多边形完全不相交（完全不在或完全内部）的情况下，以及在有任何形式的部分路口（边缘始终如果有相交是重叠）。
有关测试，我只想确保测试每一个可能的组合。在一个以上的从我看缺少的是共享的单一优势，但一个多包含在其他。我还要补充试验一些更复杂的聚的形状，从三 - >多方面的，只是作为预防措施
此外，如果你有一个U型聚完全包围了聚，但没有重叠，我相信你的情况会处理，但我想补充一点，作为检查，也是如此。
由于altCognito已经给你一个解决方案，我只指出一个很好的书计算几何您可能感兴趣。
这是一个想法：
找到每个多边形的中心点
找到每个多边形中最接近另一个多边形中心点的两个点。它们将是凸多边形中的相邻点。这些定义了每个多边形的最近边缘，我们将点称为 {A, B} 和 {Y, Z}
找到线 AB 和 YZ 的交点。如果线段交叉（AB 上的交点位于 A 和 B 之间），则多边形相交。如果AB和XY平行则忽略这个条件，下一步就会陷入这个问题。
您还需要检查另一种情况，即当多边形相交足够严重时，AB 和 XY 完全相互交叉并且实际上并不相交。要捕获这种情况，请计算 AB 和 XY 到每个多边形中心点的垂直距离。如果任一中心点更接近相对多边形的线段，则多边形会严重重叠。
