假设在一个平面上有许多凸多边形，也许是一张地图。这些多边形可以相互碰撞并共享一条边，但不能重叠。
要测试两个多边形P和Q是否重叠，首先我可以测试P中的每条边，看看它是否与Q中的任何边相交。如果找到一个交点，我声明P和Q相交。如果没有相交，那么我必须测试P完全被Q包含的情况，反之亦然。接下来，存在P == Q的情况。最后，有些情况共享一些边缘，但不是全部。（这最后两种情况可能被认为是相同的一般情况，但这可能并不重要。）
我有一个算法可以检测两条线段相交的位置。如果这两个线段是共线的，则出于我的目的，它们不被视为相交。
我是否正确列举了这些案例？对这些案例的测试有什么建议吗？
请注意，我不是要找到作为交叉点的新凸多边形，我只想知道是否存在交叉点。有许多有据可查的算法可以找到交叉点，但我不需要付出所有努力。
您可以使用这种碰撞算法：
为了能够确定两个凸多边形是否相交（相互接触），我们可以使用分离轴定理。本质上：
- 如果两个凸多边形不相交，则存在一条穿过它们的线。
- 仅当多边形之一的边之一形成这样的线时，才存在这样的线。
第一个陈述很简单。由于多边形都是凸面的，因此您可以绘制一条线，其中一个多边形在一侧，另一个多边形在另一侧，除非它们相交。第二个不太直观。看图 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 到每个多边形中心点的垂直距离。如果任一中心点更靠近对面多边形的线段，则您的多边形重叠严重。
