算法設(shè)計(jì)與分析(十)

1、算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析2010.92010.9(ACM(ACM創(chuàng)新實(shí)驗(yàn)班創(chuàng)新實(shí)驗(yàn)班) )王多強(qiáng)王多強(qiáng)十、計(jì)算幾何學(xué)十、計(jì)算幾何學(xué)什么是計(jì)算幾何學(xué)？ 計(jì)算幾何學(xué)是計(jì)算機(jī)科學(xué)的一個(gè)分支，專門研究解決幾何問題的算法。 這一類問題中，輸入一般是關(guān)于一組幾何對(duì)象的描述，如點(diǎn)、線段、多邊形等。輸入則是對(duì)有關(guān)這些對(duì)象的問題的解答，如直線是否相交？是否為一個(gè)新的幾何對(duì)象，如頂點(diǎn)集合的凸包等。 p1p2p4p2計(jì)算幾何學(xué)常見問題折線段的拐向判斷判斷點(diǎn)與線、矩形、多邊形、圓之間的相對(duì)位置關(guān)系計(jì)算點(diǎn)到線段、折線、矩形、多邊形的最近點(diǎn)計(jì)算線段、直線與線、矩形、多邊形、圓的交點(diǎn)判斷形狀間的包含，如一個(gè)矩形是否在另

2、一個(gè)矩形之中凸包問題等 在現(xiàn)代工程和數(shù)學(xué)領(lǐng)域，計(jì)算幾何在圖形學(xué)、機(jī)器人技術(shù)、超大規(guī)模集成電路設(shè)計(jì)和統(tǒng)計(jì)學(xué)等諸多領(lǐng)域，都有著十分重要的應(yīng)用。10.1 線段的性質(zhì)1.點(diǎn)的表示 n個(gè)點(diǎn)輸入對(duì)象記為：p1,p2,.,pn，其中每個(gè)pi=(xi,yi),xiR,yiR。 形狀一般用點(diǎn)的序列來表示，如多邊形用頂點(diǎn)集p1,p2,.,pn表示。2.點(diǎn)的凸組合(convex combination) 兩個(gè)不同的點(diǎn)p1=(x1,y1)和p2=(x2,y2)的凸組合是滿足下列條件的任意點(diǎn)p3=(x3,y3)：對(duì)于a，(0a1)，有： x3=ax1+(1-a)x2 ,y3=ay1+(1-a)y2。 也可寫作p3=ap

3、1+(1-a)p2。 p1,p2,p3的相對(duì)位置關(guān)系如圖： 亦即，p3位于穿過p1和p2的直線上、并處于p1和p2之間（包括p1和p2兩點(diǎn)）的任意點(diǎn)。而線段p1p2可以看作是p1和p2的凸組合的集合p1p3p2這里， 稱p1、p2是線段的p1p2的端點(diǎn)。 如果考慮有向性，可以記有向線段為p1p2。 如果p1是原點(diǎn)(0,0)，則有向線段p1p2簡(jiǎn)稱為向量向量p2。 向量p1和p2的叉積可以看作是由點(diǎn)(0,0)，p1，p2和p1+p2=(x1+x2,y1+y2)所形成的平行四邊形的面積。如圖所示： 叉積也被定義為下面的行列式形式：叉積p2p1p1+p2(0,0)121221212121ppyxyx

4、yyxxpp分析： 如果p1p2為正數(shù)，則相對(duì)于原點(diǎn)(0,0)來說，p1在p2的順 時(shí)針方向上； 如果p1p2為負(fù)數(shù)，則p1在p2的逆時(shí)針方向上； 下圖示出向量p的順時(shí)針區(qū)域和逆時(shí)針區(qū)域。 如果叉積為0的話，則p1、p2共線，p1、p2指向同一個(gè)方向 或相反的方向。p(0,0)xyp1p2(0,0)p1p2(0,0)p的逆時(shí)針方向p的順時(shí)針方向p1、p2同向共線p1、p2逆向共線如何判斷線段之間的相對(duì)方向？ 已知兩個(gè)有公共端點(diǎn)p0的有向線段p0p1、p0p2，計(jì)算叉積： (p1-p0)(p2-p0)=(x1-x0)(y2-y0)-(x2-x0)(y1-y0) 若0，則p0p1在p0p2的順時(shí)針

5、方向上 若0，則p0p1在p0p2的逆時(shí)針方向上 若0，則p0p1和p0p2共線確定連續(xù)線段是向左轉(zhuǎn)還是向右轉(zhuǎn)？ 已知兩條連續(xù)的線段p0p1、p1p2，在p1點(diǎn)是向左轉(zhuǎn)還是向右轉(zhuǎn)？ 方法一：運(yùn)用三角公式求出p0p1p2，判斷其轉(zhuǎn)向； 方法二：運(yùn)用叉積，無需對(duì)角進(jìn)行計(jì)算即可判斷線段的轉(zhuǎn)向。亦即如圖所示，檢查有向線段p0p2是在有向線段p0p1的順時(shí)針方向還是在其逆時(shí)針方向？p0p1p2逆時(shí)針p0p2順時(shí)針p1計(jì)算叉積：(p2-p0)(p1-p0) 若叉積0,則p0p2在p0p1逆時(shí)針方向，在點(diǎn)p1就是左轉(zhuǎn)。 若叉積0,則p0p2在p0p1順時(shí)針方向，在點(diǎn)p1就是右轉(zhuǎn)。 若叉積0,則p0、p1、p

6、2三點(diǎn)共線。p0p1p2逆時(shí)針p0p2順時(shí)針p1確定兩個(gè)線段是否相交跨域：給定一個(gè)線段p0p2線，如果點(diǎn)p1位于某一直線 的一邊，而點(diǎn)p2位于該直線的另一邊，則稱線 段p0p2跨越了該直線。 如果p1和p2落在直線上，則出線共線情況。相交：當(dāng)且僅當(dāng)下面兩個(gè)條件中至少一條成立時(shí)， 兩個(gè)線段相交： 1）每個(gè)線段都跨越了另一線段的直線； 2）一個(gè)線段的某一端點(diǎn)位于另一線段上。p1p2程序描述1）定義過程 DIRECTION(pDIRECTION(pi i,p,pj j,p,pk k) )：使用叉積計(jì)算線段pipk相對(duì)于線段pipj的方位，返回叉積的值。 如圖所示，令d1= DIRECTION(p1,

7、p2,p3)， d2= DIRECTION(p1,p2,p4)， 若d10，d20，且兩者的符號(hào)不同，則線段p3p4跨越線段p1p2的直線，如圖a)和b)。 若d10，則線段p3在線段p1p2的直線上,如圖c)或d)。p1p2p3p4p1p2p3p4p1p2p3p4a)b)c)p1p2p3p4d)2）定義過程 ON-SEGMENT(pON-SEGMENT(pi i,p,pj j,p,pk k) )：當(dāng)dk0時(shí)， ON-SEGMENT(pi,pj,pk)判斷pk是否位于線段pipj上： 點(diǎn)pk位于pipj上的充分必要條件是pk落在端點(diǎn)pi和pj之間，包括與端點(diǎn)pi或pj重疊。 如圖： 圖c)是線

8、段相交的情形，而圖d)中的兩個(gè)線段 并不相交。p1p2p3p4c)p1p2p3p4d)3）定義過程 SEGMENTS-INTERSECT(pSEGMENTS-INTERSECT(p1 1,p,p2 2,p,p3 3,p,p4 4) )： 布爾函數(shù)，判斷線段p1p2和p3p4是否相交，相交，則返回TRUE，否則返回FALSE。4）過程的描述如下： SEGMENTS-INTERSECT(p1,p2,p3,p4) d1DIRECTION(p3,p4,p1) d2DIRECTION(p3,p4,p2) d3DIRECTION(p1,p2,p3) d4DIRECTION(p1,p2,p4) if(d10

9、 and d20)or(d10 and d20) and (d30 and d40)or(d30 and d40) then return TRUE else if d10 and ON-SEGMENT(p3,p4,p1) then return TRUE else if d20 and ON-SEGMENT(p3,p4,p2) then return TRUE else if d30 and ON-SEGMENT(p1,p2,p3) then return TRUE else if d40 and ON-SEGMENT(p1,p2,p4) then return TRUE else retu

10、rn FALSE END SEGMENTS-INTERSECTDIRECTION(pi,pj,pk) return (pk-pi)(pj-pi)END DIRECTIONON-SEGMENT(pi,pj,pk) if min(xi,xj)xkmax(xi,xj) and min(yi,yj)ykmax(yi,yj) then return TRUE else return FALSEEND ON-SEGMENT例：p1p2p3p4p1p2p3p4a)b)0)()(3431pppp0)()(1213pppp0)()(1214pppp0)()(3432pppp0)()(3431pppp0)()(1

11、213pppp0)()(3432pppp0)()(3432pppp分析： 上述問題也可以按照通常的解析幾何的方法求解，如計(jì)算出形如y=kx+b的直線方程，然后求直線交點(diǎn)，然后檢查交點(diǎn)是否落在線段的端點(diǎn)之間，判定線段的相交性。 我們的算法僅使用加、減、乘和比較運(yùn)算就完成了計(jì)算，沒有使用除法，不需要三角函數(shù)計(jì)算。優(yōu)點(diǎn)：除法、三角函數(shù)的計(jì)算代價(jià)都很高除法的舍入誤差問題近似平行線時(shí)，求斜率k對(duì)計(jì)算機(jī)除法運(yùn)算的精度非常敏感，很容易產(chǎn)生溢出問題等。10.2 確定任意一對(duì)線段是否相交 對(duì)給定的一組線段，確定其中任意兩個(gè)線段是否相交？ 這里假設(shè)： 1）所有的線段不垂直的（水平的可以）。 2）相交于同一點(diǎn)的線段

12、數(shù)2。 （假設(shè)的目的是為了在算法設(shè)計(jì)中簡(jiǎn)化對(duì)邊界條件的處理?？梢宰C明假設(shè)的合理性，對(duì)于假設(shè)外的情況也可以進(jìn)行有效處理）掃除技術(shù)掃除技術(shù)（Sweeping）：在幾何空間中，假想存在一條垂直直線，稱為掃除線掃除線。從左到右移動(dòng)掃除線。掃除線移動(dòng)時(shí)會(huì)穿過一組已知的幾何物體，而掃除線移動(dòng)的空間方向移動(dòng)的空間方向可以看作是一種次序（時(shí)間順序或空間位置次序）。利用穿過幾何體時(shí)掃除線的這種次序?qū)缀挝矬w進(jìn)行空間排序、篩選或其它處理。這種技術(shù)稱為掃除技術(shù)abcdrut線段排序線段排序 根據(jù)假設(shè)，不存在垂直線段，所以任何線段與垂直掃除線至多有一個(gè)交點(diǎn)。因此，在某x處，可以根據(jù)線段與掃除線交點(diǎn)的y坐標(biāo)對(duì)線段進(jìn)行排

13、序。 考察兩條線段s1和s2。如果橫坐標(biāo)為x時(shí)，垂直掃除線與這兩條線段都相交，則稱這兩條線段在x處是可比的。 如果s1和s2在x處可比，并且在x處，掃除線的交點(diǎn)與s1的交點(diǎn)比與s2的交點(diǎn)高，則說在x處，s1位于s2之上，記為s1xs2。如圖，有如圖，有 1）arc 2）atb、atc 、btc 3）buc 4）線段d與其它任何線段都不可比abcdrut 對(duì)任意給定的x，關(guān)系x是定義在那些在x出與掃除線相交 的線段上的全序關(guān)系，即任何兩條這樣的線段都是可比的。 當(dāng)線段的左端點(diǎn)遇到掃描線時(shí)，線段進(jìn)入排序，而當(dāng)其 右端點(diǎn)遇到掃除線時(shí)，就離開排序。 隨著x的不同，掃除線與掃除線的交點(diǎn)是不斷變化的，線段

14、 間的次序會(huì)隨之而改變。 如圖，線段e和f相交與o點(diǎn)。 在o的左方，evf， 而在o的右方，fwe 交點(diǎn)交點(diǎn)o o：存在線段次序變換的現(xiàn)象efghiwzvo 當(dāng)掃除線穿過兩條線段的交點(diǎn)時(shí)，它們?cè)谌蛑械奈恢脤⒈活嵉?，如圖所示，線段e、f在交點(diǎn)o處的次序發(fā)生了顛倒。 由于假定沒有三條線段相交于同一點(diǎn)，所以必有某條垂直線掃除線x，使得相交線段e和f在全序x中是連續(xù)連續(xù)的。 如圖，任何穿過陰影區(qū)域的掃描線（如z）都是的e和 f在其全序中連續(xù)。efghiwzvo掃除線的數(shù)據(jù)結(jié)構(gòu)定義掃除線一般要維護(hù)下列兩組數(shù)據(jù)： 1）掃除線狀態(tài)（sweep-line status）：即與掃除線相交的物體之間的關(guān)系； 2

15、）事件點(diǎn)（event-point schedule）：是一個(gè)從左向右的x x坐標(biāo)的排列坐標(biāo)的排列，這些x坐標(biāo)記錄了掃除線狀態(tài)發(fā)生變化的位置。 efghiwzvo 在本問題中，每條線段的端點(diǎn)都是事件點(diǎn)，因?yàn)楫?dāng)掃除線進(jìn)入（離開）任何端點(diǎn)處，都將引起掃除線狀態(tài)的改變。而這，通過增加x坐標(biāo)，從左向右對(duì)線段的端點(diǎn)進(jìn)行排序即可得線段問題的所有事件點(diǎn)。 如果兩個(gè)或多個(gè)端點(diǎn)位于同一條垂直線上，若y坐標(biāo)不同，則有坐標(biāo)小的排在前面，若y坐標(biāo)也相同（即相交于同一點(diǎn)），則看另一端點(diǎn)的x坐標(biāo)，小的放在前面。abcdefabab dbcdcdceehfhf基于上述定義，根據(jù)事件點(diǎn)調(diào)度序列檢查線段。當(dāng)掃除線遇到線段的左端點(diǎn)

16、時(shí)，就把該線段插入到掃除線狀態(tài)中；當(dāng)掃除線遇到線段的右端點(diǎn)時(shí)，就把它從掃除線狀態(tài)中刪去；當(dāng)兩條線段在全序中第一次變?yōu)檫B續(xù)（連續(xù)排列在一起）時(shí)，就檢查它們是否相交（注：非連續(xù)排列在一起的線段是不會(huì)相交的）。掃除線狀態(tài)是一個(gè)全序T，定義T上的操作如下：INSERT(T,s)：把線段s插入T中；DELETE(T,s)：把線段s從T中刪除；ABOVE(T,s)：返回T中緊靠線段s上面的線段；BELOW(T,s)：返回T中緊靠線段s下面的線段。 輸入n條線段，運(yùn)用紅黑樹，可以在O(logn)的時(shí)間內(nèi)執(zhí)行上述操作。判斷線段集合中線段相交的過程ANY-SEGMENTS-INTERSECT(S) /S為n個(gè)線

17、段的集合，如果找到S中任一對(duì)線段相交就返回TRUE；否則，若S中沒有任何線段相交，則返回FALSE。全序T由一棵紅黑樹實(shí)現(xiàn)。/ T sort the endpoints of the segments in S from left to right,breaking ties by puting left endpoint before right endpoints and breaking further ties by putting points with lower y-coordinates first forfor each point p in the sorted list

18、of endpoints do ifdo if p is the left endpoint of a segment s thenthen INSERT(T,s) ifif(ABOVE(T,s) exists and intersects s) or (BELOW(T,s) exists and intersects s) thenthen returnreturn TRUE endifendif ifif p is the right endpoint of a segment s thenthen ifif(both ABOVE(T,s) and BELOW(T,s) exists an

19、d ABOVE(T,s) intersects BELOW(T,s) thenthen returnreturn TRUE DELETE(T,s) endifendif endforendfor returnreturn FALSEEND ANY-SEGMENTS-INTERSECTabcdefa bab dbcdcdceehfhf例：abcdefaabacbdacbdcbedcbedbtimeANY-SEGMENTS-INTERSECT的執(zhí)行過程。每條虛線都是一個(gè)事件點(diǎn)處的掃除線，每條掃除線下的線段名排序?yàn)閒or循環(huán)結(jié)束時(shí)的全序T，在該循環(huán)中，要對(duì)各對(duì)應(yīng)的事件點(diǎn)進(jìn)行處理。當(dāng)線段c被刪除時(shí)，即

20、可發(fā)現(xiàn)線段d和b相交。10.3 凸包問題1.關(guān)于多邊形的概念1）多邊形：是平面上一組首尾相連的折線段所構(gòu)成的封閉曲線稱為多邊形。2）邊：構(gòu)成多邊形的折線段稱為多邊形的邊。3）頂點(diǎn)：連接兩條連續(xù)邊的點(diǎn)稱為頂點(diǎn)。邊頂點(diǎn)4）簡(jiǎn)單多邊形：內(nèi)部沒有交叉的多邊形稱為簡(jiǎn)單多邊形。 非簡(jiǎn)單多邊形 簡(jiǎn)單多邊形 對(duì)一個(gè)簡(jiǎn)單多邊形，內(nèi)部包圍的區(qū)域稱為該多邊形的內(nèi)部?jī)?nèi)部；多邊形的邊構(gòu)成邊界邊界；邊界以外的區(qū)域稱為多邊形的外部外部。外部?jī)?nèi)部邊界凸多邊形：一個(gè)簡(jiǎn)單多邊形，如果給定其邊界上或內(nèi)部 的任意兩點(diǎn)，連接這兩個(gè)點(diǎn)的線段上的所有點(diǎn) 都包含在該多邊形的邊界上或內(nèi)部，則該多邊 形為凸多邊形（convex polygon）

21、。非凸多邊形凸多邊形內(nèi)部?jī)?nèi)部點(diǎn)的極角點(diǎn)的極角：一個(gè)點(diǎn)p相對(duì)于原點(diǎn)o的極角為向量p的極角。 p相對(duì)于另外一個(gè)點(diǎn)q的極角是向量p-q的極角。如，例：相對(duì)于(2,4)， 點(diǎn)(3,5)的極角為向量(1,1)的極角：45（/4） 點(diǎn)(3,3)的極角為向量(-1,1)的極角：315（7/4）opopqpqp 2.凸包的定義 凸包凸包：點(diǎn)集Q的凸包是一個(gè)最小的凸多邊形P，使得Q中的每個(gè)點(diǎn)或者在P的邊界上，或者在P的內(nèi)部，記為CH(Q)。例：如圖所示，p0p12的凸包是p0p=p=p10p12圍成的凸多邊形。其中p0、p1、p3、p10、p12既是CH(Q)的頂點(diǎn)，也是Q中的點(diǎn)。p11p9p8p7p6p5p4

22、p2p10p12p0p1p3點(diǎn)集Q=p0,p1,.,p12及其凸包CH(Q)3. GRAHAM掃描法定義一個(gè)候選點(diǎn)的堆棧S。在S上定義操作TOP(S)：讀取棧頂?shù)狞c(diǎn)，但不取走。NEXT-TO-TOP(S)：返回讀取棧頂下面的點(diǎn)，但不取走。POP(S)：摘除棧頂?shù)狞c(diǎn)PUSH(pi,S)：將點(diǎn)pi壓入棧。Graham掃描算法GRAHAM-SCAN描述如下。過程GRAHAM-SCAN返回時(shí)，堆棧S中從底部頂部，依次是按逆時(shí)針方向排列的CH(Q)中的頂點(diǎn)。GRAHAM-SCAN(Q)GRAHAM-SCAN(Q) let p0 be the point in Q with the minimum y-c

23、oordinate or the leftmost such point in case of a tie. let(p1,p2,.pm) be the remaining points in Q,sorted by polar angle in counterclockwise order around p0(if more than one point has the same angle, remove all but the one that is farthest from p0) PUSH(p0,S) PUSH(p1,S) PUSH(p2,S) for i3 to m do whi

24、le the angle formed by points NEXT-TO-TOP(S),TOP(S), and pi makes a nonleft turn do POP(S) PUSH(pi,S)return S關(guān)于算法的說明1）第1行選取當(dāng)前具有最小y坐標(biāo)的點(diǎn)作為p0。 如果有數(shù)個(gè)這樣的點(diǎn)，則選取最左邊的點(diǎn)作為p0。 p0是找到的CH(Q)中第一個(gè)頂點(diǎn)：最下、左方的點(diǎn)。如：p11p9p8p7p6p5p4p2p10p12p0p1p32）第2行對(duì)除p0之外的其它點(diǎn)，根據(jù)它們相對(duì)于p0的極角進(jìn)行排序。 Q中每個(gè)點(diǎn)關(guān)于p0的極角（弧度表示）0,)，所以點(diǎn)按照該極角排序后，得到的是這些點(diǎn)按相對(duì)于

25、p0的逆時(shí)針逆時(shí)針方向排序的序列。p11p9p8p6p5p4p10p12p1p3p2p0p7 如果有兩個(gè)或多個(gè)點(diǎn)相對(duì)于p0的極角相同，則除了與p0距離最遠(yuǎn)的點(diǎn)以外，其余的點(diǎn)都可以不考慮，因?yàn)檫@些點(diǎn)都是p0與最遠(yuǎn)點(diǎn)的圖凸組合。 設(shè)，剔除可以被凸組合的點(diǎn)后，除p0外剩余點(diǎn)的數(shù)目為m。p11p9p8p6p5p4p10p12p1p3p2p0p7p53）初始化 首先將p0、p1、p2入棧。 p0、p1、p2的連接關(guān)系如圖所示。p11p9p8p6p5p4p10p12p1p3p2p0p74）循環(huán)的每一步對(duì)點(diǎn)p3、p4.pn依次進(jìn)行處理 凸包頂點(diǎn)的判定條件：按逆時(shí)針方向通過凸包時(shí)，在頂點(diǎn)處應(yīng)該左轉(zhuǎn)。如果發(fā)現(xiàn)在

26、頂點(diǎn)處沒有左轉(zhuǎn)，則該頂點(diǎn)不是凸包頂點(diǎn)，應(yīng)被刪除。p11p9p8p7p6p5p4p2p10p12p0p1p3左轉(zhuǎn)右轉(zhuǎn) 判別對(duì)象：當(dāng)前的棧頂頂點(diǎn)，注：不是pi本身 判別方法:計(jì)算NEXT-TO_TOP(S)TOP(S)pi的夾角方向（叉積計(jì)算），若非左轉(zhuǎn)，從棧頂刪除S，再重復(fù)重復(fù)該過程(while循環(huán))，刪除所有不能左轉(zhuǎn)的點(diǎn)。 最后pi將作為新的凸包頂點(diǎn)壓如棧。p10p11p9p8p7p6p5p4p2p12p0p1p3處理p3時(shí)，p2是S的棧頂例：p11p9p8p7p6p5p4p2p10p12p0p1p3p11p9p8p7p6p5p4p2p10p12p0p1p3p11p9p8p7p6p5p4p2p10p12p0p1p3p11p9p8p7p