Line Segment Intersection

2.1Line Segment Intersection

The network overlay Problem

对于两个网络的叠加，几何情况如下：给定两组线段，计算来自一组的一个段与来自另一个的一个段之间的所有交叉点。

为了简化描述，我们将两组中的段放入一组，并计算该组中各段之间的所有交叉点。
给定平面中n个闭合段的集合S，计算S中段之间的所有交叉点。

如果直接遍历任意两条线段判断是否相交，则其时间复杂度为O（n2）

Output-sensitive algorithm
算法的运行时间对输出的大小敏感。 我们也可以将这种算法称为交叉敏感。

然而事实情况下，只有临近的线段才有相交的可能。

Plane sweep algorithm（平面扫描线算法）

Let S={s1,s2,……，sn} be the set of segments for which we want to compute all intersections.

L扫描线
水平线，自顶向下移动

event Point（事件点）
the endpoints of the segments.（线段的两端）

扫描线经过事件点时更新扫描线的状态并执行一些交叉测试。
如果事件点是上端点，测试其与扫描线相交的其他线段是否相交
如果事件点是下端点，则将其从状态中删除。

因此该算法不是输出敏感的。
问题是与扫掠线相交的两个段在水平方向上仍然可以相隔很远。
在扫描线相交时，从左到右排序
仅在水平排序中相邻时测试段

自顶向下的扫描控制了在垂直方向的临近关系，而仅在水平排序中相邻时才测试段，又控制了其在水平方向的临近关系。大大的减少了运算量。 ——赵静

在相交点处，邻居关系会发生改变
相交点是一新的事件点

假设
1、没有段是水平的
2、任何两个段最多相交一个点，它们不重叠
3、并且没有三个段在一个公共点相交。

Lemma 2.1

Let si and sj be two non-horizontal segments whose interiors intersect in a single point p, and assume there is no third segment passing through p. Then there is an event point above p where si and sj become adjacent and are tested for intersection.

si 和sj相交于点P，则P的上方存在一个事件点，使得si和sj相邻。

Proof of Lemma 2.1

当l 和p点足够接近时，si和sj必定是邻居关系。但是在算法开始的时候，si和sj还不是邻居。

---

至此为止
事件点包括以下两种类型

• endpoints of the segments
• the intersection points

当扫描线经过上端点Sj时，需要检测与其相邻的Si和Sk是否相交。在上图的情况下，si和sj的交点会被检测出来。

当扫描线经过交点时，需要改变线段的相邻关系

扫描线经过下端点Sl时，sl原来的两个邻居sk和sm称为了彼此的邻居，此时需要检测sk和sm是否相交。

Degenerate cases

算法所使用的数据结构
事件队列Q
同一水平线上的事件点从左到右处理

根据此顺序，我们将事件点存储在平衡的二叉搜索树中

操作需要O（logn）的时间

Algorithm FINDINTERSECTIONS(S)

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

在退化情况下（即某个事件点涉及到多条线段时）

HANDLEEVENTPOINT§

令 U§为所有以 p 为上端点的线段构成的集合; 这些线段都与事件点 p 存放在一起(若是水平线段，则以其左端点做为上端点)
将那些以p为下端点的线段组成集合L§
将那些在内部包含p的线段组成集合C§

如果L§∪U§∪C§包含不止一条线段，则p是交点

Lemma 2.2

Algorithm FINDINTERSECTIONS computes all intersection points and the segments that contain it correctly.

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

Lemma 2.3

The running time of Algorithm FINDINTERSECTIONS for a set S of n line segments in the plane is O(nlogn+Ilogn), where I is the number of intersection points of segments in S.

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

Theorem 2.4

Let S be a set of n line segments in the plane. All intersection points in S, with for each intersection point the segments involved in it, can be reported in O(nlogn+I logn) time and O(n) space, where I is the number of intersection points.

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

2.2The Doubly-Connected Edge List

(双向链接边表)

vertex (顶点）
The embedding of a node of the graph is called a
vertex

edge（边）
The embedding of an arc is called an edge

face（面）
A face of the subdivision is a maximal connected subset of the plane that doesn’t contain a point on an edge or a vertex

complexity
复杂性取决了顶点数、边数、面数

A doubly-connected edge list

half-edges
a half-edge bounds only one face
将每条边理解为两条反向的有向边
每条边都是一个半边

逆时针的半边形成一个面
在每条边(对应的记录)中存储一个指针，指向下一条边。
若一条半边e 起始于v，终止于w，则Twin(e )起始于w，终止于v。

沿着空洞的边界逆时针前进，面却总是居于左侧。

DCEL结构的各组成部分

每条半边有自己的前驱（Prev）和后继（Next）
一条边分割两个面，半边对应一个面

如图对应于边 ei 的两条半边分别 记为e i,1 和e i,2。
图中共两个面，f1和f2。f1由顺时针方向的边构成，f2由逆时针方向的边构成。
f1 无环封闭，内有洞，则有内分量；f2有环封闭，有外分量

表为双向链接边表的数据结构，记录了每个半边的源顶点，孪生边，左侧面，前驱和后继信息。

2.3Computing the Overlay of Two Subdivisions

（计算子区域划分的叠合）

如图，计算两个子区域划分的重叠情况

Algorithm for computing the Overlay of Two Subdivisions

基于2.1节的平面扫描算法，用于计算一组线段和双重连接边列表中的交点

重叠情况分三种：

• s1的一条边经过s2的一个顶点
• s1的一条边和s2的一条边相交
• s1的一个点与s2的一个点重合

Compute the information about the faces of O（s1,s2）

O（s1,s2）表示s1 和s2的叠合

如果该角度小于180°，则环是外边界，否则它是孔的边界。在每个环上，只有最左端的顶点才具有这个性质，而其它的顶点则不见得。

Definition:There is an arc between two cycles if and only if one of the cycles is the boundary of a hole and the other cycle has a half-edge immediately to the left of the leftmost vertex of that hole cycle.

Lemma 2.5

Each connected component of the graph G corresponds exactly to the set of cycles incident to one face.

图 G 中的每一连通子块，都恰好对应于与某张面相关联的所有(内、外)环。

Theorem 2.6

Let S1 be a planar subdivision of complexity n1, let S2 be a subdivision of complexity n2, and let n := n1 + n2. The overlay of S1 and S2 can be constructed in O(n log n + k log n) time, where k is the complexity of the overlay.

给定任意两个平面子区域划分 S1 和 S2，其复杂度分别为 n1 和 n2，令 n = n1 + n2。则可以在 O(nlogn + klogn)时间内计算出 S1 与 S2 的叠合，其中 k 为叠合结果的复杂度。

2.4 Boolean Operations

布尔运算实现两个多边形P1 和P2 的布尔运算(boolean operation)⎯⎯并(union)、交 (intersection)和差(difference)

Corollary 2.7

Let P1 be a polygon with n1 vertices and P2 a polygon with n2 vertices, and let n := n1 +n2. Then P1 ∩P2, P1 ∪P2, and P1 \P2 can each be computed in O(n log n + k log n) time, where k is the complexity of the output.

任意给定两个多边形 P1 和 P2，设其顶点数分别为 n1、n2，令 n := n1 + n2。则可以在 O(nlogn + klogn) 时间内，计算出 P1∩P2、P1∪P2 或 P1\P2，其中 k 为最终输出的复杂度。