算法設計與分析(十)

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

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

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

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

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

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

7、p2,p3)， d2= DIRECTION(p1,p2,p4)， 若d10，d20，且兩者的符號不同，則線段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) )：當dk0時， ON-SEGMENT(pi,pj,pk)判斷pk是否位于線段pipj上： 點pk位于pipj上的充分必要條件是pk落在端點pi和pj之間，包括與端點pi或pj重疊。 如圖： 圖c)是線

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

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

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

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

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

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

17、段的集合，如果找到S中任一對線段相交就返回TRUE；否則，若S中沒有任何線段相交，則返回FALSE。全序T由一棵紅黑樹實現(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í)行過程。每條虛線都是一個事件點處的掃除線，每條掃除線下的線段名排序為for循環(huán)結束時的全序T，在該循環(huán)中，要對各對應的事件點進行處理。當線段c被刪除時，即

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

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

22、p2p10p12p0p1p3點集Q=p0,p1,.,p12及其凸包CH(Q)3. GRAHAM掃描法定義一個候選點的堆棧S。在S上定義操作TOP(S)：讀取棧頂?shù)狞c，但不取走。NEXT-TO-TOP(S)：返回讀取棧頂下面的點，但不取走。POP(S)：摘除棧頂?shù)狞cPUSH(pi,S)：將點pi壓入棧。Graham掃描算法GRAHAM-SCAN描述如下。過程GRAHAM-SCAN返回時，堆棧S中從底部頂部，依次是按逆時針方向排列的CH(Q)中的頂點。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關于算法的說明1）第1行選取當前具有最小y坐標的點作為p0。 如果有數(shù)個這樣的點，則選取最左邊的點作為p0。 p0是找到的CH(Q)中第一個頂點：最下、左方的點。如：p11p9p8p7p6p5p4p2p10p12p0p1p32）第2行對除p0之外的其它點，根據(jù)它們相對于p0的極角進行排序。 Q中每個點關于p0的極角（弧度表示）0,)，所以點按照該極角排序后，得到的是這些點按相對于

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

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