算法設(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è)分支，專(zhuān)門(mén)研究解決幾何問(wèn)題的算法。 這一類(lèi)問(wèn)題中，輸入一般是關(guān)于一組幾何對(duì)象的描述，如點(diǎn)、線(xiàn)段、多邊形等。輸入則是對(duì)有關(guān)這些對(duì)象的問(wèn)題的解答，如直線(xiàn)是否相交？是否為一個(gè)新的幾何對(duì)象，如頂點(diǎn)集合的凸包等。 p1p2p4p2計(jì)算幾何學(xué)常見(jiàn)問(wèn)題折線(xiàn)段的拐向判斷判斷點(diǎn)與線(xiàn)、矩形、多邊形、圓之間的相對(duì)位置關(guān)系計(jì)算點(diǎn)到線(xiàn)段、折線(xiàn)、矩形、多邊形的最近點(diǎn)計(jì)算線(xiàn)段、直線(xiàn)與線(xiàn)、矩形、多邊形、圓的交點(diǎn)判斷形狀間的包含，如一個(gè)矩形是否在另

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

3、1+(1-a)p2。 p1,p2,p3的相對(duì)位置關(guān)系如圖： 亦即，p3位于穿過(guò)p1和p2的直線(xiàn)上、并處于p1和p2之間（包括p1和p2兩點(diǎn)）的任意點(diǎn)。而線(xiàn)段p1p2可以看作是p1和p2的凸組合的集合p1p3p2這里， 稱(chēng)p1、p2是線(xiàn)段的p1p2的端點(diǎn)。 如果考慮有向性，可以記有向線(xiàn)段為p1p2。 如果p1是原點(diǎn)(0,0)，則有向線(xiàn)段p1p2簡(jiǎn)稱(chēng)為向量向量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)來(lái)說(shuō)，p1在p2的順 時(shí)針?lè)较蛏希?如果p1p2為負(fù)數(shù)，則p1在p2的逆時(shí)針?lè)较蛏希?下圖示出向量p的順時(shí)針區(qū)域和逆時(shí)針區(qū)域。 如果叉積為0的話(huà)，則p1、p2共線(xiàn)，p1、p2指向同一個(gè)方向 或相反的方向。p(0,0)xyp1p2(0,0)p1p2(0,0)p的逆時(shí)針?lè)较騪的順時(shí)針?lè)较騪1、p2同向共線(xiàn)p1、p2逆向共線(xiàn)如何判斷線(xiàn)段之間的相對(duì)方向？ 已知兩個(gè)有公共端點(diǎn)p0的有向線(xiàn)段p0p1、p0p2，計(jì)算叉積： (p1-p0)(p2-p0)=(x1-x0)(y2-y0)-(x2-x0)(y1-y0) 若0，則p0p1在p0p2的順時(shí)針

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

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

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

8、段相交的情形，而圖d)中的兩個(gè)線(xiàn)段 并不相交。p1p2p3p4c)p1p2p3p4d)3）定義過(guò)程 SEGMENTS-INTERSECT(pSEGMENTS-INTERSECT(p1 1,p,p2 2,p,p3 3,p,p4 4) )： 布爾函數(shù)，判斷線(xiàn)段p1p2和p3p4是否相交，相交，則返回TRUE，否則返回FALSE。4）過(guò)程的描述如下： 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分析： 上述問(wèn)題也可以按照通常的解析幾何的方法求解，如計(jì)算出形如y=kx+b的直線(xiàn)方程，然后求直線(xiàn)交點(diǎn)，然后檢查交點(diǎn)是否落在線(xiàn)段的端點(diǎn)之間，判定線(xiàn)段的相交性。 我們的算法僅使用加、減、乘和比較運(yùn)算就完成了計(jì)算，沒(méi)有使用除法，不需要三角函數(shù)計(jì)算。優(yōu)點(diǎn)：除法、三角函數(shù)的計(jì)算代價(jià)都很高除法的舍入誤差問(wèn)題近似平行線(xiàn)時(shí)，求斜率k對(duì)計(jì)算機(jī)除法運(yùn)算的精度非常敏感，很容易產(chǎn)生溢出問(wèn)題等。10.2 確定任意一對(duì)線(xiàn)段是否相交 對(duì)給定的一組線(xiàn)段，確定其中任意兩個(gè)線(xiàn)段是否相交？ 這里假設(shè)： 1）所有的線(xiàn)段不垂直的（水平的可以）。 2）相交于同一點(diǎn)的線(xiàn)段

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

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

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

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

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

17、段的集合，如果找到S中任一對(duì)線(xiàn)段相交就返回TRUE；否則，若S中沒(méi)有任何線(xiàn)段相交，則返回FALSE。全序T由一棵紅黑樹(shù)實(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í)行過(guò)程。每條虛線(xiàn)都是一個(gè)事件點(diǎn)處的掃除線(xiàn)，每條掃除線(xiàn)下的線(xiàn)段名排序?yàn)閒or循環(huán)結(jié)束時(shí)的全序T，在該循環(huán)中，要對(duì)各對(duì)應(yīng)的事件點(diǎn)進(jìn)行處理。當(dāng)線(xiàn)段c被刪除時(shí)，即

20、可發(fā)現(xiàn)線(xiàn)段d和b相交。10.3 凸包問(wèn)題1.關(guān)于多邊形的概念1）多邊形：是平面上一組首尾相連的折線(xiàn)段所構(gòu)成的封閉曲線(xiàn)稱(chēng)為多邊形。2）邊：構(gòu)成多邊形的折線(xiàn)段稱(chēng)為多邊形的邊。3）頂點(diǎn)：連接兩條連續(xù)邊的點(diǎn)稱(chēng)為頂點(diǎn)。邊頂點(diǎn)4）簡(jiǎn)單多邊形：內(nèi)部沒(méi)有交叉的多邊形稱(chēng)為簡(jiǎn)單多邊形。 非簡(jiǎn)單多邊形 簡(jiǎn)單多邊形 對(duì)一個(gè)簡(jiǎn)單多邊形，內(nèi)部包圍的區(qū)域稱(chēng)為該多邊形的內(nèi)部?jī)?nèi)部；多邊形的邊構(gòu)成邊界邊界；邊界以外的區(qū)域稱(chēng)為多邊形的外部外部。外部?jī)?nèi)部邊界凸多邊形：一個(gè)簡(jiǎn)單多邊形，如果給定其邊界上或內(nèi)部 的任意兩點(diǎn)，連接這兩個(gè)點(diǎn)的線(xià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描述如下。過(guò)程GRAHAM-SCAN返回時(shí)，堆棧S中從底部頂部，依次是按逆時(shí)針?lè)较蚺帕械腃H(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)于算法的說(shuō)明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í)針?lè)较蚺判虻男蛄?。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í)針?lè)较蛲ㄟ^(guò)凸包時(shí)，在頂點(diǎn)處應(yīng)該左轉(zhuǎn)。如果發(fā)現(xiàn)在

26、頂點(diǎn)處沒(méi)有左轉(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ù)該過(guò)程(while循環(huán))，刪除所有不能左轉(zhuǎn)的點(diǎn)。 最后pi將作為新的凸包頂點(diǎn)壓如棧。p10p11p9p8p7p6p5p4p2p12p0p1p3處理p3時(shí)，p2是S的棧頂例：p11p9p8p7p6p5p4p2p10p12p0p1p3p11p9p8p7p6p5p4p2p10p12p0p1p3p11p9p8p7p6p5p4p2p10p12p0p1p3p11p9p8p7p