計(jì)算機(jī)算法基礎(chǔ) 第2版 課件 第12章 計(jì)算幾何基礎(chǔ)

1第12

章

計(jì)算幾何基礎(chǔ)計(jì)算幾何簡介

2平面線段及相互關(guān)系

3平掃線技術(shù)和線段相交的確定

17平面點(diǎn)集的凸包

27Graham掃描法

29Jarvis行進(jìn)法 38最近點(diǎn)對(duì)問題

441.計(jì)算幾何簡介

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

2.平面線段及其相互關(guān)系

4

5

顯然，

p1

p2=p2

p1，但是

p1

p2=-p2

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

O=(0,0)p1p2

X

Y(x1,y1)(x2,y2)點(diǎn)積7

O=(0,0)p1p2

X

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

u8平面線段的相互關(guān)系我們回答前面所提的三個(gè)問題

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

p2>0那么p1是在p2

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

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

p2

=

|Op1||Op2|sin

。如果p1

p2>0，那么就有sin

>0。sin

>0說明

=(

-

)>0，即p1是在p2

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

-

)<0，即p1是在p2

的逆時(shí)針方向上。如果p1

p2=0，sin

=0，必有

=0或

=180

，顯然表明二個(gè)向量共線。

9P1P2

OP1P2

O(a)p1

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

p1

p2

<0,在p1處向右拐

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

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

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

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

逆向行走。這就回答了第二個(gè)問題。

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。兩個(gè)線段不共線而且相交。充要條件是情形(1)(2)的條件不滿足。(偽碼見下頁)14

15

16OP1P2P3P4p1=(-3,4)，p2

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

和p4

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

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

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

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

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

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

平掃線在4個(gè)點(diǎn)的狀態(tài):

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

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

f，但是f

>y

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

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

s

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

r的右端點(diǎn)。操作如下：檢查

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

(參閱附錄-A)。

這里我們約定幾個(gè)對(duì)紅-黑樹T進(jìn)行操作的記號(hào)：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個(gè)線段的集合T

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

個(gè)端點(diǎn)排序，得調(diào)度序列L[1..2n]for

i

1to2n

ifL[i]

istheleftendpointofsegments //L[i]是線段s的左端點(diǎn) then

Insert(T,s)

if

(Above(T,s)existsandintersectss)

//調(diào)用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的右端點(diǎn)

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

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

then

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

endif

Delete(T,r)

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

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

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

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

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

兩個(gè)線段的左端點(diǎn)都與交點(diǎn)p重合。pab27定義12.5

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

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

28p0p1p4p2p3p5(a)

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

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

一個(gè)凸多邊形例定義

12.9

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

P9下面討論兩個(gè)找凸包的算法。29

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

3個(gè)點(diǎn)的集合假設(shè)已有

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 //從點(diǎn)p到q后，再到pi時(shí)，不左拐 Pop(S) //點(diǎn)q不可能是凸包的頂點(diǎn)

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時(shí)，彈出p4后壓入p5

p2

p6p4

p7p5p9

p8

p1

p0p3(a)

初始狀態(tài)

p2

p6p4

p7p5p9

p8

p10

p1

p0p3(b)

掃描到p3時(shí)，彈出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時(shí)，彈出p7、p6后壓入p8

p2

p6p4

p7p5p9

p8

p1

p0p10p3(h)

掃描

p9后壓入p9

p2

p6p4

p7p5p9

p8

p1

p033p10p3(i)

掃描

p10時(shí)，彈出p9后壓入p10

p2

p6p4

p7p5p9

p8

p1

p0p10p3(j)

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

p2

p6p4

p7p5p9

p8

p1

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

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

Q3

…

Qn

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

=Q，定理得證。我們?cè)O(shè)計(jì)一個(gè)與

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

(k

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

pipi-1(a)

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

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

p0pjpi中。因?yàn)閺膒j到pi是向左拐，因此CH(Qj)加上pi點(diǎn)后是Qj

{pi}的凸包。因?yàn)樗斜粡棾龅狞c(diǎn)也被包含在這個(gè)凸包中，因此斷言在這種情況下亦正確。循環(huán)終止因?yàn)橥Ｖ箯棾鰰r(shí)堆棧中至少有兩個(gè)點(diǎn)，所以每次循環(huán)對(duì)堆棧的操作是有限次。因?yàn)檠h(huán)次數(shù)為n-2，所以算法一定會(huì)終止，定理正確。

38

39

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

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

(偽碼見下頁)41

42

p2p10p1p3p8(c)P5是下一個(gè)凸包頂點(diǎn)

p6p4

p7p5p9

p0p8

p10(d)

P8是下一個(gè)凸包頂點(diǎn)p2p1p3

p6p4

p7p5p9

p0p8(a)

初始化后情形

p2p10p1p3

p6p4

p7p5p9

p0(b)

P3是下一個(gè)凸包頂點(diǎn)

p2p10p1p3p8

p6p4

p7p5p9

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

P10是下一個(gè)凸包頂點(diǎn)

p2p10p1p8

p6p4

p7p5p9

p0

p2p10p1p3p8

p6p4

p7p5p9

p0Jarvis行進(jìn)法復(fù)雜度因?yàn)閺亩褩Ｖ忻總€(gè)點(diǎn)出發(fā)去找下一個(gè)凸包頂點(diǎn)時(shí)，Jarvis行進(jìn)法需要在集合Q中找出最右邊點(diǎn)，這需要O(n)時(shí)間，所以Jarvis行進(jìn)法的復(fù)雜度是O(hn)，這里h是凸包頂點(diǎn)的個(gè)數(shù)，也是算法結(jié)束時(shí)堆棧中點(diǎn)的個(gè)數(shù)。44給定平面上n個(gè)點(diǎn)的集合P，最近點(diǎn)對(duì)問題是：找出兩個(gè)點(diǎn)a和b使得它們的距離是所有點(diǎn)對(duì)中最近的，即d(a,b)=min{d(u,v)|u,v

P}。如果算出所有點(diǎn)對(duì)之間的距離，那么需要

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

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

Y[1]≤Y[2]≤…≤Y[n]。用X[1..n]表示它們對(duì)應(yīng)的X坐標(biāo)，所以，這n點(diǎn)可表示為

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

k

n)。把

pk(1

k

n)

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

(1

i

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

k

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

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

47分治法的分設(shè)有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分為左右兩個(gè)集合，L和R。它們的X-坐標(biāo)是

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

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

[mid+1..n]它們對(duì)應(yīng)的Y-坐標(biāo)排序于數(shù)組YL[1..mid]和YR[1..n-mid]中。在劃分時(shí)，如果PL中點(diǎn)有Y坐標(biāo)YL[l]的話(1

l

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

r

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

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

mid=

n/2

已在調(diào)用它的程序中算出l

r

1 //

分別是YL

和YR

的開始序號(hào)fork

1to

n //逐個(gè)分配和處理Y[k]

i

I[k] //Y[k]

的X坐標(biāo)是X*[i]

if

i

mid //對(duì)應(yīng)的點(diǎn)(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 //構(gòu)造函數(shù)IL，YL[l]的X坐標(biāo)是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

//構(gòu)造函數(shù)IR，YR[r]的X坐標(biāo)是X*R[j]

r

r+1

endifendfor

End

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

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

和PR中最近點(diǎn)對(duì)，其距離分別是

L

和

R。它們對(duì)應(yīng)的點(diǎn)對(duì)為(pL，qL)和(pR，qR)。我們先找出

=min{

L

和

R}，其對(duì)應(yīng)點(diǎn)對(duì)為(p,q)。顯然

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

,

)，則其中一點(diǎn)

在集合PL中而另一點(diǎn)

在集合PR中。另外，

和

與直線x

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

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

=l為中心，以

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

。做法如下：50x=lLR

L中的一個(gè)點(diǎn)和R中的一個(gè)點(diǎn)可能在此重迭L中一個(gè)點(diǎn)和R中的一個(gè)點(diǎn)可能在此重迭

(b)

最多8個(gè)點(diǎn)可出現(xiàn)在

2

矩形之中L

R=Y(

)

2

x=l

=Y(

)+

x=l-

x=l+

(a)點(diǎn)對(duì)(

,

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

矩形中51(1) 把帶狀區(qū)域中點(diǎn)按Y-坐標(biāo)從小到大排序于數(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時(shí)已算好m

0fork

1to

n

i

I[k] //

Y[k]對(duì)應(yīng)的X坐標(biāo)是X*[i]

if

(l-

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

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

then

m

m+1

Y*[m]

Y[k]

J[m]

k //以便從Y*[m]找到Y(jié)[k]

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

(1

i

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

(i

<j

m),使得這兩點(diǎn)間距離小于

。假設(shè)Y*[i]對(duì)應(yīng)的點(diǎn)是

，它的Y-坐標(biāo)是Y(

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

2

的矩形中的點(diǎn)與

的距離即可。