Description
专题图的叠合（也称为地图的叠加或图层叠加）是地理信息系统（GIS）中一种常用的技术, 地理信息系统将（不同类型的）信息划分为若干层（layer）, 每一层都是一幅专题图（thematic map）(存放某一特定类型的信息), 用于将多种地理数据的图层组合在一起, 以分析、比较和可视化不同类型的数据。通过叠合，可以发现不同数据集之间的关系、趋势和模式。这种技术广泛应用于城市规划、环境管理、资源评估等领域。
1 - 线段求交
描述
给定由平面上 \(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 中各线段之间的所有交点（以及穿过各交点的线段的信息）
- 初始化一个空的事件队列 \(Q\), 然后，将所有线段的（上、下）端点插入 \(Q\) 中；对于上端点，还要记录其对应的线段
- 初始化一个空的状态结构 \(T\)
- \(\textbf{while} (Q 非空)\)
- \(\quad \textbf{do} 找出 Q 中的下一事件点 p，将其删除\)
- \( \quad \quad HANDLEEVENTPOINT(p)\)
事件的处理方法
- 若是线段的端点，则需要在状态结构 T 中插入或删除线段
- 若是交点，则需要交换(对应的)两条线段的次序
- 在事件发生后，对每一对新近成为邻居的线段, 都要进行
相交测试
算法: \(HANDLEEVENTPOINT(p)\)
- \(令 U(p) 为所有以 p 为上端点的线段构成的集合; \ 这些线段都与事件点 p 存放 在一起 (若是水平线段，则以其左端点做为上端点)\)
- \(在 T 中找出包含 p 的所有线段 (\textbf{在 T 中，这些线段是(依次)相邻的})在 所找出的线段中 将那些以 p 为下端点的线段组成集合 L(p) 将那些在内部包含 p 的线 段组成集合 C(p)\)
- \(\textbf{if}(L(p) \cup U(p) \cup C(p) 包含不止一条线段)\)
- \(\quad \textbf{then} 报告“发现交点 p”; 同时返回 L(p), U(p) C(p)\)
- \(将 L(p) \cup C(p)中的线段从 T 中删除\)
- \(将 U(p) \cup C(p)中的线段插入到 T 中 (_ T 中各线段的次序，必须与它们和扫描 线刚离开 p 之后的相交次序一致 ) ( 若存在水平的线段，则将它排在包含 p 的所有 线段 2 的最后 _)\)
- \(\)
- \(\)
- \(\)
- \(\)
- \(\)
- \(\)
- \(\)
- \(\)
- \(\)
- \(\)
查找新交点
判断两条直线是否相交, 如果存在交点, 分两种情况: 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 为实际的交点总数