計算機算法基礎 第2版 課件 第12章 計算幾何基礎

1第12

章

計算幾何基礎計算幾何簡介

2平面線段及相互關系

3平掃線技術和線段相交的確定

17平面點集的凸包

27Graham掃描法

29Jarvis行進法 38最近點對問題

441.計算幾何簡介

2計算幾何(ComputationalGeometry)是計算機算法的一個重要分支，它要解決的是如何有效地完成與幾何問題有關的算法問題。例如，在X-Y平面中求兩點間距離是個簡單的幾何問題，但是如何快速地在n個點中找出距離最近的兩個點就是個算法問題。計算幾何在許多領域有廣泛的應用，例如計算機圖形學、機器人、電子游戲、大規(guī)模積成電路設計，生物信息科學等。這一學科的研究需要一些幾何知識，但大部分情況下，不需要高深的幾何知識，這要視具體問題而定。3

2.平面線段及其相互關系

4

5

顯然，

p1

p2=p2

p1，但是

p1

p2=-p2

p1。下圖(圖12-1)解釋這兩個乘積的幾何意義。6點積和叉積的幾何含義

O=(0,0)p1p2

X

Y(x1,y1)(x2,y2)點積7

O=(0,0)p1p2

X

Y(x1,y1)(x2,y2)p1叉積

u8平面線段的相互關系我們回答前面所提的三個問題

(p4)。定理12.1給定X-Y平面上兩個向量，p1和p2，如果p1

p2>0那么p1是在p2

的順時針方向上，否則是在其逆時針方向上。如果p1

p2=0，則表明兩個向量共線。證明：由上面的分析可知，p1

p2

=

|Op1||Op2|sin

。如果p1

p2>0，那么就有sin

>0。sin

>0說明

=(

-

)>0，即p1是在p2

的順時針方向上。否則，(

-

)<0，即p1是在p2

的逆時針方向上。如果p1

p2=0，sin

=0，必有

=0或

=180

，顯然表明二個向量共線。

9P1P2

OP1P2

O(a)p1

p2>0,在p1處向左拐(b)

p1

p2

<0,在p1處向右拐

10注：推論12.2中，如果起點不是原點O，而是p0，那么我們在p1點應該向左拐呢，還是向右拐呢？我們可以先把原點O平移到p0再考慮這個問題。這等價于考慮向量(p1-p0)和(p2-p0)的叉乗。所以，如果(p1-p0)

(p2-p0)>0，那么在p1點向左拐；如果(p1-p0)

(p2-p0)<0，則是向右拐；如果(p1-p0)

(p2-p0)=0，那么在p1點要么不改變方向，要么轉180

逆向行走。這就回答了第二個問題。

11

12

13

p1p3p2p4p4p1p2p3

判斷方法:

d1

=(p2–p1)

(p3–p1)，

d2

=(p2–p1)

(p4–p1) d3

(p4–p3)

(p1–p3)，

d4

(p4–p3)

(p2–p3)。不共線，不相交的充要條件是d1d2>0或d3d4>0。兩個線段不共線而且相交。充要條件是情形(1)(2)的條件不滿足。(偽碼見下頁)14

15

16OP1P2P3P4p1=(-3,4)，p2

=(2,6)，p3=(-1,7)

和p4

=(4,-5)173.平掃線技術和線段相交的確定

平掃線技術(Sweepingline)是解決許多應用問題的一個重要技巧。我們通過下面這一問題來解釋這個技術：

問題：假設X-Y平面上有n個線段，如何設計一個快速有效算法來確定是否有兩個線段相交？如果用程序Segment-Intersect為每一對線段作判斷，復雜度是

(n2)。如果用平掃線技術，則只需O(nlgn)時間就可以判斷。做法：用一根垂直于X軸的直線l，稱為平掃線，從左向右掃描。我們只需檢查2n個位置上l的狀態(tài)即可給出答案，每次只需O(lgn)時間。為簡單起見，假定沒有垂直于X軸的線段，也沒有三個線段交于一點。所以，每個線段的左、右端點有不同的X坐標。（下面會詳細討論）18平掃線的狀態(tài)定義12.4當平掃線l停留在橫坐標為x的位置時，所有與l相交的線段按交點的縱坐標從大到小排序。這個序列稱為

l在點x時的狀態(tài)，而點x稱為平掃線l的一個狀態(tài)點。序列中任兩個線段，u和v，稱為在點x可比較，并且，如果u在v之上，則記為u>x

v。例(圖12-5)udcabtr(a)平掃線在3個點的狀態(tài): r點:<a,c>t點:<a,b,c>u點:<b,c>eifhgyxwz(b)

平掃線在4個點的狀態(tài):

w點:<e,g,f>x點:<e,f>y點:<f,e>z點:<f,i,e>19平掃線的事件點我們有以下觀察：如果線段u和v相交于點p，那么必有狀態(tài)點x<p

和狀態(tài)點y>p使得在x和y的狀態(tài)序列中，u和v相鄰，但它們的順序相反。例如，在上圖(b)中，e>x

f，但是f

>y

e。平掃線狀態(tài)中的線段集合，在碰到下面兩種情況時才會改變：到達一個位置，正好是一個新線段的左端點。到達一個位置，正好是狀態(tài)中某個線段的右端點。n個線段有2n個端點。它們在X軸上的坐標稱為事件點(eventpoint)。算法根據(jù)平掃線狀態(tài)在這2n個事件點上的變化作出判斷。20事件點調度序列把2n個事件點從小到大，即從左到右，排序后的序列稱為事件點調度(Event-pointscheduling)序列。如果有多端點有共同的X-坐標，把左端點排在右端點前面。如果有多個左端點有共同的X-坐標，有較小Y-坐標的排在前面。如果有多個右端點有共同的X-坐標，有較小Y-坐標的排在前面。

21用平掃線確定線段相交的算法簡介按調度序列，逐點檢查。在每個事件點上，做下面兩件事之一：如果這個點是某線段s的左端點。操作如下：將

s

插入到狀態(tài)序列中。并檢查，s插入后，它是否有相鄰線段。如果有，用程序Segment-Intersect判斷它們與s是否相交。如果相交，算法結束并報告一對相交的線段。否則，進入下一個事件點。如果這個點是某線段

r的右端點。操作如下：檢查

r是否同時有上面的相鄰線段和下面的相鄰線段。如果有，用程序Segment-Intersect判斷這兩個相鄰線段之間是否相交。如果相交，算法結束并報告一對相交的線段。否則，算法將線段r從狀態(tài)序列中刪除。然后，進入下一個事件點。如果在2n個事件點都檢查之后仍未發(fā)現(xiàn)有線段相交，則算法結束并報告沒有交點。22紅-黑樹平掃線技術需要動態(tài)地，不斷地對狀態(tài)序列進行插入一個線段或刪除一個線段的操作，我們用紅-黑樹為數(shù)據(jù)結構來支持這些操作。紅-黑樹是二元搜索樹的一種。它可保證在O(lgn)時間內完成一個插入或刪除操作，這里，n是當前紅-黑樹中頂點的個數(shù)。所以，為2n個事件點更新狀態(tài)總共只需要O(nlgn)時間

(參閱附錄-A)。

這里我們約定幾個對紅-黑樹T進行操作的記號：Insert(T,s): 把線段s插入T；Delete(T,s): 把線段s從T中刪除；Above(T,s): 找出T中緊排在s上面的線段；Below(T,s): 找出T中緊排在s下面的線段。用平掃線確定線段相交的算法偽碼如下。23Any-Segments-Intersect(S,n) //S是n個線段的集合T

//紅黑樹初始為空把2n

個端點排序，得調度序列L[1..2n]for

i

1to2n

ifL[i]

istheleftendpointofsegments //L[i]是線段s的左端點 then

Insert(T,s)

if

(Above(T,s)existsandintersectss)

//調用Segment-Intersect，如果s與上面相鄰線段相交

thenreturntrue,s,Above(T,s)，endif

if(Below(T,s)existsandintersectss)//下面線段與s相交

thenreturntrue,s,Below(T,s)，endif else

L[i]istherightendpointofsegmentr

//L[i]是線段r的右端點

ifAbove(T,r)andBelow(T,r)existandintersect

//線段r上面和下面的線段存在并相交

then

returntrue,Above(T,r),Below(T,r)

endif

Delete(T,r)

endifendforreturnfalseEnd24例(圖12-6)第1個事件點上只有a；第2個事件點上插入b在a之下但不相交；第3個事件點上插入c，與a和b相鄰但都不相交；第4個事件點上插入d在a之上但不相交；第5個事件點上刪去a后d與c相鄰但不相交；第6個事件點上插入e在d之上但不相交；第7個事件點上刪去c后發(fā)現(xiàn)d與b相鄰并相交，算法結束。acbedcbdacbdcababeafdcbedb(1)(2)(3)(4)(5)(6)(7)25定理12.3

算法Any-Segments-Intersect能正確地確定S中是否有線段相交。證明：當算法報告有線段相交時顯然是正確的，所以我們只需證明，只要有線段相交，算法一定會報告true。假設S中有線段相交，而p是所有交點中X-坐標最小的一個，并假設在p點相交的線段是a和b。我們分三種情況討論。(a) 線段a和b的左端點均出現(xiàn)在點p的左邊。設點q是點p左邊最后一個事件點。如果a和b在q的平掃線狀態(tài)中不相鄰，那么如圖(a)，一定有線段d在q點的狀態(tài)中介于a和b之間。(a)

線段a和b的左端點都出現(xiàn)在交點p的左邊。dpabq如果d的右端點在q的右邊，則d必與a或b相交，點p就不是最左邊的交點了，矛盾。如果右端正好在q點的平掃線上，那么在事件點q上把d刪去后，發(fā)現(xiàn)a和b相鄰并相交。因假設無3線段共點，

右端點不會在p點。26（接上頁）(b) 線段a的左端點在點p的左邊，而b的左端點與p重合。(b)

線段a的左端點在p點左邊而線段b的左端點與交點p重合。pab這種情況下，p點是事件點。如在p點之前，已發(fā)現(xiàn)有線段相交，證明完成。否則，算法會在p點把b插入到平掃線狀態(tài)中并且與a相鄰。顯然，算法會報告a和b相交。同理可證對稱情況，即a的左端點與p重合，而b的左端點出現(xiàn)在p的左邊。線段a和b的左端點均與點p重合。這種情況下，a和b的左端點都是事件點，并且會在p點的平掃線狀態(tài)中被先后插入而且相鄰，所以算法會報告a和b相交。(證畢)(c)

兩個線段的左端點都與交點p重合。pab27定義12.5

一個多邊形就是平面上一組首尾相連的線段組成的封閉曲線。曲線中的線段稱為邊(side)，而這條曲線稱為多邊形的邊界。假設順序有n條邊，(p0,p1)，(p1,p2)，…，(pn-1,p0)，那么這個多邊形稱為n邊形，并可表示為<p0,p1,…,pn-1>，稱為頂點序列。定義12.6

一個簡單n邊形就是自身無交點的多邊形，即它的n條邊之間，除相鄰兩條邊的一端點重合外，沒有其他交點。除特別說明外，我們只討論簡單多邊形，簡稱多邊形。定義12.7被一個多邊形所包圍的平面上的點的集合(不含邊界)稱為該多邊形的內部，多邊形的邊界和內部的點以外的平面上所有其他點的集合稱為該多邊形的外部。定義12.8如果一個多邊形的內部或邊界上任意兩點間的線段不含外部的點，那么該多邊形稱為一個凸多邊形。3.平面點集的凸包

28p0p1p4p2p3p5(a)

一個非簡單多邊形p5p3p2p4p0p1(b)

一個簡單多邊形但不是凸多邊形p0p4p3p2內部外部邊界p1(c)

一個凸多邊形例定義

12.9

假設Q是平面上n個點的集合，它的凸包(ConvexHull)是包含Q的最小凸多邊形，記為CH(Q)。例(圖12-9)p1p2p3p4p5p6p7p8p0

P9下面討論兩個找凸包的算法。29

30Graham-scan(Q) //Q是有n+1

3個點的集合假設已有

1

<

2

<…<

n。Push(S,p0)；Push(S,p1)；Push(S,p2)； //初始化fori

3to

n

q

Top(S) p

Next-to-top(S) while(q–p)

(pi–q)

0 //從點p到q后，再到pi時，不左拐 Pop(S) //點q不可能是凸包的頂點

q

p

p

Next-to-top(S)

endwhile Push(S,pi)endforreturn

SEnd31例(圖12-10)p10p3(c)

掃描p4后壓入p4

p2

p6p4

p7p5p9

p8

p1

p0p10p3(d)

掃描p5時，彈出p4后壓入p5

p2

p6p4

p7p5p9

p8

p1

p0p3(a)

初始狀態(tài)

p2

p6p4

p7p5p9

p8

p10

p1

p0p3(b)

掃描到p3時，彈出p2后壓入p3

p2

p6p4

p7p5p9

p8

p10

p1

p032p10p3(e)

掃描

p6后壓入p6

p2

p6p4

p7p5p9

p8

p1

p0p10p3(f)

掃描

p7后壓入p7

p2

p6p4

p7p5p9

p8

p1

p0p10p3(g)

掃描

p8時，彈出p7、p6后壓入p8

p2

p6p4

p7p5p9

p8

p1

p0p10p3(h)

掃描

p9后壓入p9

p2

p6p4

p7p5p9

p8

p1

p033p10p3(i)

掃描

p10時，彈出p9后壓入p10

p2

p6p4

p7p5p9

p8

p1

p0p10p3(j)

算法產(chǎn)生的凸包

p2

p6p4

p7p5p9

p8

p1

p0Graham掃描法復雜度主要部分是排序。排序后的掃描只需O(n)時間，這是因為每次檢查三點兩線段的走向是在向堆棧內壓入一個點或彈出一個點之后進行，包括第一次檢查也是在初始化壓入三點后進行。因每個點最多被壓入和彈出各一次，而檢查一次只需常數(shù)時間，所以排序后的掃描只需O(n)時間，因此，掃描法的復雜度是O(nlgn)。34Graham掃描法的正確性證明定理12.4算法Graham-scan(Q)結束時，堆棧中從底到頂?shù)狞c的序列就是點集合Q的凸包頂點沿反時針方向的一個序列。證明：初始化后，其余各點掃描的順序是p3,p4,…,pn。定義Qi

={p0,p1,p2,…,pi}，i=2,3,4,…,n。顯然有Q2

Q3

…

Qn

=Q。下面，我們歸納證明：在for循環(huán)從i=3開始，對pi掃描后，堆棧中從底到頂?shù)狞c的序列就是Qi的凸包頂點沿反時針方向的一個序列。這樣，在i=n時，因為Qn

=Q，定理得證。我們設計一個與

i有關的命題稱為不變量(invariant)。先證明這個命題在循環(huán)開始前正確(相當于歸納基礎)。再證明每次循環(huán)后，這個命題都是正確的(相當于歸納步驟)。最后證明循環(huán)一定會停止。(接下頁)35命題：對pi掃描后，堆棧中從底到頂?shù)狞c的序列就是Qi的凸包CH(Qi)的頂點沿反時針方向的一個序列。初始化循環(huán)開始前，堆棧中從底到頂點的點序列是{p0,p1,p2}。顯然它是集合Q2的凸包CH(Q2)頂點沿反時針方向的一個序列。循環(huán)維持假設在循環(huán)i=k

(k

3)，之前，堆棧中從底到頂點的點序列是集合Qk-1的凸包CH(Qk-1)的頂點沿反時針方向的一個序列。那么，當我們剛進入循環(huán)i=k時，由算法知，必有Top(S)=pi-1，假設此時，Next-to-top(S)=pa。循環(huán)i=k的操作有兩部分。第一部分是while循環(huán)，把不可能成為凸包頂點的點從堆棧彈出。第二部分是把pi壓入堆棧。這時有兩種情況，分別討論如下：36

pipi-1(a)

壓入pi前棧頂為pi-1Qi-1p0p1pap2(a) 壓入pi前棧頂為pi-1，Next-to-top(S)=pa。因此，在循環(huán)i=k結束時，堆棧中從底到頂?shù)狞c的序列就是凸包CH(Qi)的頂點沿反時針方向的一個序列。（第2種情況見下頁）37

(b) 壓入pi前棧頂為pj，而j<i-1。pj(b)壓入pi前棧頂為pj，j<i-1Qjp0p1pipap2pi-1可看出，所有被彈出的點都被包含在

p0pjpi中。因為從pj到pi是向左拐，因此CH(Qj)加上pi點后是Qj

{pi}的凸包。因為所有被彈出的點也被包含在這個凸包中，因此斷言在這種情況下亦正確。循環(huán)終止因為停止彈出時堆棧中至少有兩個點，所以每次循環(huán)對堆棧的操作是有限次。因為循環(huán)次數(shù)為n-2，所以算法一定會終止，定理正確。

38

39

40算法的正確性證明(繼續(xù))因此，棧外各點，pi+1,pi+2,…,pn，以及p0，除pk外的任何一點都不可能是在凸包CH(Q)的頂點沿反時針方向的序列中接在pi后面的頂點，否則，如下圖(12-12)所示，pk會落在凸包的外部。因此，凸包中pi后面的頂點必定是pk。歸納成功。pkp0p1piPu堆棧中點都是凸包頂點棧外所有點，以及p0，都在pk的逆時針方向或在線段(pi,pk)上。由所證命題知，每次第(2)步壓入堆棧的點都是凸包的下一個頂點，所以，當pk

=p0時，堆棧中點就必定是CH(Q)的頂點序列，算法正確。

(偽碼見下頁)41

42

p2p10p1p3p8(c)P5是下一個凸包頂點

p6p4

p7p5p9

p0p8

p10(d)

P8是下一個凸包頂點p2p1p3

p6p4

p7p5p9

p0p8(a)

初始化后情形

p2p10p1p3

p6p4

p7p5p9

p0(b)

P3是下一個凸包頂點

p2p10p1p3p8

p6p4

p7p5p9

p0例(圖12-13)43p3(e)

P10是下一個凸包頂點

p2p10p1p8

p6p4

p7p5p9

p0

p2p10p1p3p8

p6p4

p7p5p9

p0Jarvis行進法復雜度因為從堆棧中每個點出發(fā)去找下一個凸包頂點時，Jarvis行進法需要在集合Q中找出最右邊點，這需要O(n)時間，所以Jarvis行進法的復雜度是O(hn)，這里h是凸包頂點的個數(shù)，也是算法結束時堆棧中點的個數(shù)。44給定平面上n個點的集合P，最近點對問題是：找出兩個點a和b使得它們的距離是所有點對中最近的，即d(a,b)=min{d(u,v)|u,v

P}。如果算出所有點對之間的距離，那么需要

(n2)時間。我們介紹一個只要O(nlgn)時間的分治法。分如下幾部分討論：預備工作和分治法的底分治法的分分治法的合分治法的偽碼4.最近點對問題

45預備工作和分治法的底把P中這n個點的Y坐標從小到大排序并存放在數(shù)組Y中，使得

Y[1]≤Y[2]≤…≤Y[n]。用X[1..n]表示它們對應的X坐標，所以，這n點可表示為

pk=(X[k],Y[k])(1

k

n)。把

pk(1

k

n)

的X坐標從小到大排序并存放在數(shù)組X*中，使得X*[1]≤X*[2]≤…≤X*[n]

(1

i

n)。用函數(shù)I[k]記錄原序列中X[k](1

k

n)在序列X*中的序號。如果X[k]=X*[i]，則有I[k]=i。如果n

2，分治法見底，我們可以直接地算出最近點對的距離。算法對底的處理很簡單，下頁給出這部分的偽碼。46

47分治法的分設有Y[1]≤Y[2]≤…≤Y[n]，X*[1]≤X*[2]≤…≤X*[n]，并且已建立函數(shù)I[k](1

k

n)。如果n

3，則需要分治。下面是分治的步驟：mid

n/2；以直線x

=X*[mid]為分界線把P分為左右兩個集合，L和R。它們的X-坐標是

X*L[1..mid]=X*[1..mid]

X*R[1..n-mid]=X*

[mid+1..n]它們對應的Y-坐標排序于數(shù)組YL[1..mid]和YR[1..n-mid]中。在劃分時，如果PL中點有Y坐標YL[l]的話(1

l

mid)，那么，求該點的X坐標在X*L中的序號的函數(shù)IL[l]也同時產(chǎn)生。同樣地，對PR中點(1

r

n-mid)，函數(shù)IR[r]也同時產(chǎn)生。以上劃分集合P的工作可用下面一段程序完成

(見下頁)48Distribution(X*[1..n],Y[1..n],I[1..n],mid) //

mid=

n/2

已在調用它的程序中算出l

r

1 //

分別是YL

和YR

的開始序號fork

1to

n //逐個分配和處理Y[k]

i

I[k] //Y[k]

的X坐標是X*[i]

if

i

mid //對應的點(X*[i],Y[k])屬于PL

then

YL[l]

Y[k] //把Y[k]按序排入左集合

X*L[i]

X*[i] //

逐步做X*L[1..mid]

X*[1..mid]

IL[l]

i //構造函數(shù)IL，YL[l]的X坐標是X*L[i]

l

l+1

else

YR[r]

Y[k] //把Y[k]按序排入右集合

j

i–mid

X*R[j]

X*[i] //

逐步做X*R[1..n-mid]

X*[mid+1..n]

IR[r]

j

//構造函數(shù)IR，YR[r]的X坐標是X*R[j]

r

r+1

endifendfor

End

分治法的劃分總共需要O(n)時間49分治法的合把P中點分為PL

和PR后，遞歸地分別找到PL

和PR中最近點對，其距離分別是

L

和

R。它們對應的點對為(pL，qL)和(pR，qR)。我們先找出

=min{

L

和

R}，其對應點對為(p,q)。顯然

不一定是最近奌對的距離。分治法的合就是要解決子問題的解不能包含的那些情況下的解。在這個問題中，如果有更近的點對(

,

)，則其中一點

在集合PL中而另一點

在集合PR中。另外，

和

與直線x

=l(=X*[mid])的距離必須小于

。如下圖(12-14(a))所示，我們只須檢查以直線x

=l為中心，以

為左右距離的帶狀區(qū)域中點即可。我們檢查是否這個區(qū)域中有兩點，其距離小于

。做法如下：50x=lLR

L中的一個點和R中的一個點可能在此重迭L中一個點和R中的一個點可能在此重迭

(b)

最多8個點可出現(xiàn)在

2

矩形之中L

R=Y(

)

2

x=l

=Y(

)+

x=l-

x=l+

(a)點對(

,

)必須出現(xiàn)在2

矩形中51(1) 把帶狀區(qū)域中點按Y-坐標從小到大排序于數(shù)組Y*[1..m]

(m

n)中。

另外，用J[h]=k

表示Y*[h]在原序列Y[1..n]中的位置，即Y*[h]=Y[k](1

h

m)。這一步可由下面程序完成：Delta-Selection(X*[1..n],Y[1..n],I[1..n],Y*[1..m],J[1..m],

)//輸出Y*，Jl

X*[mid] //mid

在劃分集合P時已算好m

0fork

1to

n

i

I[k] //

Y[k]對應的X坐標是X*[i]

if

(l-

<X*[i])and(X*[i]<l+

) //帶狀區(qū)內，順序放入Y*

then

m

m+1

Y*[m]

Y[k]

J[m]

k //以便從Y*[m]找到Y[k]

endifendfor //帶狀區(qū)域內有m個點End52逐點檢查Y*[i]

(1

i

m)，看是否有Y*[j]

(i

<j

m),使得這兩點間距離小于

。假設Y*[i]對應的點是

，它的Y-坐標是Y(

)=Y*[i]，如上圖(12-14(a))所示，我們只需檢查

2

的矩形中的點與

的距離即可。