計(jì)算機(jī)算法基礎(chǔ) 第2版 習(xí)題及答案 第12章

PAGE22第12章 計(jì)算幾何基礎(chǔ)給定以下X-Y平面上兩個(gè)向量，求它們的點(diǎn)積和叉積：p1=(4,-6)，p2=(-2,7)p1=(0,8)，p2=(5,-2)解：(a) p1·p2=4-6·-27=- p1′p2=4-2-67=28(b) p1·p2=08·5-2= p1′p2=058-2假設(shè)平面上四個(gè)點(diǎn)p1，p2，p3，p4的坐標(biāo)如下，用叉積判斷線段p1p2和p1=(3,5)，p2=(-4,6)，p3=(-2,-1)和p4=(1,-5)p1=(-1,8)，p2=(5,-1)，p3=(1,6)和p4=(-4,-7)解：(a) p1=(3,5)，p2=(-4,6)，p3=(-2,-1)和p4=(1,-5)d1=(p2–p1)(p3–p1)=x2-x1xd2=(p2–p1)(p4–p1)=x2-x1x4因?yàn)閐10，顯然不共線。又因?yàn)閐1d2>0所以兩線段不相交。pp3p4p2p1O(b) p1=(-1,8)，p2=(5,-1)，p3=(1,6)和p4=(-4,-7)d1=(p2–p1)(p3–p1)=x2-x1x3-xd2=(p2–p1)(p4–p1)=x2-x1x4-x1y2d3=(p4–p3)(p1–p3)=x4-x3x1-d4=(p4–p3)(p2–p3)=x4-x3x因?yàn)閐10，顯然不共線。又因?yàn)閐1d2<0和d3d4<0，所以兩線段相交。pp3p4p2p1O線段p1p2和p3p4相交但不共線有三種情況，即交點(diǎn)不與任何端點(diǎn)重合，交點(diǎn)與其中一個(gè)線段的一個(gè)端點(diǎn)重合，和交點(diǎn)與兩個(gè)線段各有一個(gè)端點(diǎn)重合。書中算法Segment-Intersect不給予分類。請(qǐng)修改書上算法使得每種相交類型得以確定，并指明交點(diǎn)與哪一個(gè)端點(diǎn)或哪兩個(gè)端點(diǎn)重合解： 修改后算法如下，正確性顯然。Modified-Segment-Intersect(p1,p2,p3,p4) //p1p2和d1(p2–p1)(p3–p1)d2(p2–p1)(p4–p1)d3(p4–p3)(p1–p3)d4(p4–p3)(p2–p3)ifd1=d2=0 //p1p2和p3p4共一直線，此時(shí)必有d3 then ifx1=x2 then ifmax{y1,y2}<min{y3,y4}ormax{y3,y4}<min{y1,y2} thenreturnfalse //不相交 elsereturntrue //相交 endif else ifmax{x1,x2}<min{x3,x4}ormax{x3,x4}<min{x1,x2} thenreturnfalse //不相交 elsereturntrue //相交 endif endif else if(d1d2>0)or(d3d4>0) thenreturnfalse //不相交 elsecase //相交 (1)(d1d2<0)and(d3d4<0) return(true,交點(diǎn)不與任何端點(diǎn)重合) (2)(d1d2<0)and(d3=0)and(d40) return(true,交點(diǎn)只與p1重合) (3)(d1d2<0)and(d4=0)and(d30) return(true,交點(diǎn)只與p2重合) (4)(d3d4<0)and(d1=0)and(d20) return(true,交點(diǎn)只與p3重合) (5)(d3d4<0)and(d2=0)and(d10) return(true,交點(diǎn)只與p4重合) (6)(d1=0)and(d3=0) return(true,交點(diǎn)與p1和p3重合) (7)(d1=0)and(d4=0) return(true,交點(diǎn)與p2和p3重合) (8)(d2=0)and(d3=0) return(true,交點(diǎn)與p1和p4重合) (9)(d2=0)and(d4=0) return(true,交點(diǎn)與p2和p4重合) endifendifEnd假設(shè)平面上有三個(gè)點(diǎn)，p1=(x1,y1)，p2=(x2,y2)，p3=(x3,y3)，用叉積表示以這三個(gè)點(diǎn)為頂點(diǎn)的三角形的面積。解： 假如p1，p2，p3是逆時(shí)針方向繞出的三角形的(也就是說，當(dāng)沿這三點(diǎn)前行時(shí)，三角形是在這三條邊左側(cè))，下面的圖(a)表明這個(gè)三角形的面積為p1p2p3=Op1p2+Op2p3-Op1p3=12(p1′p2+p2′p3+p3′p1)。 注意，這里p3′p1是負(fù)值。所以有：p1p2p3=12(x1x2y1y2+x2x容易看出，只要p1，p2，p3是逆時(shí)針方向繞出的三角形的，不論圖中夾角，，之間關(guān)系如何，公式(1)總是對(duì)的。讀者可以用下面圖(b)為例驗(yàn)證。如果p1，p2，p3是順時(shí)針方向繞出的三角形的，那么公式仍然正確，但結(jié)果是個(gè)負(fù)值。另外，不論坐標(biāo)原點(diǎn)O是在三角形外面還是里面，公式(1)和(2)總是對(duì)的。這是因?yàn)槿绻炎鴺?biāo)平移一個(gè)值，公式(2)的值不變:111a+x1a+x2a+x3=111x1x2x=111pp1p3(a)=+p2p1p3(b)=-p2OO平面一個(gè)點(diǎn)p1相對(duì)于以另一點(diǎn)p0為原點(diǎn)的極角(極坐標(biāo)角)就是向量p1-p0在通常的極坐標(biāo)中的角度。例如，點(diǎn)(3,5)相對(duì)于點(diǎn)(2,4)的極角就是向量(3,5)-(2,4)=(1,1)在極坐標(biāo)中的角度，即45或p/4，而點(diǎn)(3,3)相對(duì)于點(diǎn)(2,4)的極角是向量(1,-1)在極坐標(biāo)中的角度，也就是315或7p/4。現(xiàn)在，假設(shè)有一個(gè)n個(gè)點(diǎn)的序列<p1,p2,…,pn>以及另外一點(diǎn)p0，請(qǐng)?jiān)O(shè)計(jì)一個(gè)復(fù)雜度為O(nlgn)的算法把這n個(gè)點(diǎn)按它們相對(duì)于點(diǎn)p0的極角從小到大排序，并且要求用叉積的方法比較兩個(gè)點(diǎn)的極角而不是實(shí)際算出它們的極角。我們假定，沒有一個(gè)點(diǎn)與點(diǎn)p0重合。解：算法的步驟解釋如下：我們先計(jì)算v1=p1-p0，v2=p2-p0，…，vn=pn-p0。然后，把v1，v2，…，vn按它們?cè)谕ǔO坐標(biāo)中的角度進(jìn)行排序。我們用angle(v)表示點(diǎn)v的極角，X(v)和Y(v)表示點(diǎn)v的X-坐標(biāo)和Y-坐標(biāo)。假設(shè)p1=(x1,y1)，p2=(x2,y2)是其中兩個(gè)點(diǎn)，我們知道，如果p1p2>0，p2是在p1的逆時(shí)針方向上，那么，我們能否講angle(p2)>angle(p1)呢？不一定，這個(gè)結(jié)論成立當(dāng)且僅當(dāng)|angle(p2)-angle(p1)|<180°。下面圖解釋了這個(gè)關(guān)系。所以，在我們的算法中，我們先把各點(diǎn)按它們的Y-坐標(biāo)分組:Y-坐標(biāo)等于零并且角度為0的點(diǎn)歸入第一組，Y-坐標(biāo)大于零的點(diǎn)為第二組，Y-坐標(biāo)等于零并且角度為180的點(diǎn)歸入第三組，Y-坐標(biāo)小于零的點(diǎn)為第四組。這樣一來，各組中任兩點(diǎn)的角度差都小于180°，我們只需把第二和第四組中點(diǎn)排序后，把四個(gè)組順序連上即可。對(duì)各組中的點(diǎn)排序可以用任何一個(gè)復(fù)雜度為O(nlgn)的比較排序算法，例如合并排序。我們只要改動(dòng)Merge部分中一行即可，即把A[i]B[j]改為叉積A[i]B[j]0，并假定數(shù)組A和B是點(diǎn)的序列而不是數(shù)字序列。我們把這個(gè)排序算法稱為Modified-Merge-Sort，細(xì)節(jié)省略。p1p2>0時(shí)兩點(diǎn)極坐標(biāo)角度的關(guān)系 算法的偽碼如下，復(fù)雜度顯然為O(nlgn)。Angle-Sort(p0,p[1..n],G[1..n]) //G[1..n]是輸出序列fori?1ton vi=pi-p0endforG1?G2?G3?G4??fori?1ton ifY(vi)=0 //點(diǎn)vi的Y坐標(biāo) then ifX(vi)>0 //點(diǎn)vi的X坐標(biāo) thenG1?G1è{v elseG3?G3è{v endif else ifY(vi)>0 thenG2?G2è{v elseG4?G4è{v endif endifendforModified-Merge-Sort(G2)Modified-Merge-Sort(G4)G[1..n]G1G2G3G4 //End設(shè)計(jì)一個(gè)O(n2lgn)的算法以判定平面上n個(gè)不同點(diǎn)中是否有三個(gè)點(diǎn)共線。解： 假設(shè)有三個(gè)點(diǎn)共線并有順序a、b、c，那么點(diǎn)b和點(diǎn)c相對(duì)于點(diǎn)a的極角相等。所以，如果我們把點(diǎn)a以外的n-1個(gè)點(diǎn)按相對(duì)于a的極角排序的話，一定會(huì)發(fā)現(xiàn)點(diǎn)b和點(diǎn)c相對(duì)于點(diǎn)a的極角相等。根據(jù)第5題的答案，這個(gè)排序需時(shí)O(nlgn)。但是，怎樣才能找到a呢？一個(gè)簡(jiǎn)單方法就是把每個(gè)點(diǎn)都當(dāng)成a來試一下，總能把a(bǔ)找到。這樣的話，總共需要O(n2lgn)時(shí)間。假設(shè)這n個(gè)點(diǎn)存放在集合S中，這個(gè)算法的偽碼如下：Three-Co-linear(S，n)foreachvS p0?v p[1..n-1]?S–{v} Angle-Sort(p0，p[1..n-1]，G[1..n-1]) //調(diào)用第5題中算法 fori?1ton-2 if(G[i]-p0)(G[i+1]-p0)=0 thenreturn(yes，p0，G[i]，G[i+1]) endif endforendforreturn(No)End設(shè)計(jì)一個(gè)時(shí)間為O(nlgn)的算法來判定一個(gè)n個(gè)頂點(diǎn)的多邊形是個(gè)簡(jiǎn)單多邊形。為簡(jiǎn)單起見，假設(shè)沒有垂直于X軸的邊。解： 我們只要檢查這個(gè)多邊形的n個(gè)邊，除相鄰兩條邊有共同端點(diǎn)外，互相不相交即可。設(shè)這個(gè)多邊形的n個(gè)點(diǎn)的集合是V={v1，v2，…，vn)。假設(shè)這個(gè)多邊形的n個(gè)邊對(duì)應(yīng)的線段是:e1=(u1，w1)，e2=(u2，w2)，…，en=(un，wn)，并假定ui是ei的左端點(diǎn)，wi是ei的右端點(diǎn)(1in)。因沒有垂直于X軸的邊，可假設(shè)ui的X坐標(biāo)X(ui)小于wi的X坐標(biāo)X(wi)，X(ui)<X(wi)(1in)。我們用平掃線方法去判定有無(wú)線段相交。如第12.2.1節(jié)討論的，我們先把2n個(gè)端點(diǎn)從左到右排序成事件點(diǎn)調(diào)度L[1..2n]。為了敘述的方便，我們用L[k]=ui表示事件點(diǎn)L[k](1k2n)是邊ei的左端點(diǎn)，用L[k]=wi表示L[k]是邊ei的右端點(diǎn)，用V(L[k])=vj表示L[k]是集合V中頂點(diǎn)vj。顯然，從L[k]可確定該事件點(diǎn)是哪個(gè)邊的左端點(diǎn)，或哪個(gè)邊的右端點(diǎn)，以及V中哪個(gè)頂點(diǎn)，并且只需O(1)時(shí)間。我們注意到，如果這個(gè)多邊形是個(gè)簡(jiǎn)單多邊形的話，V中每一個(gè)頂點(diǎn)出現(xiàn)在事件點(diǎn)調(diào)度L[1..2n]中正好兩次，否則不是簡(jiǎn)單多邊形。我們把第12.2.2節(jié)的平掃線方法稍作改動(dòng)，來判斷這個(gè)多邊形的n條邊有無(wú)相交。詳細(xì)算法如下。改動(dòng)之處，有注解說明。Simple-Polygon(S,n) //S是n個(gè)線段的集合T //建一個(gè)空的紅黑樹。按第12.2.1節(jié)討論以及上面的解釋，把2n個(gè)端點(diǎn)從左到右排序成事件點(diǎn)調(diào)度L[1..2n]fork1to2n-2 ifV(L[k])=V(L[k+1])=V(L[k+2]) thenreturn(notsimple) //這一步查有無(wú)三個(gè)端點(diǎn)重合 endifendforfork1to2n-2 //最后兩端點(diǎn)不需查 ifL[k]=ui then sei //L[k]是邊ei的左端點(diǎn)ui Insert(T,s) ifAbove(T,s)existsandAbove(T,s)=ej then if(ujui)and(wjui)and(ejintersectsei) thenreturn(notsimple) endif endif ifBelow(T,s)existsandBelow(T,s)=ej then if(ujui)and(wjui)and(ejintersectsei) thenreturn(notsimple) endif endif endif ifL[k]=wi //L[k]是邊ei的右端點(diǎn)wi then sei ifAbove(T,s)existsandAbove(T,s)=ej then ifBelow(T,s)existsandBelow(T,s)=eh thenif(wjwh)and(ejintersectseh) thenreturn(notsimple) endif //只有ej和eh右端點(diǎn)有可能重疊 endif Delete(T,s) endifendforreturn(simple)End算法第2步的排序需要O(nlgn)時(shí)間，第3行的for循環(huán)需要O(n)時(shí)間，第8行的for循環(huán)需要執(zhí)行O(n)次紅黑樹的插入或刪除操作，而每次紅黑樹的操作需要O(lgn)時(shí)間，所以，算法的復(fù)雜度是O(nlgn)。一個(gè)園盤就是一個(gè)園心和半徑定義的一個(gè)園再加上它的內(nèi)部，即由該園所包圍的點(diǎn)集。兩個(gè)園盤如果有任何公共點(diǎn)，則稱為相交。設(shè)計(jì)一個(gè)復(fù)雜度為O(nlgn)的算法以確定在n個(gè)給定的園盤中是否有兩個(gè)園盤相交。解： 假設(shè)我們用(p,r)代表一個(gè)園盤，這里p是該園盤的園心點(diǎn)而r是其半徑。如下圖(a)所示，園盤(p1,r1)和園盤(p2,r2)相交當(dāng)且僅當(dāng)|p2-p1|=(x1-x2)2+(y1-y2)2￡r1+r2。這里，p1=(x1,y1)，p2=(x2,我們用平掃線的方法來尋求答案。設(shè)園盤(p,r)的園心p有坐標(biāo)p=(x,y)，我們用它的平行于X軸的直徑(一個(gè)線段)來表示這個(gè)園，它的左端點(diǎn)為u=(x-r,y)，而右端點(diǎn)為v=(x+r,y)。我們假定對(duì)應(yīng)于這n個(gè)園盤的直徑的線段為D1=(u1,v1)，D2=(u2,v2)，…，Dn=(un,vn)。我們把這2n個(gè)端點(diǎn)按X坐標(biāo)由小到大排序。如果有多個(gè)端點(diǎn)有相同的X坐標(biāo)，那么左端點(diǎn)排在右端點(diǎn)前面。如果有多個(gè)右端點(diǎn)或左端點(diǎn)有相同的X坐標(biāo)，那么有較小Y坐標(biāo)的點(diǎn)排在前面。我們假定沒有兩端點(diǎn)同時(shí)有相同的X坐標(biāo)和Y坐標(biāo)，因?yàn)檫@表示兩個(gè)園盤相交。這2n個(gè)端點(diǎn)稱為事件點(diǎn)，并用X(v)表示事件點(diǎn)v的X坐標(biāo)。當(dāng)平掃線l從左到右經(jīng)過每個(gè)事件點(diǎn)v時(shí)，我們檢查和更新它的狀態(tài)，這里，狀態(tài)指的是按Y坐標(biāo)從大到小排好序的所有與l相交的直徑的序列。我們的算法與書中第12.2.2節(jié)的確定線段相交的算法類似，具體操作如下：如果v是某直徑D的左端點(diǎn)時(shí)，把D插入到當(dāng)前的狀態(tài)中，并檢查狀態(tài)中與v相鄰的直徑對(duì)應(yīng)的園盤是否與D所對(duì)應(yīng)的園盤相交。當(dāng)v是直徑D的右端點(diǎn)時(shí)，把D從當(dāng)前的狀態(tài)中刪去并檢查狀態(tài)中與v相鄰的上下兩直徑對(duì)應(yīng)的園盤是否相交。算法的偽碼如下：Disk-Intersect(S,n) //S是n個(gè)園盤的集合T?? //平掃線初始狀態(tài)為空，紅黑樹初始為空計(jì)算n個(gè)直徑并將2n個(gè)端點(diǎn)按X坐標(biāo)排序?yàn)閜[1..2n] //假定沒有兩端點(diǎn)重合fori1to2n ifp[i]是某直徑D的左端點(diǎn) then Insert(T,D) //把D插入平掃線狀態(tài) if(Above(T,D)existsandintersectsD) //指對(duì)應(yīng)園盤相交 thenreturntrue,D,Above(T,D) endif if(Below(T,D)existsandintersectsD) thenreturntrue,D,Below(T,D) endif else //p[i]是某直徑D的右端點(diǎn) ifAbove(T,D)andBelow(T,D)existandintersect thenreturntrue,Above(T,D),Below(T,D) endif Delete(T,D) endifendforreturnfalseEnd和書上一樣，我們用紅-黑樹作為T的數(shù)據(jù)結(jié)構(gòu)，這個(gè)算法的復(fù)雜度為O(nlgn)。至于它的正確性，我們只需證明，如果兩園盤相交，一定會(huì)報(bào)告相交。下面我們證明，如果兩園盤相交，一定會(huì)在平掃線的某狀態(tài)中有兩個(gè)相鄰直徑所對(duì)應(yīng)的園盤相交。因?yàn)樗惴z查每個(gè)平掃線的狀態(tài)中所有相鄰直徑所對(duì)應(yīng)的園盤是否相交，所以一定會(huì)報(bào)告相交。假設(shè)兩相交園盤各有直徑D1=(u1,v1)和D2=(u2,v2)，不失一般性，設(shè)Y(u2)Y(u1)。那么在點(diǎn)u1的平掃線會(huì)穿過D2或者在點(diǎn)u2的平掃線會(huì)穿過D1。不失一般性，設(shè)在點(diǎn)u1的平掃線穿過D2，交點(diǎn)為y。我們分兩種情況討論：點(diǎn)u1在園盤D2內(nèi)，如下圖(a)所示。這時(shí)平掃線在點(diǎn)u1的狀態(tài)中，如果D1和D2相鄰，則正確性得證。否則，在點(diǎn)u1的狀態(tài)中必有在D1和D2之間的直徑，其中必有一個(gè)直徑D與D2相鄰。因?yàn)橹睆紻出現(xiàn)在點(diǎn)u1的狀態(tài)中，那么直徑D必與線段u1y相交，因而它對(duì)應(yīng)的園盤與園盤D2相交，因此，算法會(huì)報(bào)告相交。這里，y是平掃線與D2的點(diǎn)u1不在園盤D2內(nèi)，如下圖(b)所示。這時(shí)線段u1y與D2的園周相交于點(diǎn)z。設(shè)點(diǎn)w是園盤D1與D2相交的最左邊點(diǎn)。這時(shí)平掃線在點(diǎn)u1的狀態(tài)中，如果D1和D2相鄰，則正確性得證。否則，在點(diǎn)u1的狀態(tài)中必有在u1和u2之間的直徑，它們或與線段zy相交，或與u1z相交。如果有直徑與線段zy相交，那么與D2相鄰的那個(gè)直徑對(duì)應(yīng)的園盤與園盤D2相交，正確性得證。如果沒有直徑與線段zy有直徑D與u1z相交但都不在三角形u1wz中終止。那么它們必定與園盤D1或D2相交。所以與D1或D2相鄰的直徑中必有一個(gè)與D1或D2有直徑D與u1z相交并在三角形u1wz中終止的。如圖(b)所示，也許還有兩個(gè)端點(diǎn)都包含在三角形u1wz中的直徑。設(shè)x是在這些直徑中最右邊的一個(gè)端點(diǎn)的X坐標(biāo)。那么在平掃線到達(dá)點(diǎn)x并更新在點(diǎn)x的狀態(tài)時(shí)，要么算法已經(jīng)報(bào)告有園盤相交，要么把最后一個(gè)端點(diǎn)在x的直徑刪去后，D1和D2相鄰。uu1D1v2D2v1u2平掃線zwDy(b) 直徑D1左端點(diǎn)u1不在園盤D2內(nèi)v2D2u1D1v1yu2平掃線(a) 直徑D1左端點(diǎn)u1在園盤D2內(nèi)兩園盤相交時(shí)的兩種情況圖示假設(shè)線段a和b在點(diǎn)x可比較，a和b都不垂直于X軸并且它們也不相交。下面的圖給出了一個(gè)例子。請(qǐng)?jiān)O(shè)計(jì)一個(gè)程序在O(1)時(shí)間內(nèi)確定是a>xb還是b>xa。解： 已知a和b不相交并且都和直線x相交，我們可假定a的兩端點(diǎn)為p1=(x1,y1)和p2=(x2,y2)，并且x1￡x￡x2，而b的兩端點(diǎn)為p3=(x3,y3)和p4=(x4,y4)，并且x3￡x￡x4。偽碼如下：Above(p1,p2,p3,p4) d1?(p2–p1)′(p3–p1)d2?(p2–p1)′(p4–p1)d3?(p4–p3)′(p1–p3)d4?(p4–p3)′(p2–p3)if(d1<0andd2<0) //p1p3和p1p4同在 or(d3>0andd4>0) //或者p3p1和p3p2 thena>xb elseb>xaendifEnd另外一個(gè)辦法是把兩線段與垂直線x的交點(diǎn)算出來后做比較。某教授建議用下面的算法決定一個(gè)n個(gè)頂點(diǎn)的序列<p0，p1，…，pn-1>是否是一個(gè)凸多邊形的連續(xù)頂點(diǎn)：如果集合{Dpipi+1pi+2|i=0,1,…,n-1}不同時(shí)含有左拐和右拐，那么回答是，否則回答不是。這里對(duì)足標(biāo)的加法是以n為模加法，即和數(shù)大于等于n時(shí)，除以n后取余數(shù)。請(qǐng)證明，這個(gè)算法雖然是個(gè)線性算法，但不能始終得到正確答案。請(qǐng)修改這個(gè)算法使其始終能在線性時(shí)間內(nèi)得到正確答案。解： 下面的圖顯示了一個(gè)反例。集合{Dpipi+1pi+2|i=0,1,…,n-1}不同時(shí)含有左拐和右拐是個(gè)必要條件但不充分。我們需要加上一些額外條件才行。讓我們假設(shè)集合{Dpipi+1pi+2|i=0,1,…,n-1}不含有右拐。對(duì)于不含左拐的情形可對(duì)稱處理。我們注意到，如果序列<p0，p1，…，pn-1>是一個(gè)凸多邊形的連續(xù)頂點(diǎn)，那么，任一個(gè)子序列，<p0，p1，…，pi>(2in-1)，也必定構(gòu)成一個(gè)凸多邊形。當(dāng)i=2時(shí)，<p0，p1，p2>顯然是一個(gè)凸多邊形(三角形)。我們要探討的是，如果子序列，<p0，p1，…，pi>(2in-2)，構(gòu)成一個(gè)凸多邊形，那么點(diǎn)pi+1需要滿足什么條件使子序列<p0，p1，…，pi，pi+1>也構(gòu)成一個(gè)凸多邊形？從下面的圖中可以看出這個(gè)額外條件是：Dpipi+1p0和Dpi+1p0p1必須不向右拐。綜上所述，n個(gè)頂點(diǎn)的序列<p0，p1，…，pn-1>是一個(gè)凸多邊形的連續(xù)頂點(diǎn)的條件是：集合{Dpipi+1pi+2|i=0,1,…,n-1}{Dpipi+1p0|i=2,3,…,n-2}{Dpi+1p0p1|i=3,4,…,n-2}不同時(shí)含右拐和左拐。因?yàn)闄z查一個(gè)角度是左拐還是右拐只需O(1)時(shí)間，這個(gè)修改后的算法仍然只需O(n)時(shí)間。給定平面上一點(diǎn)p0=(x0,y0)，以這點(diǎn)為起點(diǎn)的右水平射線(righthorizontalray)，R(p0)，是從p0開始的與X軸平行的半條直線，即R(p0)={(x,y)|y=y0，xx0}。請(qǐng)用判斷線段相交的方法在O(1)時(shí)間判斷一個(gè)線段p1p2是否與R(p0解： 下圖顯示了線段p1p2與R(p0)假定交點(diǎn)在(x,y0)，那么必有x0￡x￡max(x1,x2)。記x’=max(x1,x2)，那么點(diǎn)p=(x’,y0)是R(p0)上一點(diǎn)。線段p1p2與R(p0)的交點(diǎn)就是p1p2與p0p的交點(diǎn)。所以判斷線段p1pIntersect(p0,p1,p2) //p0=(x0,y0),p1=(x1,y1),p2=(x2,y2)x’max(x1,x2)p(x’,y0)ifSegment-Intersect(p0,p,p1,p2)=true thenreturntrue elsereturnfalseendifEnd注意，有可能x’<x0，這時(shí)p1p2不可能與R(p0)相交，也不會(huì)與假設(shè)一多邊形的頂點(diǎn)按反時(shí)針方向的順序是áp1,p2,…,pn?，這里pi=(xi,yi)(1￡i￡n)。假設(shè)這個(gè)多邊形是一個(gè)凸多邊形，設(shè)計(jì)一個(gè)O(n)算法來判斷點(diǎn)p0=(x0,y0)是否在這個(gè)多邊形內(nèi)部(在邊界上的點(diǎn)不算在內(nèi)部)。為簡(jiǎn)單起見，我們假定x01xi(1￡i￡n)和y01yi(1￡i￡n)。假設(shè)這個(gè)多邊形是個(gè)簡(jiǎn)單多邊形，但不一定是凸多邊形，其他同(a)，重做(a)部分問題。解: (a) 我們只需要檢查pip0是否是在pipi+1左邊(1￡i￡n-1)以及p偽碼如下：Convex-Inclusion(p[1..n],p0)fori?1ton-1 if(pi+1–pi)′(p0–pi)0 thenreturn(notinside) endifendforif(p1–pn)′(p0–pn)0 thenreturn(notinside) elsereturn(yes,inside)endifEnd(b) 考慮一條從p0開始的右水平射線(定義見題11)。點(diǎn)p0在多邊形內(nèi)當(dāng)且僅當(dāng)R(p0)與該多邊形的奇數(shù)條邊相交。因?yàn)榧俣▂0yi(1≤i≤n)，邊pipi+1與R(p0)相交必有yi<y0<yi+1或者yi+1<y0<yi。這里，i+1=(imod(b.1) 如果yi<y0<yi+1，那么pipi+1與R(p0)相交當(dāng)且僅當(dāng)pip0(b.2) 如果yi+1<y0<yi，那么pipi+1與R(p0)相交當(dāng)且僅當(dāng)pip0根據(jù)以上分析，偽碼如下：Simple-Polygon-Inclusion(p[1..n],p0) //頂點(diǎn)序列可以是反時(shí)針或正時(shí)針方向c?0 //記錄相交次數(shù)fori?1ton j(imodn)+1 if(yi<y0<yj)and(pj–pi)′(p0–pi)>0 thenc?c+1 elseif(yj<y0<yi)and(pj–pi)′(p0–pi)<0 thenc?c+1 endif endifendforifcmod2=1 thenreturn(Yes,inside) elsereturn(No,notinside)endifEnd*假設(shè)一個(gè)簡(jiǎn)單多邊形的逆時(shí)針方向的頂點(diǎn)序列是<p0，p1，…，pn-1>。請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(n)的算法來計(jì)算這個(gè)多邊形所圍的面積。注意，這個(gè)多邊形不一定是凸多邊形。解： 因?yàn)樽鴺?biāo)平移不影響面積，我們可假定原點(diǎn)在多邊形內(nèi)部。下圖(a)顯示，如果這個(gè)多邊形是個(gè)凸多邊形，那么，其所圍的面積等于一系列三角形面積相加。但是，如果這個(gè)多邊形不是個(gè)凸多邊形，那么，如下圖(b)顯示，其所圍的面積等于一系列三角形面積的代數(shù)和，其正負(fù)號(hào)正好等于對(duì)應(yīng)叉積的正負(fù)號(hào)。所以這個(gè)多邊形所圍的面積有如下公式：面積S=12i=0n-1(pioop0p1一p2p3p4(b) 非凸多邊形情形op0p1p2p3p4(a) 凸多邊形情形p5算法的偽碼如下：Polygon-Area(p0,p1,…,pn-1)s0fori1ton-1 ss+12returnsEnd注意，不論原點(diǎn)在哪里，在多邊形內(nèi)部或外部，這個(gè)面積公式S=12i=0n-1(pi×pi+1modn)都是正確的。這是因?yàn)?，如果我們把原點(diǎn)平移到任何位置，相當(dāng)于把每一個(gè)頂點(diǎn)pi=(xi,yi)(0in-1)平移到pi’=(xi+a,yi+b)，這里，a和b可以是任意實(shí)數(shù)。下面我們證明，i=0n-1(pii=0n-1(pi=i=0n-1x=i=0n-1xixi+1y=i=0n-1xixi+1yi=i=0n-1xixi+1yiy=i=0n-1xixi+1=i=0n-1xix=i=0=i=0n-1假設(shè)點(diǎn)q是一個(gè)簡(jiǎn)單多邊形P的邊界上一點(diǎn)，如果線段qr上所有點(diǎn)都在P的內(nèi)部或邊界上，那么點(diǎn)r稱為q的一個(gè)陰影點(diǎn)。點(diǎn)q的所有陰影點(diǎn)的集合稱為q的陰影(Shadow)。如果P中存在一個(gè)點(diǎn)p，它是所有P的邊界上點(diǎn)的陰影點(diǎn)，那么這個(gè)點(diǎn)p稱為是P的核心點(diǎn)，而P被稱為一個(gè)星形多邊形(star-shaped)。所有核心點(diǎn)的集合稱為核心(kernel)。下圖給出了星形多邊形和非星形多邊形例子。假設(shè)P是一個(gè)n個(gè)頂點(diǎn)的星形多邊形，它的逆時(shí)針方向的頂點(diǎn)序列是<p0,p1,…,pn-1>。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n)算法計(jì)算它的凸包CH(P)。星形多邊形示例解： 下面這個(gè)算法與Graham掃描法相似。不同處是，這個(gè)算法不用極角排序而是直接用給定的頂點(diǎn)序列。不失一般性，假設(shè)p0是Y坐標(biāo)最小的頂點(diǎn)。如果有幾個(gè)這樣的點(diǎn)，則取有最小X坐標(biāo)的一個(gè)點(diǎn)為p0。顯然，p0必定是CH(P)中一個(gè)點(diǎn)?，F(xiàn)在，假設(shè)P的逆時(shí)針方向的頂點(diǎn)序列是<p0，p1，…，pn-1>。算法的偽碼如下：Convex-Hull-Star-Shaped-Polygon(p[0..n-1])//InitializationS //堆棧清空Push(S,p0)Push(S,p1) //初始化完成fori2ton(modn) qTop(S) pNext-to-top(S) while(q–p)(pi–p)0 //由點(diǎn)p到點(diǎn)q后，再到點(diǎn)pi時(shí)，不向左拐 Pop(S) qp pNext-to-top(S) endwhile Push(S,pi)endforreturnSEnd 算法的復(fù)雜度顯然是O(n)，因?yàn)閴簵?dòng)作為n-1次而彈出動(dòng)作少於n-1次。下面證明正確性。因?yàn)镻是一個(gè)星形多邊形，如圖(a)所示，它有一個(gè)核心點(diǎn)p。當(dāng)我們沿著P的逆時(shí)針方向的頂點(diǎn)序列<p0，p1，…，pn-1>移動(dòng)一個(gè)點(diǎn)x時(shí)，因?yàn)閤p在多邊形P內(nèi)部或邊界上，所以由點(diǎn)p和任何一條邊pkpk+1modn(0kn-1)組成的三角形都必定包含在凸包之內(nèi)。顯然，由點(diǎn)p和連續(xù)的兩條邊，pkpk+1和pk+1pk+2modn(0kn-2)組成的四邊形也必定包含在凸包里。因此，當(dāng)點(diǎn)x沿著邊pkpk+1移動(dòng)到點(diǎn)pk+1時(shí)，如果轉(zhuǎn)到邊pk+1pk+2modn上去時(shí)向右轉(zhuǎn)，那么，如圖(a)所示，點(diǎn)pk+1一定在由點(diǎn)p,點(diǎn)pk和點(diǎn)pk+2組成的三角形內(nèi)部。因此，點(diǎn)pk+1注意，p0在堆棧中頭尾各出現(xiàn)一次。另外，如果多邊形不是星形多邊形，這個(gè)算法可能出錯(cuò)，下圖(b)給出了這樣一個(gè)例子。在用分治法計(jì)算最近點(diǎn)對(duì)的算法中，在分治法合(combine)的過程中，我們?yōu)閿?shù)組Y*中每個(gè)點(diǎn)檢查7個(gè)與之相鄰的點(diǎn)。請(qǐng)證明實(shí)際上只需檢查5個(gè)與之相鄰的點(diǎn)即可。證明： 因?yàn)樵跁袌D12-14所示的2矩陣中最多可以有8個(gè)點(diǎn)，所以與任一個(gè)點(diǎn)距離小于的點(diǎn)最多是7個(gè)。但是，這8個(gè)點(diǎn)中有兩個(gè)點(diǎn)與其他兩個(gè)點(diǎn)重合。如果不算重合的點(diǎn)，只有6個(gè)不重合的點(diǎn)。所以，如果沒有重合的點(diǎn)，那么只需檢查5個(gè)與之相鄰的點(diǎn)即可。那么，如果有重合的點(diǎn)，檢查5個(gè)與之相鄰的點(diǎn)能行嗎？答案是沒有問題。這是因?yàn)?，如果有兩點(diǎn)重合，那么在檢查到這兩個(gè)重合點(diǎn)時(shí)，它們的Y-坐標(biāo)相等，從圖12-14可知，Y坐標(biāo)相等的點(diǎn)最多有4個(gè)，因此，一定在3個(gè)與之相鄰的點(diǎn)中會(huì)發(fā)現(xiàn)有兩點(diǎn)重合而得到=0。*假設(shè)一個(gè)凸多邊形P的反時(shí)針方向的頂點(diǎn)序列是<p0，p1，…，pn-1>(n3)。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n)的算法找出P的直徑，即最大的兩頂點(diǎn)間距離。解： 假設(shè)di是頂點(diǎn)pi(0in-1)和其他頂點(diǎn)間最大距離，那么P的直徑為max0≤i≤n-1{di}。但是，如果計(jì)算每一個(gè)頂點(diǎn)和pi的距離，則需要(n)時(shí)間得到di，從而需要(n2)時(shí)間得到P的直徑。下面介紹一個(gè)快速方法。我們想象把P沿著水平初始化：在滾動(dòng)開始時(shí)，設(shè)線段p0p1與水平底線置全局變量diameter=0。直徑兩端u，v暫無(wú)定義，即unil，vnil。變量diameter記錄當(dāng)前發(fā)現(xiàn)的頂點(diǎn)間最大距離。用下面算法，尋找下標(biāo)最小，但在線段p0p1的垂直平分線左邊的頂點(diǎn)pkk2 while|p0–pk|>|p1–pk| //|p0–pk|表示p0和pk間距離 k(k+1)modn //pk可能等于p2，也可能等于p0endwhile //初始化完成滾動(dòng)中對(duì)每個(gè)事件點(diǎn)的處理：在滾動(dòng)中，頂點(diǎn)p1，…，pn-1會(huì)順序接觸底線，稱為事件點(diǎn)。當(dāng)頂點(diǎn)pj(1jn-1)接觸底線時(shí)，我們計(jì)算頂點(diǎn)pj(2jn-1)和其他頂點(diǎn)間的距離。一旦發(fā)現(xiàn)某距離比全局變量diameter大，則更新這個(gè)全局變量。為了使計(jì)算復(fù)雜度小，我們只計(jì)算有可能大于全局變量的距離。如果頂點(diǎn)pj和某頂點(diǎn)x之間的距離肯定小于最大距離，則跳過不計(jì)算。關(guān)鍵是如何進(jìn)行刪減。如下圖(a)所示，當(dāng)頂點(diǎn)pj(1jn-1)接觸底線時(shí)，如果頂點(diǎn)x在線段pj-1pj的垂直平分線的右側(cè)，則不需計(jì)算pj和x的距離|pj-x|。這是因?yàn)閨pj-x|<|pj-1-x|，它不可能是最大距離。假設(shè)頂點(diǎn)pk是逆時(shí)針方向第一個(gè)在垂直平分線左側(cè)的點(diǎn)，那么從點(diǎn)pk開始，沿逆時(shí)針方向，逐點(diǎn)計(jì)算與點(diǎn)pj的距離，直到頂點(diǎn)ph為止。這里，點(diǎn)ph是從點(diǎn)pk開始，沿逆時(shí)針方向，第一個(gè)頂點(diǎn)使得|pj–ph|<|pj+1–ph|。如下圖(b)所示，這是因?yàn)閺狞c(diǎn)ph開始，所有點(diǎn)都在線段pjpj+1的垂直平分線的左側(cè)pk-1

pk+1

pkp

(a)

pj

ph

pj-1

pk(b)

pj+1

pj-1

pj

pj+1

實(shí)際上，這意味著，新的事件點(diǎn)到來了，點(diǎn)pj+1開始接觸底線，而點(diǎn)ph是是反時(shí)針方向第一個(gè)在pjpj+Diameter(p0，p1，…，pn-1)diameter0 //初始化直徑為0unilvnil //u,v是當(dāng)前找到的最大距離的兩個(gè)端點(diǎn)，暫無(wú)定義k2while|p0–pk|>|p1–pk| k(k+1)modn //pk可能等于p2，也可能等于p0endwhile //初始化完成forj1ton jjmodn while|pj–pk||p(j+1)modn–pk| if|pj–pk|>diameter then diameter|pj–pk| upj vpk endif k(k+1)modn endwhileendforreturn(diameter,u,v)End算法的復(fù)雜度可分析如下。因?yàn)榈?行的for循環(huán)中，j的序號(hào)增長(zhǎng)n次，而序號(hào)k只增不減。因?yàn)樾蛱?hào)k對(duì)應(yīng)的點(diǎn)pk不會(huì)超越點(diǎn)pj，所以，序號(hào)k增加的次數(shù)不會(huì)大於開始與序號(hào)j的距離，再加n次。所以序號(hào)k增加的次數(shù)不會(huì)大於2n。所以第10行的比較次數(shù)總共不會(huì)超過2n次。因?yàn)榈?行開始的for循環(huán)的主要工作是第10行的比較，而每次比較只需O(1)時(shí)間，所以算法的復(fù)雜度為O(n)。第12.2.2節(jié)中用平掃線確定有線段相交的算法Any-Segments-Intersect有兩個(gè)限制要求。一個(gè)是沒有三個(gè)線段相交于一點(diǎn)，另一個(gè)是沒有垂直于X軸的線段。假設(shè)沒有這兩個(gè)限制，當(dāng)線段p1p2垂直于X軸時(shí)，設(shè)p1=(x1,y1)，p2=(x2,y2)，x1=x2，y1y2，我們把點(diǎn)p1當(dāng)做左端點(diǎn)，把點(diǎn)p2當(dāng)做右端點(diǎn)。另外，在決定平掃線在x=x1的狀態(tài)時(shí)，我們把點(diǎn)p1作為平掃線和線段p1p2的交點(diǎn)來和其它線段排序。證明，這樣處理后，即使沒有這兩證明： 當(dāng)算法Any-Segments-Intersect報(bào)告有線段相交時(shí)顯然是正確的，所以我們只需證明，只要有線段相交，算法一定會(huì)報(bào)告true。為此，讓我們假設(shè)集合S中有線段a和b相交于點(diǎn)p，而p的X坐標(biāo)，X(p)，是所有交點(diǎn)中X坐標(biāo)最小的一個(gè)。我們分三種情況討論：線段a和b的左端點(diǎn)均出現(xiàn)在點(diǎn)p的左邊。線段a的左端點(diǎn)出現(xiàn)在點(diǎn)p的左邊，而線段b的左端點(diǎn)與直線x=X(p)相交。線段a和b的左端點(diǎn)均與直線x=X(p)相交。 下圖顯示了這三種情況。 我們證明在這三種情況下，算法都會(huì)報(bào)告有交點(diǎn)。如果線段a和b的左端點(diǎn)均出現(xiàn)在點(diǎn)p的左邊，我們考慮在點(diǎn)p左邊最后一個(gè)事件點(diǎn)q的平掃線狀態(tài)。線段a和b必定包含在點(diǎn)q的平掃線狀態(tài)中。如果a和b在某個(gè)平掃線狀態(tài)中相鄰，那么它們必定被算法檢查過并一定報(bào)告相交。如果a和b在所有平掃線狀態(tài)中不相鄰，那么一定有一條線段d在q點(diǎn)的平掃線狀態(tài)中介于a和b之間。這時(shí)，有下面幾種情況。(a.1)如果線段d的右端點(diǎn)在p點(diǎn)的右邊，但是線段d不與點(diǎn)p相交。這種情況下，線段d必定與a或b相交，這樣一來，點(diǎn)p就不是最左邊的交點(diǎn)了，這不可能。(a.2)如果線段d的右端點(diǎn)在p點(diǎn)的右邊，而且線段d與點(diǎn)p相交。這種情況下，三個(gè)線段，a，b，d交于p點(diǎn)。也許這樣的線段d不止一條，它們都在線段a和b之間并相交于點(diǎn)p。那么，平掃線在點(diǎn)q刪去所有以點(diǎn)q為右端點(diǎn)的線段后，會(huì)發(fā)現(xiàn)線段a，b，以及d這樣的線段中，有兩個(gè)相鄰，從而算法一定會(huì)報(bào)告有線段相交于p點(diǎn)。(a.3) 如果線段d的右端點(diǎn)正好在q點(diǎn)的平掃線上(包括d垂直于X軸的情況)，那么，d的右端點(diǎn)是個(gè)事件點(diǎn)，算法會(huì)在這個(gè)事件點(diǎn)上把線段d刪去而使a和b相鄰并得到相交的結(jié)果。如果a的左端點(diǎn)出現(xiàn)在點(diǎn)p的左邊，而b的左端點(diǎn)與直線x=X(p)相交，那么有兩種情況。(對(duì)稱情況略去。)(b.1) 線段b不垂直于X軸。這種情況下，b的左端點(diǎn)必與交點(diǎn)p重合，并且是一個(gè)事件點(diǎn)。當(dāng)算法對(duì)這個(gè)事件點(diǎn)進(jìn)行操作時(shí)，如果算法還沒有發(fā)現(xiàn)有相交的線段，那么，算法會(huì)把b插入到平掃線狀態(tài)中。并發(fā)現(xiàn)b與a相鄰。顯然，算法會(huì)報(bào)告a和b相交。(b.2)線段b垂直于X軸。這種情況下，b的左端點(diǎn)是一個(gè)事件點(diǎn)。算法在亊件點(diǎn)x=X(p)會(huì)把b插入到平掃線狀態(tài)中。如果b與a相鄰，算法會(huì)報(bào)告a和b相交。如果b與a不相鄰，那么在該點(diǎn)的狀態(tài)序列中，b的左端點(diǎn)一定在點(diǎn)p的下面，并且b的左端點(diǎn)和點(diǎn)p之間有其它線段。因?yàn)檫@些線段都與線段b相交，那么算法會(huì)報(bào)告與b相鄰的那個(gè)線段與b相交。如果線段a和b的左端點(diǎn)均與直線x=X(p)相交，那么線段a和b的左端點(diǎn)都是亊件點(diǎn)。在亊件點(diǎn)x，線段a和b被先后插入。不妨設(shè)a和b的左端點(diǎn)的Y坐標(biāo)分別是Y(a)和Y(b)，并有Y(a)Y(b)。根據(jù)算法，線段a先被插入，有3種情況(對(duì)稱情況略去)。(c.1)線段a和b都不垂直于X軸。這種情況下，a和b的左端點(diǎn)必定相交于點(diǎn)p，那么在插入b時(shí)，如果算法還沒有報(bào)告有相交