算法技术手册（原书第2 版）

计算几何

｜

245

计算几何

算法

经过了实践的检验，它通过关注数据的子集来改善性能。试想一下，使用一条水平

线

L

从上至下扫描线段，然后输出和线段的交点。图

9-7

给出了从上到下扫描时线段

L

的状态。

图 9-7：寻找 6 条线段的 7 个交点

线段扫描的创新之处在于将所有线段从左至右按照

y

坐标进行排序。水平线段被认为左

端点“高于”右端点。线段

只可能和扫描线上的相邻线

段有交点。具体来说，如果两条

线段

S

i

和

S

j

相交，那么肯定有某个时间点，它们在扫描线上处于相邻位置。

线段扫描算

法

能通过所维护线段的状态来实现交点的高效检测。

在仔细地检查图

9-7

的扫描线选择的

9

个位置时，我们会发现这些位置是线段的起点、

终点或者交点。

线段扫描

不会真的在笛卡儿平面上做“扫描”动作，而是首先在事件队

列中插入线段的

2*n

个端点，这个事件队列是一个优化过的优先队列。所有交点都可以

在处理这些点时找到。

线段扫描算法

处理这个队列，维护

L

的状态并检测

L

上相邻的线

段是否相交。

9.5.1 输入 / 输出

线段扫描算法

可处理笛卡儿平面上规模为

n

的线段集

S

。

S

中可以没有重复的线段。没

有两条线段会共线（也就是说，重叠或者有相同的斜率）。该算法可以处理水平或者垂

直线段，但是需要仔细地计算并对线段进行精准的排序。线段不能只包含一个点（例如，

一条起点和终点相同的线段）。

输出是

k

个交点（如果存在），以及

S

中相交于交点

P

i

的实际线段。