检测多边形自相交的两种情况（内部或外部发生的交叉）。

Question

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

为此，我检测多边形中的所有线段交点，并按较低交点x排序，然后按顺序处理每个线段交点。但是，可能会发生两种类型的交点，我需要根据发生的交点类型不同而以不同的方式分割多边形。下面是两种可能情况的示例：

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

假设线段（P_i，P_i + 1）和（P_j，P_j + 1）在点Q处相交，其中j> i。

情况1：将多边形分成两个多边形，[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）。

我已经阅读了关于由循环形成的多边形的有符号面积的内容，但并不完全理解。我不是在寻找最有效的算法，只是需要一个可行的算法。谢谢！

- user1354784

Answer 1

如果你在交点处将复杂的多边形分割成简单的多边形，那么：

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

• 情况2：简单的多边形重叠，并且其中一个简单的多边形实际上是一个“反向多边形”（描述要排除什么而不是要包括什么）。

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

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

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

对于更有趣的东西，请考虑这样的东西（但没有外圆）：

大多数情况下，使其能够正确处理所有可能的情况的机会为零；解决这个问题的唯一明智的方法是预防措施（找到一种避免处理复杂多边形的方法）。

- Brendan

Answer 2

首先构建多边形的 平面直线图 (PSLG)。换句话说，将多边形视为一堆线段，在每个交点处分割线段。存在一个特殊情况，即两个或多个线段可以在一个非平凡的线段中重叠，而不是在一个点上。在 PSLG 中，交点线段应该是单独的分离线段，但我们还需要知道有多少条线段与它重叠。因此，这是一个退化的多边形 (A-B-C-D-E-F-G-A)

A-C-B-D
|    /
|   /
G--E---F

转化成

   3
*-*-*-*
|    /
|   /
*--*---* ,
     2

省略所有标签上的1。

接下来的步骤是计算此PSLG的组合嵌入。这意味着我们遍历顶点，按逆时针顺序按角度对每个顶点的入射边进行排序。在标准计算几何中，我们可以使用有符号面积得到一个比较器，它不涉及三角函数。

现在，我们有了以下数据结构。

   3
t-u-v-w
|    /
|   /
x--y---z ,
     2

t: t-u, t-x, t-y
u: u-v (3), u-t
v: v-w, v-u (3)
w: w-v, w-y
x: x-y, x-t
y: y-z (2), y-w, y-x
z: z-y (2)

我们得到一个定向边（以下简称箭头）的排列，其中每个箭头指向列表中的下一个箭头（如果需要则循环）。

t-u -> t-x
t-x -> t-u
u-v (3) -> u-t
u-t -> u-v (3)
v-w -> v-u (3)
v-u (3) -> v-w
w-v -> w-y
w-y -> w-v
x-y -> x-t
x-t -> x-y
y-z (2) -> y-w
y-w -> y-x
y-x -> y-z (2)
z-y (2) -> z-y (2)

我们通过构建一个新的置换，其中每个飞镖指向其当前分配的反向，来计算此嵌入的对偶。

t-u -> x-t
x-t -> y-x
y-x -> z-y (2)
z-y (2) -> y-z (2)
y-z (2) -> w-y
w-y -> v-w
v-w -> u-v (3)
u-v (3) -> t-u

t-x -> u-t
u-t -> v-u (3)
v-u (3) -> w-v
w-v -> y-w
y-w -> x-y
x-y -> t-x

现在，我已经将排列分组成循环。这些循环是PSLG的面（顺时针顺序内部多边形和逆时针顺序无限面）。使用有向面积测试来找到无限面。

回到图形表示，对以无限面为根的面进行深度优先搜索，标记每个面为奇数（如果边上数字的总和为奇数）或偶数。奇数循环的集合就是你要寻找的结果。

实际上，既然我已经写出了整个答案，最好只需删除开始的偶数重复段，将相邻的多边形压缩在一起。这可能会导致多个无限面，但检测方法仍然有效。

- David Eisenstat