线段求交

描述

给定由平面上 \(n\) 条闭线段构成的一个集合 \(S\), 求出 \(S\) 中个线段之间 的所有交点. 其中闭线段是指不同线段端点的重合也将被视为交点

“输出敏感"的算法

我们所希望得到的算法，其运行时间不仅取决于输入中线段的数目，还取决于（实际的）交 点数目。这样的算法，被称为“输出敏感的”算法（output-sensitive algorithm）⎯⎯ 也就 是说，这种算法的运行时间对（实际）输出的大小很敏感。也可以称这样一个算法是“交点 敏感的”（intersection-sensitive）⎯⎯ 因为，输出的大小就是由交点的数目决定的

引理 2.1

设两条非水平的线段 \(si\) 和 \(sj\) 只相交于其内部的一点 \(p\)，而且，任 何第三条线段都不经过 \(p\)。则在（扫描线到达）高于 \(p\)$ 的某个事件点处（ 时），\(si\) 和 \(sj\) 必然会彼此紧邻，并因此接受相交测试（于是对应的交点 将被发现）。

几何分析

  • 将一条线段在y轴上的正交投影, 定义为该线段的 y-区间, 任何两条线段, 只要其y-区间没有重叠部分, 则一定不会相交

事件队列(Event Queue)

在该算法中的队列是一个有序队列, 且在该队列中的查找是基 于平衡二分查找树(balanced binary search tree).

  • Enqueue: 来存放（当前已被检测出来，但尚未发生的）事件。
  • Dequeue: 把即将发生的下一事件从 Q 中删除掉，并将它返回（给主程序），以便对它进 行处理。
  • Insert:
  • Sort:

状态结构(Status Structure)

状态(是与当前扫描线相交的所有线段构成的有序序列), 通过一个状态结构（status structure），可以访问某一给定线段\(s\)的（左、右）邻居.

在插入一个线段\(s\)之后, 就可以立即进行相应的相交测试

这个状态结构式动态的, 当有某条线段开始（或不再）与扫描线相交，就应将它插入到状 态结构中（或从状态结构中删去）

在任一时刻(在某一事件点), 状态结构中的所有线段之间具有一个定义明确的次序(与当前 扫描线相交的每条线段，都按照其次序，)，因此可以使用一棵平衡二分查找树来实现状 态结构

平面扫描线算法(plane sweep algorithm)

  • 扫描线(sweep line)
  • 扫描线的状态(status): 当前扫描线相交的所有线段构成的集合
  • 事件点(event point): 扫描线的状态进行更新

只有在扫描线触及某个事件点的时候，算法才会进行实质的处理⎯⎯更新扫描线的状态，并进行一些相交测试

算法: \(FINDINTERSECTIONS(S)\)

Input：平面线段集 S

Output: S 中各线段之间的所有交点（以及穿过各交点的线段的信息）

  1. 初始化一个空的事件队列 \(Q\), 然后，将所有线段的（上、下）端点插入 \(Q\) 中；对于上端点，还要记录其对应的线段
  2. 初始化一个空的状态结构 \(T\)
  3. \(\textbf{while} (Q 非空)\)
  4. \(\quad \textbf{do} 找出 Q 中的下一事件点 p，将其删除\)
  5. \( \quad \quad HANDLEEVENTPOINT(p)\)

事件的处理方法

  • 若是线段的端点，则需要在状态结构 T 中插入或删除线段
  • 若是交点，则需要交换(对应的)两条线段的次序
  • 在事件发生后，对每一对新近成为邻居的线段, 都要进行相交测试

算法: \(HANDLEEVENTPOINT(p)\)

  1. \(令 U(p) 为所有以 p 为上端点的线段构成的集合; \ 这些线段都与事件点 p 存放 在一起 (若是水平线段，则以其左端点做为上端点)\)
  2. \(在 T 中找出包含 p 的所有线段 (\textbf{在 T 中，这些线段是(依次)相邻的})在 所找出的线段中 将那些以 p 为下端点的线段组成集合 L(p) 将那些在内部包含 p 的线 段组成集合 C(p)\)
  3. \(\textbf{if}(L(p) \cup U(p) \cup C(p) 包含不止一条线段)\)
  4. \(\quad \textbf{then} 报告“发现交点 p”; 同时返回 L(p), U(p) C(p)\)
  5. \(将 L(p) \cup C(p)中的线段从 T 中删除\)
  6. \(将 U(p) \cup C(p)中的线段插入到 T 中 (_ T 中各线段的次序，必须与它们和扫描 线刚离开 p 之后的相交次序一致 ) ( 若存在水平的线段，则将它排在包含 p 的所有 线段 2 的最后 _)\)
  7. \(\)
  8. \(\)
  9. \(\)
  10. \(\)
  11. \(\)
  12. \(\)
  13. \(\)
  14. \(\)
  15. \(\)
  16. \(\)

查找新交点

判断两条直线是否相交, 如果存在交点, 分两种情况: 1. 已被处理, 2. 未被处理. 另外, 如果两条直线中存在水平直线时候(因为扫描线与 x 轴平行), 即出现与扫描线 y 坐标相同 的事件点时, 按照从左向右的顺序处理

算法: FindNewEvent(sl, sr, p)

$$1. \textbf{if} (sl 和 sr 相交于当前扫描线的下方 \\ (或者交点正好落在当前扫描线上并且在当前事件点的右侧)，\\ 而且该交点尚未做为一个事件出现在 Q 中) \\ 2. then 将这个交点做为一个事件，插入到 Q 中$$

引理 2.2

算法 FINDINTERSECTIONS 能够正确地计算出所有的交点，并能同时给出穿过各交点的线 段。

引理 2.3

对于由平面上任意 n 条线段组成的集合 S，算法 FINDINTERSECTIONS 的运行时间都是 O(nlogn + Ilogn)，其中 I 为 S 中各线段之间的交点总数

引理 2.4

给定由平面上任意 n 条线段构成的一个集合 S。可以在 O(nlogn + Ilogn)时间内，使用 O(n)空间，报告 出 S 中各线段之间的所有交点，以及与每个交点相关的所有线段。其中 ，I 为实际的交点总数