7.7 线段相交
(Intersection of Segments)

我们已经看到，\(\Omega(n^2)\) 是两个各含 \(n\) 条边的多边形求交问题的下界。但在许多实际应用中，最坏情况很少发生。 这促使我们开发一种输出规模敏感的算法，其复杂度取决于输出结果的规模 \(k\)，即交点顶点的数量。 事实证明，这项任务的难点在于一个更一般的问题: 寻找平面上 \(n\) 条线段的所有交点。之所以说它更一般，是因为它不假设这些线段连接起来构成多边形的。 接下来，我们将探讨线段相交问题，介绍一种由 Bentley & Ottmann (1979) 提出的一个优雅算法，这是计算几何中最早的对输出规模敏感的算法之一。 我们将在 7.8 节回到多边形相交的问题。

暴力求交算法的时间复杂度为 \(\Omega(n^2)\)。它需要逐一检查每个线段与其他所有线段是否相交， 例如使用 7.2 节中的 SegSegInt 函数。 为了实现输出敏感，我们希望只计算那些实际相交的线段对之间的交点。这个目标听起来像是循环论证，但这也蕴含着解决问题的线索，因为相交的线段彼此是靠近的，并非在其整个长度上都靠近， 而是在其相交处非常接近! 如果我们能以某种方式沿着两条线段"向下行进"，直到它们彼此靠近后在判定是否相交，我们就能实现输出敏感。平面扫描(Plane sweep)提供了所需的"向下行进(travel down)"机制。

回想一下 2.4 节，我们可以用一条水平线 \(L\) 扫描多边形的边，并仅在 \(L\) 命中的顶点的局部邻域内搜索弦的交点， 从而高效地计算梯形分解。这正是我们解决线段相交问题所需的局部交点(local focus)。

想象一下用直线 \(L\) 扫描一组线段 \(S = \{s_0, s_1, \dots, s_{n-1}\}\)。设 \(x = s_i \cap s_j\) 是两条线段之间的交点。 在 \(L\) 到达 \(x\) 之前，\(L\) 同时穿过 \(s_i\) 和 \(s_j\)，并且它们在 \(L\) 上相邻。即，在 \(L\) 上，它们之间没有其他线段。 因此，在每个相交事件(\(L\) 穿过交点时)之前，相交的线段在 \(L\) 上都是相邻的。这提供了我们寻求的局部性: 计算 \(L\) 上相邻线段之间的交点就足以捕获所有交点。 虽然其中一些相邻线段实际上并不相交，但我们会发现这种浪费是很小的。

为了聚焦于主要思想，我们做出一下几个简化假设: 假设没有线段是水平的，也没有三条线段通过同一点。计划是用 \(L\) 扫过这些线段，并在三种类型的事件发生时停止:

1. 到达线段的上端点; the top endpoint of a segment is hit
2. 经过线段的下端点; the bottom endpoint of a segment is passed
3. 到达两条线段的交点。an intersection point between two segments is reached

这三个事件都会导致被扫描线 \(L\) 穿过的线段列表 \(\mathcal{L}\) 发生变化，分别是插入线段、删除线段，或者交换两个相邻线段的位置。每当发生变化后，都需要计算新相邻线段之间的交点。

虽然到达两个线段交点 \(x\) 之前必须在 \(\mathcal{L}\) 中变为相邻，但这并不保证当 \(x\) 被计算出来时，它就是下一个相交事件。 相反，相交事件必须与线段端点一起放入按高度排序的队列 \(Q\) 中。如图 7.17 中所示的线段集合 \(S = \{s_0, s_1, \ldots\}\)。 设 \(a_i\) 为线段 \(s_i\) 的上端点，\(b_i\) 为其下端点。那么事件队列被初始化为 \(Q = (a_0, a_1, a_2, a_3, a_4, a_5, a_6, b_2, \ldots)\)， 即所有线段端点按从上到下的顺序排列。当 \(L\) 到达 \(a_1\) 和 \(a_2\)(位置 1)时，\(s_0\) 和 \(s_1\) 变为新相邻，它们的交点 \(x_{01}\) 被添加到队列中 \(b_2\) 的后面。 \(s_1\) 和 \(s_2\) 也是新相邻但不相交。注意此时，较高的交点 \(x_{56}\) 尚未被构建。

在位置 2，\(L\) 碰到 \(a_3\)，新相邻的线段 \(s_3\) 和 \(s_0\) 不相交。此时 \(\mathcal{L} = (s_3, s_0, s_1, s_2)\)。 在位置 3，\(L\) 碰到 \(a_4\)，交点 \(x_{34}\) 被添加到 \(Q\) 中的适当位置。注意，在到达 \(x_{34}\) 之前，将会遇到 \(s_3\) 和 \(s_4\) 之间的三个相交事件。 当 \(L\) 到达位置 6 的第一个相交事件时，上方的所有端点都已被处理，且 \(\mathcal{L} = (s_3, s_5, s_6, s_4, s_0, s_1)\)。该事件导致 \(s_5\) 和 \(s_6\) 在 \(\mathcal{L}\) 中交换位置， 引入新的相邻关系，\(x_{36}\) 和 \(x_{45}\) 被添加到 \(Q\)。此时 \(Q\) 包含了图中所示的所有画圈的交点。

该算法需要维护两个动态数据结构分别用于 \(\mathcal{L}\) 和 \(\mathcal{Q}\)。两者都必须支持快速插入和删除，以实现整体较低的时间复杂度。 平衡二叉树足以保证 \(\mathcal{L}\) 和 \(\mathcal{Q}\) 的存储空间与其元素数量 \(m\) 成正比，并且所有必要的操作都能在 \(O(\log m)\) 时间内完成。 我们不再深究数据结构的细节。现在，我们论证这样的结构使得 \(n\) 条相交线段的时间复杂度为 \(O((n + k) \log n)\)，其中 \(k\) 是线段的交点数。我们将继续假设没有三条线段交于一点。

事件总数为 \(2n + k = O(n + k)\)，即 \(2n\) 个线段端点和 \(k\) 个交点。因此，\(\mathcal{Q}\) 的长度永远不会超过这个值。 因为每个事件在 \(\mathcal{Q}\) 只插入和删除一次，所以维护 \(\mathcal{Q}\) 的总成本是 \(O((n + k) \log(n + k))\)。 因为 \(k = O(n^2)\)，所以 \(O(\log(n + k)) = O(\log n + 2\log n) = O(\log n)\)。因此，维护 \(\mathcal{Q}\) 的成本为 \(O((n + k) \log n)\)。

维护 \(\mathcal{L}\) 的总成本是 \(O(n \log n)\)。每次插入和删除 \(n\) 条线段的成本都是 \(O(\log n)\) 的。剩下的只是限制交点计算的次数， 每次计算可以通过调用函数 SegSegInt(Code7.2)在常数时间内完成。 回想一下之前关于浪费算力的担忧。然而，交点计算次数最多是事件数量的两倍，因为每个事件最多产生两个新的线段邻接关系，插入的线段与其新邻居，删除中间线段时产生的两个新邻居， 以及在交点事件处切换时产生的新左右邻居。因此，交点计算的总数为 \(O(n + k)\)。

因此，该算法的整体时间复杂度为 \(O((n + k) \log n)\)，对输出规模 \(k\) 敏感。我们已经看到，空间需求是 \(O(n + k)\)，因为这是 \(\mathcal{Q}\) 可能增长的最大长度。 事实证明，空间需求可以降低到 \(O(n)\)(练习 7.8.1[2])。此外，这两个理想的复杂度都可以在不进行任何简化假设的情况下实现(练习 7.8.1[1])。

这些成果在 1981 年就已经实现了(Bentley & Ottmann 1979; Brown 1981)，但还需要十多年的进一步研究才取得在时间和空间上都最优的算法：

这里，\(k\) 不再像最初的 Bentley–Ottmann 算法那样需要乘以 \(\log n\)。虽然实际应用中的差异可能微乎其微，但要填补这一理论上的差距，仍需开发新的技术手段。