浏览量:602

3.7. 线段集的交

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。

PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry

3.7. 线段集的交

本小节重点解决求线段集中所有交点的问题,首先会先介绍线段集相交算法的发展历史及其应用,然后介绍Shamos-Hoey算法的基本思想,因为Bentley-Ottmann算法只是对它的扩展,最后着重介绍Bentley-Ottmann算法的基本思想和实现。

3.7.1. 线段集相交算法简介

\(n\)条线段的相交测试,最多有\(n\left( {n - 1} \right)/2 = O({n^2})\)个交点,最坏情况下就需要一个时间复杂度为\(O({n^2})\)的算法。最简单的暴力算法就是分别对\(O({n^2})\)个线段对进行相交测试,并记录下所有的交点,但对于只有少数交点的线段集,则不需要对每个线段对进行相交测试。

\(S\)\(n\)条线段的集合,\(I\)是线段集\(S\)中所有的\(k\)个交点的集合,当\(k = \left( {n - 1} \right)n/2\)时,是最坏情况[14]。早在1976年,Shamos&Hoey[6]提出了通过扫描线的方法在时间为\(O(n\log n)\)、空间为\(O(n)\)内判定集合\(S\)中是否存在相交点的算法。3年后,Bentley&Ottmann[7]对该算法进行了扩展,新的算法能在时间为\(O(n\log n + k\log n)\)、空间为\(O(n + k)\)内,计算集合\(S\)中所有的交点,Pach& Sharir[17](1991)、Brown[18](1981)把该算法的空间降低到了\(O(n)\)。由于Bentley-Ottmann算法容易理解、实现较为简单,因此在之后的几十年里得到广泛的应用,但是求线段集所有交点的问题的理论下限为\(O(n\log n + k)\),Bentley-Ottmann算法并没有达到理论上的下限,Chazelle[8](1986)提出了一种时间为\(O(n{\log ^2}n/\log \log n + k)\)的算法,进一步降低了时间复杂度。直至1988年,Chazelle& Edelsbrunner[9,10]提出了时间复杂度达到最优的算法,但是他们提出的算法需要\(O(n + k)\)的空间,而且很难实现。后来,Balaban[11] (1995)对算法进行改进,发现了一种时间为\(O(n\log n + k)\)、空间为\(O(n)\)的确定性算法。也有人通过随机算法,使得平均时间复杂度达到\(O(n\log n + k)\),最早由Myers[12](1985)提出的算法需要\(O(n + k)\)的空间,Clarkson& Shor[13](1989)把空间降到\(O(n)\)

对于“求红-蓝线段集交点”的问题,即有两个线段集合\({S_1}\)\({S_2}\),分别称为红线段集和蓝线段集,只考虑集合\({S_1}\)\({S_2}\)之间的相交,不考虑集合内部的相交。针对这类问题,有更加简单、高效的算法,Chan[16](1994)基于Mairson& Stolfi[15](1988)的研究,提出了一种时间为\(O(n\log n + k)\)、空间为\(O(n)\)的确定性算法。

近几十年,虽然出现了很多比Shamos-Hoey算法、Bentley-Ottmann算法在时间、空间复杂度更低的算法,但是它们仍具有里程碑的意义,由于易理解、易实现,它们仍具有广泛的应用,例如判定一个多边形是否是简单多边形,把非简单多边形分解成多个简单多边形,平面划分,多边形布尔操作等。

但是,Bentley-Ottmann算法也存在一定的局限,它的时间复杂度与交点个数相关,如果交点的个数为\(O({n^2})\),那么算法的时间复杂度就是\(O({n^2}logn)\),比暴力算法还慢;如果交点的个数小于等于\(O(n)\),那么算法能达到\(O(nlogn)\)的时间复杂度。

3.7.2. Shamos-Hoey算法

问题描述:输入是一个线段集合\(S = \{ {L_i}\} ,0 \le i \prec n\),判断线段集\(S\)中是否存在相交。

2015-3-22 23-06-37

图3.24 Shamos-Hoey算法的基本思想

Shamos-Hoey算法解决的就是判定给定线段集中是否存在交点的问题,可以把它看作是一种扫描线算法(Sweep Line Algorithm),如图3.24所示,一条垂直扫描线从左往右扫描整个平面,直至扫描完线段的每个端点。

线段的每一个端点可以当作是事件(Event),如图3.24所示,每条线段的端点\({p_i},{q_i}\)都构成算法中的事件。扫描线是虚拟的垂直直线,从左到右扫描,经过每个事件,都产生一条虚拟的扫描线。

每条扫描线与线段存在交点,与同一条扫描线相交的线段是可对比的。我们需要定义线段之间的大小关系,设扫描线的横坐标为\(x\),与该扫描线相交的线段为\(A\)\(B\),它们分别相交于点\({P_A}\)\({P_B}\),若\({P_A}\)\({P_B}\)的上方,记作\(B \prec A\),即越往下线段越小,越往上线段越大。如图3.24所示,经过事件\({p_2}\)的扫描线,三条线段的大小关系为\(\overline {{p_2}{q_2}} \prec \overline {{p_1}{q_1}} \prec \overline {{p_0}{q_0}} \)\(\overline {{p_1}{q_1}} \)是与\(\overline {{p_0}{q_0}} \)相邻且位于其下方的线段,\(\overline {{p_1}{q_1}} \)是与\(\overline {{p_2}{q_2}} \)相邻且位于其上方的线段,而在该扫描线上\(\overline {{p_3}{q_3}} \)\(\overline {{p_2}{q_2}} ,\overline {{p_1}{q_1}} ,\overline {{p_0}{q_0}} \)是不可对比的,线段的大小关系是相对于扫描线而言,扫描线是基于事件而定的。

存储线段的数据结构,称它为扫描线结构(Sweep Line Structure),用\(SL\)来表示。在给定扫描线上,存储在\(SL\)中的线段是有序的,而且\(SL\)中的线段是动态变化的:(1)当处理线段的左端点时,需要把该线段加入\(SL\)中;(2)当处理线段的右端点时,需要把该线段从\(SL\)中删除;(3)还需要查询与指定线段相邻且位于其上方或者下方的线段。可以考虑采用平衡二叉树来设计\(SL\),这样线段的插入、删除、查询操作可以在\(O(\log n)\)时间内完成,对\(SL\)的操作有:

  1. \(SL.insert(L)\),把线段\(L\)插入\(SL\)中;
  2. \(SL.{\mathop{\rm delete}\nolimits} (L)\),把线段\(L\)\(SL\)中删除;
  3. \(SL.{\mathop{\rm above}\nolimits} (L)\),返回与线段\(L\)相邻且位于其上方的一条线段;
  4. \(SL.{\mathop{\rm below}\nolimits} (L)\),返回与线段\(L\)相邻且位于其下方的一条线段;

Shamos-Hoey算法的伪码如下所示:

设输入是一个线段集合\(S = \{ {L_i}\} ,0 \le i \prec n\),判断线段集中是否存在相交
\({\mathop{\rm SHAMOS}\nolimits} \_HOEY(S)\)
return ({TRUE , FALSE})
1.    对线段集\(S\)中的端点按照\(x,y\)的字典序进行排序,使得\({P_0}\)表示最左方的点,\({P_{2n - 1}}\)表示
最右方的点。
2.    \(SL = \emptyset \);
3.    for( i=0 ; i<2n-1; i++ )
4.           \(P\)= \({P_i}\);                                                      //设\(P\)是线段\(L\)的端点
5.           if \(P\)\(L\)的左端点, then
6.                  \(SL.insert(L)\);
7.                  \(A = SL.{\mathop{\rm above}\nolimits} (L)\);
8.                  \(B = SL.{\mathop{\rm below}\nolimits} (L)\);
9.                  if (\(A\)存在)&&( \(A\)\(L\)相交), then
10.                        return TRUE;
11.                 else (\(B\)存在)&&( \(B\)\(L\)相交), then
12.                        return TRUE;
13.                 end if;
14.          else                                                   //说明\(P\)是线段\(L\)的右端点
15.                 \(A = SL.{\mathop{\rm above}\nolimits} (L)\);
16.                 \(B = SL.{\mathop{\rm below}\nolimits} (L)\);
17.                 if (\(A\)存在)&&( \(B\)存在)&&( \(A\)\(B\)相交), then
18.                        return TRUE;
19.                 end if;
20.                 \(SL.{\mathop{\rm delete}\nolimits} (L)\);
21.          end if;
22.          return FALSE;

以图3.24为例,介绍算法Shamos-Hoey的基本过程,对线段的端点按照\(x,y\)的字典序从左到右排序,则可以得到事件队列\(\left\{ {{p_0},{p_1},{p_2},{q_0},{p_3},{q_1},{q_2},{q_3}} \right\}\),初始化扫描线结构\(SL\)为空,接着,进入for循环,依次处理每个事件。处理事件\({p_0}\)\({p_0}\)\(\overline {{p_0}{q_0}} \)的左端点,把\(\overline {{p_0}{q_0}} \)插入\(SL\),此时\(SL = \{ \overline {{p_0}{q_0}} \} \);处理事件\({p_1}\)\({p_1}\)\(\overline {{p_1}{q_1}} \)的左端点,把\(\overline {{p_1}{q_1}} \)插入\(SL\)\(SL = \{ \overline {{p_1}{q_1}} ,\overline {{p_0}{q_0}} \} \)\(\overline {{p_0}{q_0}} \)\(\overline {{p_1}{q_1}} \)相邻且位于其上方,易知\(\overline {{p_0}{q_0}} \)\(\overline {{p_1}{q_1}} \)不相交,算法继续;处理事件\({p_2}\),与事件\({p_1}\)的情况类似,此时\(SL = \{ \overline {{p_2}{q_2}} ,\overline {{p_1}{q_1}} ,\overline {{p_0}{q_0}} \} \);处理事件\({q_0}\)\({q_0}\)\(\overline {{p_0}{q_0}} \)的右端点,和\(\overline {{p_1}{q_1}} \)相邻且位于下方的线段存在,但位于上方的线段不存在,不作相交检测,将\(SL\)中的线段\(\overline {{p_0}{q_0}} \)删除,\(SL = \{ \overline {{p_2}{q_2}} ,\overline {{p_1}{q_1}} \} \);处理事件\({p_3}\)\({p_3}\)\(\overline {{p_3}{q_3}} \)的左端点,把\(\overline {{p_3}{q_3}} \)插入\(SL\)\(SL = \{ \overline {{p_3}{q_3}} ,\overline {{p_2}{q_2}} ,\overline {{p_1}{q_1}} \} \)\(\overline {{p_2}{q_2}} \)\(\overline {{p_3}{q_3}} \)相邻且位于上方,检测出线段\(\overline {{p_2}{q_2}} \)\(\overline {{p_3}{q_3}} \)相交,算法结束。

2015-3-22 23-06-52

图3.25 算法正确性证明

最后,证明上述算法的正确性。

证明:设线段\(A\)\(B\)相交于一个点\(Q\)\(Q\)是位于最左的交点(若在同一条扫描线上有多个交点,\(Q\)是最下方的交点),如图3.25所示。在\(Q\)之前的线段只有插入和删除操作,只是\(SL\)内的元素发生变化,并没有发生任何相交。由于\(A\)\(B\)发生相交,一定存在一条扫描线,使得在扫描线结构\(SL\)内的线段\(A\)\(B\)一定相邻,现在考虑什么时候线段\(A\)\(B\)会相邻:

(1)线段\(A\)或者\(B\)在插入\(SL\)时,另一条线段正好位于它的above或below。以图3.25(a)所示为例,处理事件\(A\)的左端点,把\(A\)插入\(SL\),此时\(B\)正好位于\(A\)的below,这种情况会在算法的第6~13步的第1个if块内得到判定;

(2)线段\(A\)\(B\)已经在\(SL\)内,当它们之间有线段被删除后,使得\(A\)\(B\)连续。以图3.25(b)所示为例,在处理线段\(A\)\(B\)的左端点事件,把\(A\)\(B\)插入\(SL\)\(A\)\(B\)仍然不相邻,那么在\(A\)\(B\)之间夹角着一条线段,设为\(C\),在处理\(C\)的右端点事件,把\(C\)\(SL\)中删除后,可以得到\(C\)上方的线段\(A\)和下方的线段\(B\)相邻,这种情况会在算法第15~20步的第2块if块内得到判定。

在Shamos-Hoey算法中,这两种情况都能被检测到,因此相交的情况一定会被检测到,算法正确性得证。上述算法正确的精髓就在于:若两条线段相交,那么一定存在一条扫描线使得它们在扫描线结构\(SL\)内一定相邻。

算法伪码第1步,对\(2n\)个顶点的排序,需要时间\(O(n\log n)\);因为\(SL\)是一个平衡二叉树,所以线段的插入、删除、查询操作的时间为\(O(\log n)\),对\(2n\)顶点的处理时间为\(O(n\log n)\)。因此,Shamos-Hoey算法的时间复杂度为\(O(n\log n)\)

3.7.3. Bentley-Ottmann算法

问题描述:给定线段集合\(S = \{ {L_i}\} ,0 \le i \prec n\),输出由线段集\(S\)中的所有交点构成的集合\(I = \left\{ {{I_j}} \right\},0 \le j \prec k\)

为了简化对Bentley-Ottmann基本思想的描述,暂时不考虑多条线段相交于一点、存在垂直线段和线段发生重合的情况。

2015-3-22 23-07-03

图3.26 Bentley-Ottmann算法的基本思想

Bentley-Ottmann算法是对Shamos-Hoey算法的扩展,所以它也是基于事件,构造虚拟的扫描线,从左到右扫描,直至找到所有交点为止。这里的事件包括两类:1)线段的端点;2)线段与线段的交点,分别称为端点事件和相交事件。需要扫描线结构\(SL\)来存储线段,除了插入、删除、查询操作外,还需要添加一个交换两个相邻线段位置的操作,即\(SL.swap(A,B)\),交换\(SL\)中相邻两条线段\(A\)\(B\)的位置。因此,相同的线段,在不同的扫描线上的顺序可能会不同。如图3.26所示,在经过事件\({p_2}\)的扫描线上,三条线段的顺序大小是\(\overline {{p_2}{q_2}} \prec \overline {{p_0}{q_0}} \prec \overline {{p_1}{q_1}} \),但是对于经过事件\({I_0}\)的扫描线上,三条线段的大小关系\(\overline {{p_2}{q_2}} \prec \overline {{p_1}{q_1}} \prec \overline {{p_0}{q_0}} \)

在Bentley-Ottmann算法中,需要维护一个有序的事件队列(Event Queue),简称为\(EQ\)\(EQ\)中的事件按照\(x,y\)的字典序从左往右排序。定义事件的对比方法,给定两个事件\(p,q\)\(p \prec q\)当且仅当\(\left( {{p_x} \prec {q_x}} \right) \vee \left( {{p_x} = {q_x} \wedge {p_y} \prec {q_y}} \right)\)。初始的事件队列\(EQ\)是所有线段的端点,事件队列可以用堆数据结构来设计,对事件队列共有三种操作:

  1. \(EQ.top()\),获取事件队列\(EQ\)首部的事件;
  2. \(EQ.pop()\),删除事件队列\(EQ\)首部的事件;
  3. \(EQ.push(event)\),把事件\(event\)插入事件队列\(EQ\)中。

采用堆数据结构设计的事件队列的\(top()\)操作仅需\(O(1)\)的时间,\(pop()\)\(push()\)操作需\(O(\log m)\)的时间,\(m\)表示事件队列中的元素个数。

由Shamos-Hoey算法可以得到一条结论:如果两条线段相交,那么一定存在一条扫描线使得它们在扫描线结构\(SL\)内相邻。这条结论也是Bentley-Ottmann算法的核心思想,设\(A\)\(B\)相交,只要检测出它们在扫描线结构\(SL\)内相邻的所有情况,就可以检测到它们的相交,主要对下面三种情况进行相交测试:

  1. 若事件\(E\)是线段\(L\)的左端点,在\(SL.insert(L)\)操作后,检测\(SL.above(L)\)\(SL.{\mathop{\rm below}\nolimits} (L)\)是否分别与线段\(L\)相交;
  2. 若事件\(E\)是线段\(L\)的右端点,在\(SL.{\mathop{\rm delete}\nolimits} (L)\)操作前,检测\(SL.above(L)\)\(SL.{\mathop{\rm below}\nolimits} (L)\)是否相交;
  3. 若事件\(E\)是相交事件,线段\(A\)\(B\)相交于点\(E\)\(A\)位于\(B\)的上方,则交换线段\(A\)\(B\)\(SL\)里的位置,即\(SL.swap(A,B)\)操作,再分别检测\(SL.above(B)\)\(B\)\(SL.{\mathop{\rm below}\nolimits} (A)\)\(A\)是否相交。

Bentley-Ottmann算法的伪码如下所示:

给定线段集\(S = \{ {L_i}\} ,0 \le i \prec n\),输出由\(S\)中的所有交点构成的集合\(I = \left\{ {{I_j}} \right\},0 \le j \prec k\)
\({\mathop{\rm Bentley}\nolimits} \_Ottmann(S,I)\)
1.    初始化\(EQ\)为线段集\(S\)所有线段的端点,元素按照\(x,y\)的字典序从左往右排序;
2.    \(I = \emptyset \);
3.    while(\(EQ\)非空 ) then
4.           \(P = EQ.top()\);
5.           \(EQ.{\mathop{\rm pop}\nolimits} ()\);
6.           if \(P\)是线段\(L\)的左端点, then
7.                  \(SL.insert(L)\);
8.                  \(A = SL.above(L)\);
9.                  \(B = SL.below(L)\);
10.                 if (\(A\)存在) &&(\(A\)\(L\)相交于\(Q\)), then
11.                        \(I = I \cup \{ Q\} \);
12.                        \(EQ.push(Q)\);
13.                 end if;
14.                 if (\(B\)存在)&&( \(B\)\(L\)相交于\(Q\)), then
15.                        \(I = I \cup \{ Q\} \);
16.                        \(EQ.push(Q)\);
17.                 end if;
18.          else if\(P\)是线段\(L\)的右端点, then
19.                 \(A = SL.above(L)\);
20.                 \(B = SL.below(L)\);
21.                 if (\(A\)存在)&&( \(B\)存在)&&( \(A\)\(B\)相交于\(Q\)), then
22.                               \(I = I \cup \{ Q\} \);
23.                               \(EQ.push(Q)\);
24.                 end if;
25.                 \(SL.delete(L)\);
26.          else                                           //设线段\(A\)\(B\)相交于点\(P\)\(A\)位于\(B\)的上方
27.                 \(SL.swap(A,B)\);
28.                 \(B' = SL.above(B)\);
29.                 \(A' = SL.below(A)\);
30.                 if (\(A'\)存在)&&( \(A'\)\(A\)相交于\(Q\)), then
31.                               \(I = I \cup \{ Q\} \);
32.                               \(EQ.{\mathop{\rm push}\nolimits} (Q)\);
33.                 end if;
34.                 if (\(B'\)存在)&&( \(B'\)\(B\)相交于\(Q\)), then
35.                               \(I = I \cup \{ Q\} \);
36.                               \(EQ.{\mathop{\rm push}\nolimits} (Q)\);
37.                 end if;
38.          end if;
39.   end while;

以图3.26所示为例,介绍Bentley-Ottmann算法的基本过程,首先,初始化事件队列\(EQ\)为所有线段的端点,即\(EQ = \left\{ {{p_0},{p_1},{p_2},{q_0},{q_2},{q_1}} \right\}\)。接着,进入while循环,处理事件队列中的每一个事件。从\(EQ\)中取出事件\({p_0}\)并将它从\(EQ\)中删除,它是\(\overline {{p_0}{q_0}} \)的左端点,进入算法第7~13步,把\(\overline {{p_0}{q_0}} \)插入\(SL\)\(SL = \{ \overline {{p_0}{q_0}} \} \),未检测出相交点, ;从\(EQ\)中取出事件\({p_1}\)并将它从\(EQ\)中删除,它是\(\overline {{p_1}{q_1}} \)的左端点,进入算法第7~13步,把\(\overline {{p_1}{q_1}} \)插入\(SL\)\(SL = \{ \overline {{p_0}{q_0}} ,\overline {{p_1}{q_1}} \} \),检测到线段\(\overline {{p_1}{q_1}} \)\(SL.below(\overline {{p_1}{q_1}} )\)相交于点\({I_0}\),把相交事件\({I_0}\)插入到事件队列中,\(EQ = \left\{ {{p_2},{I_0},{q_0},{q_2},{q_1}} \right\}\);处理事件\({p_2}\),它是\(\overline {{p_2}{q_2}} \)的左端点,进入算法第7~13步,把\(\overline {{p_2}{q_2}} \)插入\(SL\)\(SL = \{ \overline {{p_2}{q_2}} ,\overline {{p_0}{q_0}} ,\overline {{p_1}{q_1}} \} \)\(\overline {{p_2}{q_2}} \)\(SL.above(\overline {{p_2}{q_2}} )\)不相交,\(EQ = \left\{ {{I_0},{q_0},{q_2},{q_1}} \right\}\);处理相交事件\({I_0}\),进入算法第23~33步,\(\overline {{p_0}{q_0}} \)\(\overline {{p_1}{q_1}} \)相交于点\({I_0}\)\(SL.swap(\overline {{p_0}{q_0}} ,\overline {{p_1}{q_1}} )\),有\(SL = \{ \overline {{p_2}{q_2}} ,\overline {{p_1}{q_1}} ,\overline {{p_0}{q_0}} \} \),此时\(\overline {{p_0}{q_0}} \)\(\overline {{p_1}{q_1}} \)上方,\(\overline {{p_1}{q_1}} \)\(SL.below(\overline {{p_1}{q_1}} )\)相交于点\({I_1}\),把相交事件\({I_1}\)插入到事件队列中,\(EQ = \left\{ {{I_1},{q_0},{q_2},{q_1}} \right\}\)。依此类推,直至\(EQ\)为空,算法结束。

上述伪码描述了Bentley-Ottmann算法的基本过程,但是没有考虑多条线段相交于同一个点、存在垂直线段、存在线段重合这三种退化情况,算法需要\(O(n\log n + k\log n)\)的时间和\(O(n)\)的空间,其中\(n\)表示线段的个数,\(k\)表示交点的个数。

de Berg[20]描述了另外一种Bentley-Ottmann算法的实现,Cagne[19]也提供了该算法的C++实现。接下来介绍如何实现Bentley-Ottmann算法,这里考虑多条线段相交于一个点、存在垂直线段的情况,但是不考虑线段重合的情况。

每个事件\(E\)必需与一个线段集\(LS\)(Left Set)绑定,线段集\(LS\)存储着以点\(E\)为左端点的线段,因为算法需要快速获取与给定事件相关联的线段,而且可能多条线段经过同一个点。事件队列\(EQ\)可以采用堆或者平衡二叉树来实现,若采用堆来实现,则把事件和它的\(LS\)存放在同一个结构体内;若采用平衡二叉树来实现,则把事件作为关键字(Key),而它的\(LS\)作为值(Value)存放在二叉树中。对事件队列\(EQ\)的操作有下面5种,方法1、2、3的算法复杂度都是\(O(\log m)\),方法4、5的复杂度为\(O(\log 1)\),其中\(m\)表示事件队列的事件个数:

  1. \(EQ.{\mathop{\rm lpush}\nolimits} (E,L)\):若\(EQ\)中不存在事件\(E\),把\(E\)插入\(EQ\),且把线段\(L\)加入事件\(E\)对应的线段集 内;否则,把线段\(L\)加入事件 对应的线段集\(LS\)内;
  2. \(EQ.{\mathop{\rm rpush}\nolimits} (E)\):若\(EQ\)中不存在事件\(E\),把\(E\)插入\(EQ\);否则,直接返回;
  3. \(EQ.{\mathop{\rm pop}\nolimits} ()\):移除\(EQ\)中位于首部的事件;
  4. \(EQ.{\mathop{\rm top}\nolimits} ()\):返回\(EQ\)中位于首部的事件;
  5. \(EQ.{\mathop{\rm findls}\nolimits} (E)\):返回事件\(E\)对应的线段集\(LS\)

2015-3-22 23-07-19

图3.27 线段的上下关系

接着,考虑扫描线结构\(SL\)的设计和实现,\(SL\)用于存储线段并且保证线段的大小关系,在前面已经阐述了线段大小的概念。可以采用平衡二叉树来设计\(SL\),叶节点存储着线段,内节点存储引导搜索指定叶节点的信息。如何实现线段大小关系的对比呢?线段的大小关系是相对于给定的扫描线,而扫描线又是基于当前事件,设当前处理的事件是\(w\),如图3.27所示(a)所示,当\(x = {w_x}\)时,设点\(({w_x},{a_y}),({w_x},{b_y})\)分别在线段\({L_1},{L_2}\)上,显然有\({b_y} \prec {a_y}\),所以\({L_2} \prec {L_1}\);如图(b)所示,当两条线段都经过点\(w\),则通过线段的斜率来作为线段大小关系的判定,显然线段\({L_2}\)的斜率比\({L_1}\)小,所以有\({L_2} \prec {L_1}\));如图(c)所示,当存在线段是垂直方向,那么它的斜率等于正无穷大,点\(w\)在线段\({L_2}\)上但位于线段\({L_1}\)下方,所以有\({L_2} \prec {L_1}\),注意,若此时当前事件\(w\)位于线段\({L_1}\),那么\({L_2}\)一定已从\(SL\)中移除,不存在对比\({L_1},{L_2}\)大小关系的问题。在给定事件\(w\),判断两条线段的大小关系的伪码如下所示:

\({\mathop{\rm COMPARE}\nolimits} ({L_1},{L_2},w)\)
/*在给定事件\(w\),对比两条线段\({L_1},{L_2}\)的大小关系,\({L_1},{L_2}\)表示线段, \(w\)表示事件 */
1.    \({h_1} = {\mathop{\rm HEIGHT}\nolimits} ({L_1},w)\);
2.    \({h_2} = {\mathop{\rm HEIGHT}\nolimits} ({L_2},w)\);
3.    if \({h_1} = = {h_2}\), then
4.           return\({\mathop{\rm COMPARE}\nolimits} \_SLOPE({L_1},{L_2})\);
5.    else
6.           return\({h_1} \prec {h_2}\);
7.    end if;
\({\mathop{\rm HEIGHT}\nolimits} (L,w)\))
/*\(L\)表示线段,\(w\)表示点,其中线段\(L\)的左端点为\(p\),右端点为\(q\)*/
1.    if \({p_x} = = {q_x}\), then
2.           if\({w_y} \prec {p_y}\), then
3.                  return \({p_y}\);
4.           else if\({w_y} \succ {q_y}\), then
5.                  return\({q_y}\);
6.           else
7.                  return\({w_y}\);
8.    else
9.           return\(\left( {{q_y} - {p_y}} \right) \cdot \left( {{w_x} - {p_x}} \right)/\left( {{q_x} - {p_x}} \right) + {p_y}\);
10.   end if;
\({\mathop{\rm COMPARE}\nolimits} \_SLOPE({L_1},{L_2})\)
/*\({L_1},{L_2}\)表示线段 */
1.    if\({p_{1,x}} = = {q_{1,x}}\), then
2.           \(typ{e_1} = {\rm{infinity}}\);
3.    else
4.           \({k_1} = \left( {{q_{1,y}} - {p_{1,y}}} \right)/\left( {{q_{1,x}} - {p_{1,x}}} \right)\);
5.    end if;
6.    if\({p_{2,x}} = = {q_{2,x}}\), then
7.           \(typ{e_2} = {\rm{infinity}}\);
8.    else
9.           \({k_2} = \left( {{q_{2,y}} - {p_{2,y}}} \right)/\left( {{q_{2,x}} - {p_{2,x}}} \right)\);
10.   end if;
11.   if\(typ{e_1} = = {\rm{infinity}}\), then
12.          return FALSE;
13.   else
14.          return (\(typ{e_2} = = {\rm{infinity}}\))||(\({k_1} \prec {k_2}\));
15.   end if;

扫描线结构\(SL\)是基于平衡二叉树来实现,如果采用衡二叉树模板来实现\(SL\),例如C++的STL,往往没有提供\(SL.swap()\)操作方法。这里,我们可以采用一种取巧的方法:把扫描线结构\(SL\)绑定一个事件\(W\),采用函数\({\mathop{\rm COMPARE}\nolimits} ({L_1},{L_2},W)\)对比线段与线段的大小关系,设当前事件\(E\)是相交事件,线段\(A\)\(B\)相交于点\(E\),那么把线段\(A\)\(B\)\(SL\)中删除,即\(SL.{\mathop{\rm erase}\nolimits} (A),SL.{\mathop{\rm erase}\nolimits} (B)\),更新\(SL\)绑定的事件\(W = E\),再把\(A\)\(B\)插入\(SL\)中,这样就实现了\(A\)\(B\)在扫描线结构\(SL\)内顺序的互换。

Bentley-Ottmann算法的实现伪码[20]如下所示:

给定线段集合\(S = \{ {L_i}\} ,0 \le i \prec n\),输出线段集合\(S\)中的所有交点集合\(I = \left\{ {{I_j}} \right\},0 \le j \prec k\)
\({\mathop{\rm Bentley}\nolimits} \_Ottmann(S,I)\)
1.    \(EQ = \emptyset ,I = \emptyset \);
2.    for each segment \(L\) in \(S\) do               //\(p,q\)分别是线段\(L\)的左端点和右端点
3.           \(EQ.lpush(p,L)\);
4.           \(EQ.{\mathop{\rm rpush}\nolimits} (q)\);
5.    end for;
6.    \(W = (0,0)\);                                    //扫描线结构中存储的线段是基于事件\(W\)排序的
7.    将\(SL\)初始化为空,并与事件\(W\)绑定;
8.    while(\(EQ \ne \emptyset \)) then
9.           \(T = W\);                                         //备份事件\(W\)
10.          \(E = EQ.top()\);
11.          \(EQ.{\mathop{\rm pop}\nolimits} ()\);
12.          \(LS = EQ.{\mathop{\rm findls}\nolimits} (E)\);
13.          \(W = ({E_x},{E_y})\);
14.          设\(IS\)是由包含点\(E\)(不包括点\(E\)作为线段的端点)的线段构成的集合,\(RS\)由以点\(E\)为右端点的线段构成的集合
15.          if 集合\(LS \cup IS \cup RS\)中的元素个数大于1, then
16.                 \(I = I \cup \left\{ E \right\}\);                           //多条线段经过同一个点
17.          end if;
18.          \(W = T\);
19.          \(SL.{\mathop{\rm erase}\nolimits} (IS \cup RS)\);
20.          \(W = E\);
21.          \(SL.{\mathop{\rm insert}\nolimits} (LS \cup IS)\);
22.          if\(LS \cup IS = = \emptyset \), then
23.                 从\(SL\)中找到与\(E\)相邻的两条线段\(A,B\);
24.                 \(FIND\_NEW\_EVENT(A,B,E)\);
25.          else
26.                 从\(LS \cup IS\)中分别找到最小和最大的线段\(A,B\);
27.                 \(A' = SL.below(A)\);
28.                 \(B' = SL.above(B)\);
29.                 \(FIND\_NEW\_EVENT(A,A',E)\);
30.                 \(FIND\_NEW\_EVENT(B,B',E)\);
31.          end if;
32.   end while;
\(FIND\_NEW\_EVENT(A,B,E)\)
1.    if (\(A\)有效)&&( \(B\)有效)&& \(A,B\)相交于点\(p\), then
2.           if (\(p \succ E\))&&(\(EQ\)中不存在\(p\)), then
3.                  \(EQ.{\mathop{\rm rpush}\nolimits} (p)\);
4.           end if;
5.    end if;

算法第13~14步,在扫描线结构\(SL\)中包含点\(E\)或者以\(E\)为右端点的线段是连续的,因此这一步可以在时间\(O(\log n)\)内完成;第18~19步,由于往\(SL\)插入线段集\(LS \cup IS\)时是基于前一个扫描点\(T\),因此移除时为了保证线段的大小关系,也必需基于\(T\);第20~21步,基于新的扫描点\(E\),插入线段集\(IS \cup RS\),能够使得发生相交的线段维持正确的顺序。

2015-3-22 23-07-35

图3.28 Bentley-Ottmann算法的基本过程

举个例子来解释上述Bentley-Ottmann算法的基本过程,如图3.28所示,其中线段集\(S\)由线段\({L_i}(0 \le i \le 6)\)构成,\({P_j}(0 \le j \le 7)\)作为线段的端点,\({I_k}(0 \le k \le 4)\)是线段之间的交点,其中,\({I_0} = (2.4,3.2),{I_1} = (3.4,4.1),{I_2} = (3.9,5.2),{I_3} = (4.1,5.8),{I_4} = (6,6.4)\)(浮点数保留小数点后1位)。初始阶段,\(EQ = \left\{ {{P_0},{P_1},{P_2},{P_3},{P_4},{P_5},{P_6}} \right\},SL = \emptyset \);进入while循环,开始第1步迭代,处理事件\(E = {P_0}\),此时\(EQ = \left\{ {{P_1},{P_2},{P_3},{P_4},{P_5},{P_6}} \right\},LS = \left\{ {{L_0}} \right\},IS = \emptyset ,RS = \emptyset \),再经过算法第15~31步处理后,\(SL = \left\{ {{L_0}} \right\},I = \emptyset \)\(EQ\)保持不变;接着,第2步迭代,处理事件\(E = {P_1}\),此时\(EQ = \left\{ {{P_2},{P_3},{P_4},{P_5},{P_6}} \right\},LS = \left\{ {{L_0},{L_1},{L_2}} \right\},IS = \emptyset ,RS = \emptyset \),再经过算法第15~31步处理后,\(SL = \left\{ {{L_0},{L_1},{L_2}} \right\},I = \left\{ {{P_1},{I_0}} \right\}\),由于在第30步找到交点\({I_0}\),把交点\({I_0}\)插入事件队列\(EQ\)中,使得\(EQ = \left\{ {{I_0},{P_2},{P_3},{P_4},{P_5},{P_6}} \right\}\);依次类推,每步迭代的\(LS,IS,RS\)以及迭代完成后的\(EQ,SL,I\)中的数据都会在下面的表中显示出,算法直至\(EQ\)为空时结束,由线段集\(S\)中所有交点构成的集合表示为\(I = \sum\limits_{k = 1}^m {{Q_k}} \),其中\(m\)表示算法迭代的次数。

表3.1 Bentley-Ottmann算法过程中变量的数据

2015-3-22 23-08-46

spacer

Leave a reply