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

你可以使用 this collision algorithm :

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

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

第一句话很简单。因为多边形都是凸的,所以你可以画一条线,一个多边形在一边,另一个多边形在另一边,除非它们相交。第二个稍微不那么直观。请看图1。除非多边形的最近边彼此平行,否则它们彼此最接近的点是一个多边形的角最接近另一个多边形的边的点。这一边将在多边形之间形成一个分离轴。如果两侧平行,则它们都是分离轴。

那么,这具体如何帮助我们决定多边形A和B是否相交呢?好吧,我们只需检查每个多边形的每一面,看看它是否形成一个分离轴。为此,我们将使用一些基本的向量数学将两个多边形的所有点压缩到一条垂直于潜在分隔线的直线上(见图2)。现在整个问题很容易是一维的。我们可以确定每个多边形的点所在的区域,如果这些区域不重叠,那么这条线就是一个分离轴。

如果在检查了两个多边形的每一条线后,没有找到分离轴,则证明了多边形是相交的,必须对其进行一些处理。

• 如果多边形总是凸的,首先计算从多边形中心到中心绘制的线的角度。然后,您可以不必在与其他多边形成180度角的多边形的一半中测试边段。

• 要消除边,请从左侧的多边形开始。从与上一个项目符号的直线段垂直的多边形中心取直线段,并接触多边形的两侧。称此线段为P,顶点为p1和p2。然后,对于所有顶点,如果x坐标小于p1.x和p2.x,则顶点可以进入“安全桶”。

• 如果没有,你必须检查以确保它在线路的“安全”侧(也检查Y坐标)。

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

-反转极性,使第二个多边形“向右”。

您的测试用例应该可以工作,因为您要检查多边形完全不相交(完全在外部或完全在内部)的情况,以及存在任何形式的部分相交(如果存在重叠,则边缘总是相交)的情况。

对于测试,我只需要测试每个潜在的组合。上面我看到的缺失的是一个共享的边缘,但另一个包含一个多边形。我还将添加一些更复杂的多边形测试,从三边到多边,以防万一。

另外,如果你有一个U形的多边形,它完全包围了多边形,但没有重叠,我相信你的情况会处理这个问题,但我也会加上一个检查。

既然Altcongnito已经给了你一个解决方案,我只会指出 an excellent book on computational geometry 你可能会感兴趣。

GJK collision detection should work .

这里有一个想法:

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

• 找到每个多边形最靠近另一个多边形中心点的两点。它们将是凸多边形中的相邻点。这些定义了每个多边形的最近边,我们称之为点a、b和y、z

• 找到AB线和YZ线的交点。如果直线段相交(AB上的交点位于A和B之间),则多边形相交。如果ab和xy是平行的,忽略这个条件,下一步将捕获问题。

• 还有一种情况需要检查,那就是当多边形相交的程度足够大时,AB和xy完全相互交叉,实际上并不相交。 要捕捉这种情况,请计算AB和XY到每个多边形中心点的垂直距离。如果任意一个中心点靠近另一个多边形的直线段,则多边形会严重重叠。

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

1. Sweep line 基于算法。如前所述,可以执行扫描线过程,并保留多边形与扫描线相交所产生的间隔。如果在任何时候间隔重叠,则多边形相交。复杂性是O((R+B)日志(R+B))时间。
2. Rotating Callipers 基于算法。见 here 和 here 了解更多详细信息。复杂性是O(R+B)时间。
3. 可以找到最有效的方法 here 和 here . 这些算法需要O(log r+log b)时间。