algorithm - 检测 2 种不同的多边形自相交情况(相交发生在内部或外部)

Question

我正在编写一种算法，将复杂的(自相交的)多边形拆分为一个或多个简单的多边形，以便它们可以用于我的碰撞检测算法。这可以通过添加/删除顶点和创建新的多边形来完成。

为此，我检测多边形中的所有线段交点并按较低的交点 x 对它们进行排序，然后按顺序处理每个线段交点。但是，可能会发生两种类型的交集，我需要根据发生的类型以不同方式拆分多边形。这是两种可能情况的说明:

我已经知道我应该如何处理每种交集类型，但我不知道如何检测给定的交集是否对应于情况 1 或情况 2。有没有办法确定这一点？我拥有我的算法所需的所有信息(顶点及其顺序、交点和导致它们的线段，...)。

假设线段(P_i, P_i+1)和(P_j, P_j+1)在Q点有交点，j>i。

案例 1: 我将多边形拆分为 2 个多边形，[Q, P_i+1, ..., P_j , Q] 和 [Q, P_j+1, ..., P_i,问].

情况 2: 我在多边形中插入一个顶点 V，得到的多边形为 [P1, ..., P_i, V, P_i+1, ..., P_j, Q, P_j+1, ..., P1]

所以我需要的缺失信息是弄清楚 [Q, P_i+1, ..., P_j] 形成的循环是“外部”循环(情况 1)还是“内部”循环(案例 2).

我已经阅读了有关由循环形成的多边形的有符号区域的内容，但并不完全理解。我不是在寻找最有效的算法，只是在寻找一种可行的算法。谢谢!

Answer 1

如果在交叉点将复杂的多边形拆分为简单的多边形；然后:

• 情况 1:简单多边形不重叠

• 情况 2:简单多边形重叠，其中一个简单多边形实际上是“反多边形”(描述要排除的内容而不描述要包含的内容)。

这种差异可以通过“一个多边形中的所有顶点都在另一个多边形内或接触另一个多边形”测试来确定。

请注意，对于情况 2，您可以将一个多边形插入到另一个多边形中，最终得到一个简单的多边形(例如，对于您的图表，您最终会得到“P1，交叉点，P3，P2，交叉点， P4、P5、P6”)。

但是，您还忽略了更多情况。例如，从您的第二个图表(对于案例 2)开始，向上拖动 P3 使其位于从 P6 到 P1 的直线上方(导致涉及 P3 的两条边的部分两侧没有多边形)。再举一个例子，考虑一个有六个顶点的“图 8”，中间有两条相同的边(可以通过删除两条中间边将其转换为一个简单的矩形)。

为了更有趣，考虑这样的事情(但没有外圈):

大多数情况下，让它在所有可能的情况下都正确工作的机会为零；唯一理智的解决方法是预防(找到一种方法来防止需要处理复杂的多边形)。