线段扫描

很多情况下,我们需要在几何形状中检测交点。例如在大规模集成电路设计中,精密的电路将会印制在电路板上,因此除了预先设计好的交点之外,不能存在其他交点。在做旅游计划时,大量的路在数据库中以线段的形式存储,我们需要根据交点来将路网打断。

图9-13是一个例子,在6条线段中有7个交点。也许我们不需要比较所有的C(n,2)或者n*(n-1)/2条线段。相互之间离得很远的线段很明显不会有交点。线段扫描算法是一个已经证明的高效算法,它在处理时关注数据的一个子集,而不是全部数据,这样能够提高效率。想象一下,扫描并且输出水平线L和输入线段的交点。图9-13是从上到下扫描时,线段L的状态。

阅读 ‧ 电子书库
图 9-13 在6条线段中检测到7个交点

线段扫描的创新在于将所有的线段从左至右按照y坐标进行排序[1]。线段只可能和扫描线上的相邻线段有交点。具体来说,有两条相交的线段Si和Sj,那么在扫描线上,肯定有它们相邻时。线段扫描算法能高效地维护扫描线状态,因此它能够快速地检测交点。

广告:个人专属 VPN,独立 IP,无限流量,多机房切换,还可以屏蔽广告和恶意软件,每月最低仅 5 美元

我们仔细地看看在图9-13的水平线上那9个选择了的位置,你将会发现这些位置是线段的起点或者终点,也或是一个交点。线段扫描不会真正地在笛卡儿平面上扫描线段,它首先在事件队列中插入2*n条线段的端点,这个事件队列是一个优化过的优先队列,如图9-14所示。所有的属于起点或者终点的交点都可以在处理这些点时找到。线段扫描算法对这个队列进行处理,维护L的状态,检测是否相邻的线段相交。其逻辑如图9-15所示。

阅读 ‧ 电子书库
图 9-14 线段扫描算法详解(第一部分)
阅读 ‧ 电子书库
图 9-15 线段扫描算法详解(第二部分)

输入/输出

输入

笛卡儿平面上规模为n的线段集S。

输出

这些线段的k个交点(如果存在)。

假设

在S中不会出现重复的线段。没有两条线段会共线(也就是说,重叠或者有相同的斜率)。算法需要仔细地计算和精准地排序线段,这样才能支持垂直线段或者水平线段。没有一条线段只有一个点(例如,一条起点和终点相同的线段)。

[1]水平线段被认为左端点(高于)右端点。