7.8 非凸多边形交集
(Intersection of Nonconvex Polygons)

修改 Bentley-Ottmann 扫描线算法来计算两个多边形的交集并不困难。 设这两个多边形为 \(A\) 和 \(B\)，其顶点分别标记为 \(a_i\) 和 \(b_j\)。其主要思想类似于扫描线算法在图形屏幕上填充(绘制)多边形区域， 并与我们在 7.4 节中的射线交叉分析有关。沿着扫描线 \(L\) 的长度维护一个“状态”指示器，其值如下:

1. \(\emptyset\): 在两个多边形外部
2. \(A\): 在 \(A\) 内部，但在 \(B\) 外部
3. \(B\): 在 \(B\) 内部，但在 \(A\) 外部
4. \(AB\): 同时在 \(A\) 和 \(B\) 内部。

状态记录发生在被扫描线 \(L\) 穿过的每两个相邻线段之间的跨度(span)内。显然，在每个跨度内，状态保持不变。

如图 7.18 所示，当 \(L\) 处于位置 2时，即事件 \(b_1\)，从左到右的状态列表是 \((\emptyset, A, AB, B, \emptyset)\)。这些信息可以很容易地存储在表示 \(L\) 的同一数据结构中。 我们不会深入探讨数据结构的细节，而是结合图 7.18 中的示例，概述如何在处理线段相交事件的同一次扫描中更新状态信息。

在位置 0，当扫描线 \(L\) 击中 \(a_0\) 时，两条 \(A\) 边都在 \(a_0\) 下方，这表明我们正在插入一个 A-span。在位置 1，插入了一个 B-span。 就在 \(b_0\) 稍下方，一个相交事件开启了一个 AB-span，这很容易识别，因为相交的线段分别从相反的两侧界定 \(A\) 和 \(B\)，且 \(A, B\) 都在下方。 在位置 3，即相交事件 \(x\) 处，情况正好相反。相交的线段分别在上方界定 \(A, B\)。因此，一个 AB-span 消失，取而代之的是交换线段之间的 \(\emptyset\)-span。 在 \(a_2\)(位置 4)处，遇到了与 \(a_0\) 相反的情况。\(A\) 边在上方，一个 A-span 被周围的 B-span 包围。虽然我们还没有提供精确的规则(练习 7.8.1[5])， 但显然，扫描线算法可以在不改变渐近时间或空间复杂度的情况下维护跨度(span)状态信息。

虽然这使我们能够在光栅显示器上"绘制"交集 \(A \cap B\)，但还需要一两个额外步骤，才能获得 \(A \cap B\) 中每个"多边形"部分的边列表。 之所以给“多边形”加上引号，是因为交集可能包含退化的情况，线段、点等 —— 有时称之为"毛发hair"。 是否需要将其作为输出的一部分取决于具体应用。除了这个问题之外，还有进一步的工作要做。例如，在图 7.18 的位置 3 处，一个 AB-span 在 \(x\) 处消失， 但在局部消失的多边形部分在继续延伸到更低的扫描线位置。两个 AB-span 可能会合并，这表明在 \(L\) 上方看起来是两个分离的部分实际上在下方是连接在一起的。

在这方面，我们可以在推进扫描线的过程中，不断扩展交点部分的多边形链边界，然后在特定事件发生时，将这些部分连接起来。 因此，图中的位置 3 是一个事件，它启动了左边界 AB-chain 与右边界 AB-chain 的连接。对链的"悬空端点(dangling endpoints)"数量追踪，可以检测到何时可以完整输出整个部分。 例如，在图中的位置 4，\(a_2\) 封闭了该链，可以打印出一个完整的部分；而在位置 3，在 \(x\) 处连接的链在其最右侧与 \(L\) 的交点处仍然保持开放状态。此处我们不再赘述细节。

最后不难看出，我们其实可以直接计算 \(A \cup B\)，或 \(A \setminus B\)，或 \(B \setminus A\)——状态指示符足以区分这些运算。 因此，所有多边形之间的布尔运算都可以用 Bentley-Ottmann 扫描线算法的变体来构建，并且时间复杂度相同。这些布尔运算是许多 CAD/CAM 软件系统的核心， 例如，它们通过从一个形状中减去另一个形状、连接形状、切掉形状的一部分等方式来构造用于数控加工的复杂零件，而所有这些操作都是布尔运算。

7.8.1. 练习

1. 处理退化情况 Handling degeneracies。
   1. [Easy] 证明在不增加时间或空间复杂度的情况下，所提出的算法可以处理水平线段。
   2. [more difficult] 证明处理多条线段通过同一个交点的情况，不会增加时间或空间复杂度。
2. 降低空间需求 Reducing the space requirements。证明 Pach & Sharir (1991) 提出的以下策略(另见 de Berg et al. (1997,p.29))可以将 Bentley–Ottmann 算法的空间需求降低到 \(O(n)\)， 而不会增加其时间复杂度。每当生成的线段不在相邻，例如图 7.17 中的 \(x_{34}\)，是因为在他们之间遇到了另一条线段时，本例中为 \(s_5\)，就从集合 \(Q\) 中删除该交点。 之后该交点会被重新计算并再次插入 \(Q\) 中。
3. [Programming] 线段求交 Intersection of segments。使用 SegSegInt(Code7.2) 作为子程序，用朴素数据结构实现 Bentley–Ottmann 算法。
4. 退化相交 Degenerate intersections。
   1. [easy] 举例说明 \(A \cap B\) 可以是一条由线段组成的路径(即多边形链)。
   2. 证明两个简单多边形交集的任何连通部分在拓扑上都不可能等价于构成"Y"形的三个线段的并集。
5. 跨度状态规则 Span status rules。详细说明在扫描两个多边形过程中可能发生的各种事件的跨度状态信息更新规则。
6. [easy] 多边形简单性 Polygon simplicity。证明 Bentley–Ottmann 算法可用于在 \(O(n \log n)\) 时间内检测给定的 \(n\) 个点列表是否构成简单多边形。