检测2种不同的多边形自相交情况（相交发生在内部或外部）

Question

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

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

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

假设在点 Q 处，段 (P_i, P_i+1) 和 (P_j, P_j+1) 之间存在交集，j>i。

案例 1：我将多边形分成 2 个多边形，[Q, P_i+1, ..., P_j , Q] 和 [Q, P_j+1, ..., P_i, Q]。

情况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

如果将复杂的多边形在交叉点处分割成简单的多边形；然后：

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

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

然而，还有更多你忽略的情况。例如，从第二个图（对于情况 2）开始，向上拖动 P3，使其位于从 P6 到 P1 的线上方（导致涉及 P3 的两条边的两侧都没有多边形）。再举一个例子，考虑一个有六个顶点的“数字 8”，其中中间有两条相同的边（可以通过删除两条中间边将其转换为简单的矩形）。

为了更有趣，请考虑这样的事情（但没有外圈）：

大多数情况下，让它在所有可能的情况下正常工作的机会为零；解决这个问题的唯一明智的解决方案是预防（找到一种方法来防止需要处理复杂的多边形）。