2011算法第十六、十七講 幾何掃描

ECNUYinpingLiu幾何掃描柳銀萍ECNUYinpingLiu幾何算法中，考慮的主要對象通常是二維、三維和更高維空間中的點、線段、多邊形和其他幾何體。有時候一個問題的解法要求“掃描”給出的輸入對象來收集信息以找到可行解。這種技術在二維平面稱為平面掃描，在三維空間稱為空間掃描。在它的簡單形式中，一條垂直的直線在平面中從左到右掃描，在每個對象(比如說一點)處逗留，從最左的對象開始直到最右的對象。我們結合計算幾何中的一個簡單問題來闡明這種方法。ECNUYinpingLiu定義18-1

設P1=(x1，y1，)和P2=(x2，y2)是平面中的兩點，如果x1≤x2并且y1≤y2,，則稱P2支配P1，記為Pl<P2。定義18-2

設S是平面中的一個點集，點p∈S是極大點或最大點，如果不存在點q∈S，使得p≠q并且p<q。求極大點的問題有一個簡單的算法，它是幾何掃描算法的一個很好的例子。

MAXIMALPOINTS：在平面上給定一個

n個點的集合S，確定S中的極大點。

ECNUYinpingLiu求解這個問題很容易，方法如下:

首先，我們把S中的所有點按照它們x坐標的非升序排列，最右點(有最大x值的那點)無疑是個極大點。算法從右到左掃描這些點，同時確定它是否在y坐標上被先前掃描過的任何點所支配。這個算法在下面的算法MAXIMA中給出。ECNUYinpingLiu算法18.1MAXIMA

輸入：平面上n個點的集合S。

輸出：S中極大點集合M。

1．設A為S中按

x坐標非升序排列的點的集合。如果兩個點有相同的

x

坐標，則有較大

y

坐標值的點出現(xiàn)在集合的前面

2．M←{A[1]}

3．maxy

←A[1]的

y

坐標值ECNUYinpingLiu

4．forj←2ton5．(x，y)←A[j]6．ify>maxythen7．M=MU{A[j]}8．

maxy←y9．endifendforECNUYinpingLiu圖18.1展示了算法在一個點集上的狀態(tài)。如圖所示，極大點集合{a,b,c,d}形成一個階梯。作為一個例子，請注意e

僅由a支配，而f由a和b

支配，g

僅由c

支配。很容易看出算法MAXIMA的運行時間主要由排序步驟決定，因此是O(nlogn)。上述的例子展示了平面掃描算法的兩個基本組成部分。首先，有一個事件點進度表，它是一個x坐標自右向左排序的序列，這些點定義了掃描線將會“逗留”的位置，在這里掃描線是垂直線。ECNUYinpingLiu在某些平面掃描算法中情況可能與前面的例子不同，它們的事件點進度表可能需要動態(tài)更新.并且,為了得到高效的實現(xiàn),可能需要比簡單的數(shù)組和隊列更復雜的數(shù)據(jù)結構.平面掃描方法中的其他部分是掃描線狀態(tài)，這是掃描線上幾何對象的適當描述。在上述例子中，掃描線狀態(tài)由最新探測到的極大點的“描述”組成。這個描述僅僅是它的y坐標的值。在其他的幾何算法中，掃描線狀態(tài)可能需要以棧、隊列或堆等形式存儲所需要的相關信息。ECNUYinpingLiu2.幾何預備知識

在本節(jié)中，我們介紹本章中將要用到的計算幾何中一些基本概念的定義。這些定義大多是在二維空間的框架之內(nèi)，它們可以很容易地推廣到更高維空間中。一個點p由一對坐標(x，y)表示，一條線段由它的兩個端點表示。如果p和q是兩個不同點，我們用記端點為p和q的線段。一條折線路徑∏是點p1，p2，…，pn的一個序列，使得是線段，1≤i≤n-1，如果p1=pn，我們稱∏(包括以∏為界的封閉區(qū)域)是一個多邊形。在這種情況下,點pi,1≤i≤n，稱為多邊形的頂點，而線段

,,…，

:稱為邊。ECNUYinpingLiu我們可以很方便地用一個存儲了各個頂點的環(huán)形鏈表來表示一個多邊形。在一些算法中，它用環(huán)形雙向鏈表表示。如果一個多邊形P的任意兩條邊除了在頂點處外均不相交，那么稱P是簡單的；否則它是非簡單的。圖18.2顯示了兩個多邊形，一個是簡單的，另一個不是。圖18.2(a)簡單多邊形(b)非簡單多邊形圖18.3(a)凸多邊形(b)非凸多邊形ECNUYinpingLiu從現(xiàn)在開始，除非特別加以說明，否則我們始終假設多邊形是簡單的。對于一個多邊形P，如果連接P中任意兩點的線段全部在P中，我們說P是凸的。圖18.3

顯示兩個多邊形，一個是凸的，另一個不是。設S是平面上的一個點集，我們定義包含了S中所有頂點的最小凸多邊形為S的凸包，記做CH(S)。CH(S)的頂點稱為包頂點，有時也稱為S的極點。設u=(x1，y1)，v=(x2，y2)

和w=(x3,y3)，由這三點形成的三角形帶符號面積是下面行列式的一半。ECNUYinpingLiu如果“u,v,w,u”構成一個逆時針回路，則D是正的。在這種情況下，我們說路徑u,v,w

構成一個左旋。如果u,v,w,u

形成順時針回路,則它是負的，在這種情況下，我們說路徑u,v,w

構成一個右旋(見圖18.4)。D=0當且僅當三點共線，即三點在同一直線上。ECNUYinpingLiu圖18.4(a)左旋(b)右旋ECNUYinpingLiu3.計算線段的交點

在這一節(jié)，我們考慮以下問題。給出平面上n條線段的集合L={l1,l2,…ln}，找出交點的集合。我們將假設沒有垂直線段，沒有三條線段交于同一點。如果沒有這些假設，則只會使算法變得更復雜。設

li

和

lj

是L中的任意兩條線段，如果

li

與

lj

分別和橫坐標為

x的垂直線交于點

pi和

pj

那么，倘若在橫坐標為

x的垂線上點

pi在

pj

的上方，我們就說

li

在

lj

的上方，表示為

li

>x

lj，關系

>x

定義了所有與具有橫坐標為x的垂線相交的線段集的全序。于是，在圖18.5中，我們有:l2>xll，l2>xl3，l3>yl2

和

l4>zl3ECNUYinpingLiu圖18.5關系>x

的說明算法首先將n條線段的2n個端點按它們橫坐標的非降序進行排列。在算法執(zhí)行過程中，一條垂直線從左到右掃描所有線段的端點和它們間的交點。它從空的關系開始，每遇到一個端點或一個交點，就改變序關系。具體地說，當線從左到右掃描時，只要出現(xiàn)如下事件之一，序關系就改變。ECNUYinpingLiu

(1)遇到線段的左端點時；

(2)遇到線段的右端點時；

(3)遇到兩條線段的交點時。掃描線的狀態(tài)完全由序關系>x描繪，至于事件點的進度表E，它包括這些線段已排序的端點加上它們的交點，這些交點是在線從左到右掃描時動態(tài)地添加進去的。算法在每種事件上所做的動作如下:(1)當遇到線段l的左端點時，l被加到序關系中。如果有一條線段l1，緊接在l上面同時l1和l相交，則它們的交點將被插入到事件點進度表E中去。類似地，如果存在線段l2緊接在l下面同時l2和l相交則它們的交點也將被插入到E中去。ECNUYinpingLiu(2)當遇到線段l的右端點p時，算法把l從序關系中移去。在這種情況中，算法會測試緊接在l上下的線段l1和l2，看它們是否可能1在p的右側一點q處相交。如果出現(xiàn)種情況，口會被插人到E中去.(3)當遇到兩條線段的交點時，它們在關系中的相對次序被翻轉。這樣，如果在它們的交點左邊有l(wèi)1>xl2，那么序關系要修改為l2>xl1。設l3和l4是緊接在交點p的上面和下面的兩條線段(見圖18.6)，換句話說，對于交點右面l3在l2上面而l4在l1

的下面(見圖18.6)。在這種情況下，我們檢查l2與l3和l1與l4相交的可能性。像前面一樣，如果存在交點，就把它們插入E中。ECNUYinpingLiu圖18.6在交點處翻轉兩條線段的次序事件點進度表和掃描線的狀態(tài)所需的數(shù)據(jù)結構:

為了實現(xiàn)事件點進度表E，我們需要一個支持以下運算的數(shù)據(jù)結構:

·insert(p，E)：把點p插入到E中；

·delete-min(E)：返回具有最小z坐標的點并把它從E中刪除.ECNUYinpingLiu堆這種數(shù)據(jù)結構顯然能夠在時間O(1ogn)內(nèi)支持這兩種運算。于是，E由堆實現(xiàn)，初始時它包含2n個已排序的點。每次掃描線向右移動，橫坐標最小的點被取出，像上面說明的那樣，當算法探測到一個交點p時，把p插入E。掃描線的狀態(tài)S必須支持以下的運算:

·insert(l，S)：把線段l插入到S中；

·delete(l，S)：從S中刪除線段l；

·above(l，S)：返回緊接在l上方的線段；

·below(l，S)：返回緊接在l下方的線段。ECNUYinpingLiu一種通常稱為字典的數(shù)據(jù)結構在O(logn)時間內(nèi)支持上面的每個運算。注意阿above(l,s)

或below(l,s)可能不存在，我們需要一個簡單的測試(它沒包含在算法中)來處理這兩種情況。關于這一算法，一個更精確的描述在算法INTERSECTIONSLS中給出。在算法中，過程process(p)把p插入E中并輸出p。

算法18.2:INTERSECTIONLS

輸入：平面上n個線段集L={l1,l2,···,ln}。

輸出：L中線段的交點。ECNUYinpingLiu1.按橫坐標的非降序排列端點，將它們插入堆E中(事件點進度表)2.whileE非空3.p←delete-min(E)4.ifp是左端點then5.設l是左端點為p的線段6.insert(l，S)7.l1above(l，S)8.l2below(l，S)9.ifl與l1在點q1相交thenprocess(q1)10.ifl與l2在點q2相交thenprocess(q2)ECNUYinpingLiu11.elseifp是右端點

then12.設l是右端點為p的線段13.l1←above(l,S)14.l2←below(l,S)15.

delete(l,S)16.

ifl1與

l2在

p的右邊點

q相交

thenprocess(q)17.else{p是相交點}18.設在p點相交的線段為l1和l219.其中l(wèi)1在p的左邊位于l2上方20.l3←above(l1,S){在p的左邊}21.l4←below(l2,S){在p的左邊}ECNUYinpingLiu22.ifl2與l3在q1相交thenprocess(q1)23.ifl1與l4在q2相交thenprocess(q2)24.在S中交換l1和l2的秩序25.endif26.endwhileECNUYinpingLiu排序步驟要耗費O(nlogn)時間，設交點數(shù)是m，那么有2n+m個事件點要處理，每一點需要O(1og(2n+m))處理時間，因此，算法處理所有交點的總時間是O((2n+m)log(2n+m))。因為m≤n(n-1)/2=O(n2)，階就變成O((n+m)1ogn)。由于找出全部交點用樸素的方法要運行O(n2時間，因此這算法不適合于處理交點數(shù)目預計為

O(n2/logn)線段集合。另一方面，如果m=O(n)，則算法需要

O(n1ogn)

時間。算法的時間復雜度：ECNUYinpingLiu4.凸包問題

本節(jié)我們考察也許是計算幾何中最基本的問題：在平面中給出n個點的集合S，尋找S的凸包CH(S)。我們在這里敘述一個著名的被稱為“Graham掃描”的幾何掃描算法。在它的簡單形式中，Graham掃描使用以某一點為中心的掃描線，它旋轉掃描線使之掃過整個平面，并在每一點逗留以決定這一點是否將被包括到凸包中。首先,算法在點表上做一次掃描，找出具有最小y坐標的點，記做p0,如果有兩個或更多的點具有最小y坐標，就選最右的一個為p0

。很明顯，p0屬于凸包。ECNUYinpingLiu接著，所有點的坐標被轉換為以p0為原點的坐標，于是在S-{p0}中的點按照原點p0的極角排序，如果兩點pi和pj與p0形成同樣的極角，則更靠近p0的那一點排在前面。注意，在此我們無需計算從原點起的真實距離，因為包括開方計算，計算它是耗費很大的；這里我們只需要比較距離平方。設排序之后的表是T={p0，p1，…，pn-1}，其中p1

和pn-1分別與p0形成了最小和最大的極角。圖18.7顯示了一個按照關于p0的極角排序的13個點集合的例子。ECNUYinpingLiu現(xiàn)在，對事件點的進度表，即排序表T開始掃描，掃描線的狀態(tài)用一個棧St

實現(xiàn)。棧初始時包含(pn-1，p0)，p0在棧頂。然后算法周游各點，從p1

開始到pn-1終止，在任何時刻，設棧的內(nèi)容是

St=(pn-1，p0，…，pi，pj)(pi和pj是最后壓人的點)，并設pk是下一個考慮的點。如果三元組pi，pj，pk形成一個左旋，則pk壓人棧頂，同時掃描線移到下一個點；如果三元組pi，pj，pk

形成一個右旋或三點共線，則pj彈出棧，同時掃描線繼續(xù)留在pk。圖18．8顯示了在剛好處理完p5

后導出的凸包。這時，棧的內(nèi)容是(p12，p0，p1，p3，p4，p5)ECNUYinpingLiu圖18.8處理點p5后的凸包圖18.9處理點p6后的凸包在處理點p6之后，點p5，p4

和p3

相繼彈出棧，同時點p6壓入棧頂(見圖18.9)。最終的凸包在圖18.10中顯示。ECNUYinpingLiu圖18.10最終的凸包下面給出算法更形式的描述。在算法結束時，棧St

包含CH(S)的頂點，于是它可以轉化到鏈表中形成一個凸多邊形。算法18.3CONVEXHULL

輸入：平面上n個點的集合S。

輸出：CH(S)，存儲在棧St中的S的凸包。ECNUYinpingLiu1．設p0為具有最小

y坐標的最右點2．T[0]←p03．設T[1…n-1]為S-{p0}中的點，按以p0為原點的極角的升序排列，如果兩個點pi和pj

以p0為原點有相同的極角，則與p0接近的那個點排在前面4．push(St，T[n一1])；push(St，T[0])5．k←16．whilek<n一17．設St=(T[n-1]，…，T[i]，T[j])，T[j]位于棧頂ECNUYinpingLiu8．IfT[i]，T[j]，T[k]為左旋

then9．push(St，T[k])10．k←k+111．elsepop(St)12．endif13．endwhile算法CONVEXHULL的運行時間計算如下:ECNUYinpingLiu排序步驟耗費O(nlogn)時間，至于while循環(huán)，我們觀察到，對于每一點恰好壓棧一次，最多彈棧一次。此外，檢驗三點是否形成左旋或右旋相當于計算它們帶符號的面積，耗時O(1)，這樣while循環(huán)的耗費是O(n)?？梢娝惴ǖ臅r間復雜性是O(nlogn)。練習18．9給出了另一種方法，它可以避免計算極角，其他計算凸包的算法在練習18.10和練習18.13中概要敘述。5.計算點集的直徑ECNUYinpingLiu設S是平面中點的集合，我們定義S中任意兩點間的最大距離為S的直徑，記為Diam(S)。對于這個問題，一種直接的算法是比較每個點對的距離，返回S中兩點實現(xiàn)的最大距離。采用這一策略，我們將得到一個O(n2)時間的算法。在本節(jié)中，我們研究一種算法，它能在O(nlogn)時間內(nèi)找出平面中點集的直徑。我們從以下的觀察結論開始，它看起來是直觀的(見圖18.11)圖18.11ECNUYinpingLiu觀察結論18.1

一個點集的直徑是它的凸包的直徑,即Diam(S)=Diam(CH(S)).因此，要計算平面中點集的直徑，只需要考慮凸包上的頂點。所以下面將實際上考察尋找凸多邊形直徑的問題。定義18.3設P是一個凸多邊形，P的一條支撐線是指通過P頂點的一條直線l，它使得P的內(nèi)部整個地在l的一邊(見圖18.12)。ECNUYinpingLiu圖18.12凸多邊形的一些支撐線下面的定理中給出了凸多邊形直徑的一個有用的特性(見圖18.13)定理18.1

凸多邊形P的直徑等于P的任意平行支撐線對之間的最大距離。定義18.4.接納兩條平行支撐線的任意兩點稱為跖對。對于定理18.1，我們有如下推論:ECNUYinpingLiu圖18.13具有最大間隔的平行支撐線推論18.1

在凸多邊形中實現(xiàn)直徑的任何頂點對是一個跖對。根據(jù)上述推論，問題現(xiàn)在簡化為找出所有的映對，并且選出具有最大間隔的那一對。事實上我們能夠以最優(yōu)線性時間完成。ECNUYinpingLiu定義18.5

定義點p和線段qr間的距離，記為dist(q,r,p),是從線段qr所在的直線到p的距離。如果dist(q,r,p)最大,則p是到線段qr

最遠的點。考慮圖18.14(a),其中顯示了一個凸多邊形p。從該圖中我們很容易看到p5是離邊p12p1最遠的頂點。類似地，頂點p9是離邊p1p2最遠的頂點。(a)(b)圖18.14計算跖對ECNUYinpingLiu可以證明，一個頂點p和p1形成一個跖對當且僅當它是頂點p5，p6，…，p9的一個。一般地，對于某個m≤n，設點集凸包上的頂點按逆時針序是p1,p2,…,pm，當沿逆時針方向掃過CH(S)的邊界時，設pl是第一個離邊p1p2最遠的頂點(見圖18.14(b))。那么，在pk和pl間的任何頂點(包括pk和pl)和p1形成一個跖對。而且，所有其他頂點不和p1形成跖對。這個重要的觀察結論提示我們采用如下的方法來找出所有的跖對.ECNUYinpingLiu首先從p2開始沿逆時針序掃過CH(S)的邊界直到我們找到pk，離pmp1最遠的頂點。我們把點對(p1，pk)加到存放跖對且初始時為空的集合中去。然后我們繼續(xù)掃邊界并對于遇到的每一個頂點pi存放點對(p1，pj)，直到我們達到離p1p2最遠的頂點Pl。可能有這樣的情況，l=k+1或甚至l=k，就是pl=pk。接著，我們進到p2p3來尋找和p2形成跖對的頂點。這樣，我們同時做兩個邊界逆時針掃描：一個從p1到pk，另一個從pk到pm。當探測到跖對(pk，pm)時掃描停止。最后，對跖對集合做一次線性掃描顯然足以找到凸包的直徑。由觀察結論18.1，它是所要求的點集的直徑。算法DIAMETER中給出了更形式的描述。ECNUYinpingLiu算法18.4DIAMETER

輸入：平面上n個點的集合S。

輸出：Diam(S)，S的直徑。

1．{P1，P2，