第五章-圖形運(yùn)算

第五章---圖形運(yùn)算第一頁，共76頁。若兩線段相交,則交點(diǎn)的參數(shù)值,應(yīng)滿足:即第一頁第二頁，共76頁。因此,若行列式

表示兩線段AB和CD重合或平行。一般做為它們不相交來處理。如果≠0,則可求出交點(diǎn)對應(yīng)的兩個(gè)參數(shù)值:第二頁第三頁，共76頁。

需要注意,只有,時(shí)兩線段才真正相交。否則,交點(diǎn)在兩線段或其中某一條線段的延長線上,這時(shí)仍然認(rèn)為是兩線段不相交。第三頁第四頁，共76頁。兩線段AB和CD交點(diǎn)的算法

1.〔計(jì)算行列式〕←(xb-xa)(yc-yd)-(xc-xd)(yb-ya)若=0,則兩線段重合或平行,可算做無交點(diǎn),算法結(jié)束;2.〔計(jì)算交點(diǎn)參數(shù)〕←((xc-xa)(yc-yd)-(xc-xd)(yc-ya))/?

若<0或>1,則無交點(diǎn),算法結(jié)束;←((xb-xa)(yc-ya)-(xc-xa)(yb-ya))/?

若<0或>1,則無交點(diǎn),算法結(jié)束;第四頁第五頁，共76頁。3.〔計(jì)算交點(diǎn)〕x←xa+(xb-xa),y←ya+(yb-ya),輸出交點(diǎn)(x,y)后算法結(jié)束;多條線段求交

尋找這樣的算法,其計(jì)算工作量要大體上與交點(diǎn)個(gè)數(shù)成正比,即只對有可能相交的兩線段計(jì)算交點(diǎn),對不可能相交的線段不計(jì)算交點(diǎn),使算法有更好的效率。第五頁第六頁，共76頁。

我們稱平面內(nèi)兩條線段在橫坐標(biāo)x處是可比較的,如果存在一條通過x的垂直線,此線與兩條線段都相交。我們規(guī)定一個(gè)在x處的"上面"關(guān)系為：在x處,線段S1在S2的上面,記為S1>xS2,如果在x處可比較,且S1與垂直線的交點(diǎn)位于S2與垂直線的交點(diǎn)的上面。第六頁第七頁，共76頁。

其中，S2>μS4,S1>νS2,S2>νS4,S1>νS4

第七頁第八頁，共76頁。

規(guī)定的次序關(guān)系對垂直的線段不適合兩線段相交的必要條件,即若兩線段相交,則必然存在某個(gè)x,使它們在規(guī)定的次序關(guān)系>x下是相鄰的。

算法從左向右掃描,在掃描過程維持正確的線段間上述次序關(guān)系。這種次序關(guān)系只能有三種可能的變化方式:1．遇見某條線段S的左端點(diǎn),此時(shí)S應(yīng)加入次序關(guān)系。2．遇見某線段S的右端點(diǎn),此時(shí)S應(yīng)從次序關(guān)系中刪除。3．遇到某兩條線段S1和S2

的交點(diǎn),這時(shí)在次序關(guān)系中S1和S2交換位置。第八頁第九頁，共76頁。

算法實(shí)施需要兩個(gè)基本的數(shù)據(jù)結(jié)構(gòu):

掃描線狀態(tài)表和事件點(diǎn)進(jìn)度表

掃描線狀態(tài)表L中存放按所規(guī)定次序關(guān)系>x排序的線段的序列。此表初始應(yīng)為空,在平面掃描過程中當(dāng)關(guān)系>x改變時(shí)變化。

事件點(diǎn)指掃描進(jìn)行中可能使所規(guī)定次序關(guān)系>x發(fā)生變化的點(diǎn),存放于事件點(diǎn)進(jìn)度表E中,該表初始時(shí)應(yīng)是排序的要求交點(diǎn)的各線段端點(diǎn)的坐標(biāo)。在平面掃描過程中求出的交點(diǎn),應(yīng)及時(shí)地插入到事件點(diǎn)進(jìn)度表中。

第九頁第十頁，共76頁。

掃描線狀態(tài)表應(yīng)能支持以下四個(gè)操作:(1)INSERT(S,L),把線段S插入到掃描線狀態(tài)表L中,注意應(yīng)插入到適當(dāng)位置以保持正確的次序關(guān)系。(2)DELETE(S,L),從L中刪除線段S。(3)ABOVE(S,L),返回次序關(guān)系中S上面緊接著的線段的編號。

(4)BELOW(S,L),返回次序關(guān)系中S下面緊接著的線段的編號。第十頁第十一頁，共76頁。

事件點(diǎn)進(jìn)度表E應(yīng)能支持以下三個(gè)操作:(1)MIN(E),取出表E中的最小元素。(2)INSERT(x,E),把橫坐標(biāo)為x的一個(gè)點(diǎn)插入到表E中,插入要使E中事件點(diǎn)存放保持遞增次序。

(3)MEMBER(x,E),判定橫坐標(biāo)為x的點(diǎn)是否在事件點(diǎn)進(jìn)度表E中。第十一頁第十二頁，共76頁。算法:

1.〔事件點(diǎn)進(jìn)度表E初始化〕將輸入待求交點(diǎn)的n條線段的2n個(gè)端點(diǎn)按x,y字典式排序后存放于表E中;2.〔準(zhǔn)備收集交點(diǎn)〕A←;{A是一集合,初為空,準(zhǔn)備存入找到的交點(diǎn);}3.〔平面掃描〕若表E不為空,則進(jìn)行(3.1)~(3.3)循環(huán)。直到表E為空時(shí)算法結(jié)束。3.1〔取出當(dāng)前事件點(diǎn)〕P←MIN(E)；3.2〔當(dāng)前事件點(diǎn)處理〕考查當(dāng)前事件點(diǎn)P,分三種情況:(1)若P是邊S的左端點(diǎn),則做：INSERT(S,L);第十二頁第十三頁，共76頁。S1=ABOVE(S,L);S2=BELOW(S,L);若S和S1相交,則求出的交點(diǎn)送入集和A中;若S和S2相交,則求出的交點(diǎn)送入集和A中;(2)若P是邊S的右端點(diǎn),則做：S1=ABOVE(S,L);S2=BELOW(S,L);若S1和S2相交于點(diǎn)P的右邊,則求出的交點(diǎn)送入集和A中；DELETE(S,L)；(3)若P是邊S1和S2的交點(diǎn),且在P的左邊S1=ABOVE(S2),則做第十三頁第十四頁，共76頁。S3=ABOVE(S1,L);S4=BELOW(S2,L);若S3和S2相交，則求出的交點(diǎn)送入集合A中；若S4和S1相交，則求出的交點(diǎn)送入集合A中；在L中交換S1和S2的位置；3.3〔處理找到的交點(diǎn)〕若集合A不為空，做下面循環(huán)，直至A為空：取出集合A中一個(gè)交點(diǎn)，其橫坐標(biāo)是x；若MEMBER(x,E)為FALSE,則輸出此交點(diǎn)，并做INSERT(x,E);第十四頁第十五頁，共76頁。

設(shè)有三條線段S1，S2，S3,它們的坐標(biāo)如下

(1,1),(5,3,),(2,3),(4,1),(6,4),(8,2).要計(jì)算所有交點(diǎn)。第十五頁第十六頁，共76頁。

算法初始形成的事件點(diǎn)進(jìn)度表E，可有形式

(((1,1),S1左端點(diǎn))，((2,3),S2左端點(diǎn))，((4,1),S2右端點(diǎn))，((5,3),S1右端點(diǎn))，((6,4),S3左端點(diǎn))，((8,8),S3右端點(diǎn)))第十六頁第十七頁，共76頁。算法步驟從表E前面取出的掃描到達(dá)的事件點(diǎn)P掃描線狀態(tài)表L工作解釋3.2(1)((1,1),S1左端點(diǎn))(S1)

3.2(1)((2,3),S2左端點(diǎn))(S1,S2)發(fā)生S1,S2求交,求出交點(diǎn)(3,2)插入E((4,1),S2右端點(diǎn))前3.2(3)((3,2),S1和S2的交點(diǎn)(S2,S1)

3.2(2)((4,1),S2右端點(diǎn))(S1)

3.2(2)((5,3),S1右端點(diǎn))()

3.2(1)((6,4),S3左端點(diǎn))(S3)

3.2(2)((8,8),S3右端點(diǎn))()

第十七頁第十八頁，共76頁。第二節(jié)多邊形表面的交線計(jì)算

設(shè)兩個(gè)要求交線的多邊形表面都是凸多邊形表面,分別由它們的頂點(diǎn)坐標(biāo)逆時(shí)針方向的序列確定,即約定按頂點(diǎn)序列前行時(shí)內(nèi)部在左側(cè)。

根據(jù)頂點(diǎn)坐標(biāo)求出兩個(gè)多邊形表面分別所在平面的方程,再根據(jù)平面方程計(jì)算交線,最后,還要確定出交線同時(shí)在兩個(gè)多邊形表面內(nèi)部的部分

第十八頁第十九頁，共76頁。第十九頁第二十頁，共76頁。求平面方程

采用多個(gè)頂點(diǎn)位置坐標(biāo)來計(jì)算平面方程可以減少由于不共面而引起的偏差。設(shè)要求出通過若干頂點(diǎn)的平面方程Ax+By+Cz+D=0,即要定出系數(shù)A,B,C,D,可采用如下做法

平面方程Ax+By+Cz+D=0的系數(shù)A,B,C與該平面上多邊形分別在x=0,y=0,z=0三個(gè)坐標(biāo)平面上投影的面積成比例

第二十頁第二十一頁，共76頁。多邊形在z=0平面上投影的面積S可如下求出:

式中若i=n則j=1,否則j=i+1。

類似地可計(jì)算多邊形表面在x=0和y=0平面上投影的面積,從而確定A,B,然后D可通過代入平面上一點(diǎn)坐標(biāo)數(shù)值來求出。第二十一頁第二十二頁，共76頁。第二十二頁第二十三頁，共76頁。于是有S=[(y1+y2)(x1-x2)十(y2+y3)(x2-x3）

+(y3+y1)(x3-x1)]第二十三頁第二十四頁，共76頁。

若給出空間若干點(diǎn)的坐標(biāo)(x1,y1,z1),(x2,y2,z2),….(xn,yn,zn),注意這里沒有要求這些點(diǎn)共面或圍成了凸多邊形,都可以求出通過或接近這些點(diǎn)的一個(gè)平面方程Ax+By+Cz+D=0:第二十四頁第二十五頁，共76頁。D=-Ax1-By1-Cz1式中若i=n,則j=1,否則j=i+1平面方程的求交A1x+B1y+C1z+D1=0A2x+B2y+C2z+D2=0第二十五頁第二十六頁，共76頁。

兩平面重合或平行,一般算沒有交點(diǎn)

分別對每個(gè)多邊形表面各邊相應(yīng)的線段,計(jì)算它與另一個(gè)多邊形表面所在平面的交點(diǎn)。注意這里是求線段與平面的交點(diǎn),即交點(diǎn)在線段延長線上時(shí)算不相交。假定兩個(gè)多邊形表面都是凸的,故共可以交出四個(gè)交點(diǎn)。第二十六頁第二十七頁，共76頁。線段與平面的交點(diǎn)計(jì)算

空間線段兩個(gè)端點(diǎn)的坐標(biāo)(x1,y1,z1)和x2,y2,z2)給出,平面方程Ax+By+Cz+D=0。第二十七頁第二十八頁，共76頁。

代入平面方程,得:A(x1+(x2-x1)t)+B(y1+(y2-y1)t)+C(z1+(z2-zl)t)+D=0整理得到:[A(x2-x1)+B(y2-y1)+C(z2-zl)]t=-(Ax1+By1+Cz1+D)于是知道,若

A(x2-x1)+B(y2-y1)+C(z2-z1)=0

則所給線段在平面上或與平面平行,沒有唯一確定的交點(diǎn)。否則,交點(diǎn)對應(yīng)的參數(shù)t可以求出:第二十八頁第二十九頁，共76頁。第三節(jié)平面中的凸殼算法

凸殼包含一個(gè)平面點(diǎn)集的最小凸區(qū)域凸區(qū)域指要求區(qū)域內(nèi)任意兩點(diǎn)的連線仍在該區(qū)域內(nèi)。

設(shè)S是平面上n個(gè)點(diǎn)的集合,則S的凸殼是一個(gè)凸多邊形,它包含所有n點(diǎn)且面積最小。事實(shí)上求點(diǎn)集S的凸殼就是要在S中選出殼上的點(diǎn)并排出圍成凸多邊形的次序。第二十九頁第三十頁，共76頁。Graham掃描算法處理的思路是設(shè)想有一內(nèi)點(diǎn)O并且不妨設(shè)想O就是坐標(biāo)原點(diǎn),這時(shí)點(diǎn)集S中所有各點(diǎn)相對軸OX有一個(gè)傾角。所有各點(diǎn)按傾角遞增排序后,如果某一點(diǎn)不是殼上頂點(diǎn),則它必然在兩個(gè)殼頂點(diǎn)與點(diǎn)O形成的三角形內(nèi)部。

Graham掃描的實(shí)質(zhì)是圍繞已經(jīng)按"傾角"排序的各頂點(diǎn)進(jìn)行一次掃描,在掃描過程中消去在凸殼內(nèi)部的點(diǎn),留下以希望次序排列的殼頂點(diǎn)。

第三十頁第三十一頁，共76頁。

由于是按傾角遞增排序,可知若連續(xù)三個(gè)頂點(diǎn)P1,P2,P3是一個(gè)“右轉(zhuǎn)”，則P2是一個(gè)應(yīng)去掉的內(nèi)點(diǎn)。第三十一頁第三十二頁，共76頁。

對給出的三點(diǎn)P1,P2,P3,設(shè)它們的坐標(biāo)是(x1,y1),(x2,y2),(x3,y3),這時(shí)要判斷三點(diǎn)在P2處形成一個(gè)右轉(zhuǎn)還是左轉(zhuǎn),可以計(jì)算下面的行列式

其中△給出的是帶有正負(fù)號的三角形P1P2P3面積的2倍,因此若△>0,則P1,P2,P3是左轉(zhuǎn);△<0,則是右轉(zhuǎn);△=0,則三點(diǎn)共線。第三十二頁第三十三頁，共76頁。

實(shí)現(xiàn)此算法可選點(diǎn)集S中x坐標(biāo)最小的點(diǎn)為內(nèi)點(diǎn)O,設(shè)想過O有一條向右的射線,對其余各點(diǎn),相對該射線計(jì)算傾角然后再排序。

Graham掃描算法

1.〔傾角排序〕選出輸入點(diǎn)集S中x坐標(biāo)最小的點(diǎn),若這樣的點(diǎn)不唯一則再由其中選出y坐標(biāo)最小的點(diǎn),設(shè)為O。設(shè)想有一條從O向右的射線OX,對點(diǎn)集中其余每一點(diǎn)P,計(jì)算傾角POX,再按傾角排序,得點(diǎn)序列Q1=O,Q2,Q3…,Qn;2.〔準(zhǔn)備掃描〕v←Q1;

第三十三頁第三十四頁，共76頁。3.〔掃描〕若NEXT(v)≠Q(mào)1,則循環(huán)執(zhí)行下面操作,至NEXT(v)=Q1時(shí)止,此時(shí)點(diǎn)序列中剩下排成凸多邊形的殼上頂點(diǎn),算法結(jié)束。若三個(gè)相繼的點(diǎn)v,NEXT(v),NEXT(NEXT(v))形成一個(gè)左轉(zhuǎn),則v←NEXT(v);否則,先刪除NEXT(v),再做v←PRED(v);

NEXT(v)和PRED(v)是兩個(gè)函數(shù),其值分別為算法操作的點(diǎn)序列中v的下一點(diǎn)和前一點(diǎn)。這里取下一點(diǎn)和前一點(diǎn)時(shí)認(rèn)為點(diǎn)序列是首尾相接的,即若v是點(diǎn)序列中第一點(diǎn),則PRED(υ)是點(diǎn)序列中最后一點(diǎn);若v是最后一點(diǎn),NEXT(v)是第一點(diǎn)。第三十四頁第三十五頁，共76頁。P3P2P1P0P0P1P2左轉(zhuǎn)，P1P2P3右轉(zhuǎn)，P0P1P3右轉(zhuǎn)。第三十五頁第三十六頁，共76頁。傾角計(jì)算記P點(diǎn)坐標(biāo)為(Xp,Yp),O點(diǎn)坐標(biāo)(X0,Y0),這個(gè)角度數(shù)可如下簡單地計(jì)算:

B=yp-y。若B≥0則角度數(shù)=1-A,否則角度數(shù)=3+A。這里A是向量OP與OX向上單位向量的內(nèi)積,因此是傾角的余弦數(shù)值。B用以判斷該傾角是否大于180度。第三十六頁第三十七頁，共76頁。Jarvis行進(jìn)算法想法是若相繼兩點(diǎn)是一條凸殼多邊形的邊,則對于過該邊的直線,所有點(diǎn)集中的凸殼中的頂點(diǎn)在該直線同側(cè)。因此若找到pq是殼上一邊,則以q為端點(diǎn)的下一條殼邊qr可以如下求出：計(jì)算點(diǎn)集中其余各點(diǎn)相對q點(diǎn)發(fā)出沿向量pq向的射線的傾角,若傾角最小者對應(yīng)的點(diǎn)是r,則qr是下一條殼邊

尋找開始行進(jìn)的第一條殼邊,可以選出點(diǎn)集中按x,y坐標(biāo)字典式次序的最低點(diǎn),該點(diǎn)必定是一個(gè)殼頂點(diǎn)。可從該點(diǎn)引一條豎直向下的射線,在此做一個(gè)行進(jìn)步就找到了第一條殼邊。第三十七頁第三十八頁，共76頁。第三十八頁第三十九頁，共76頁。Jarvis算法1.〔準(zhǔn)備〕v0←點(diǎn)集S中按x,y字典次序最小的點(diǎn);d←豎直向下的一個(gè)方向向量;

點(diǎn)v0送入收集凸殼頂點(diǎn)的隊(duì)列Q中;S1←S-{v0};u←v02.〔一步行進(jìn)〕v1←Wrapping(u,d,S1);3.〔準(zhǔn)備下次〕若v1≠v0,則做:v1接入隊(duì)Q后部;S1=S-{u,v1};d←從u到v1的一個(gè)方向向量;第三十九頁第四十頁，共76頁。u←v1

返步2。4.〔結(jié)束〕殼頂點(diǎn)已經(jīng)全部存入隊(duì)Q中,算法結(jié)束.

其中第2步引入函數(shù)Wrapping來實(shí)現(xiàn)一步行進(jìn)。此函數(shù)的工作是,對S1中所有各點(diǎn),相對自u發(fā)出方向?yàn)閐的射線,計(jì)算所成傾角。在所有傾角中取最小,若有多個(gè)則選與u距離最遠(yuǎn)的那個(gè),它對應(yīng)的點(diǎn)為函數(shù)的返回值。因此在步2求得的v1是一個(gè)行進(jìn)步找到的下個(gè)殼頂點(diǎn)。

Jarvis若點(diǎn)集S中只有較少數(shù)點(diǎn)在殼上,則算法效率很高。若點(diǎn)集S中絕大多數(shù)點(diǎn)都在殼上,算法的效率一般來說就不如Graham掃描了。

第四十頁第四十一頁，共76頁。第四節(jié)包含與重疊簡單多邊形的包含算法平面上的簡單多邊形是不相鄰的邊不能相交的多邊形,設(shè)它用頂點(diǎn)坐標(biāo)的逆時(shí)針序列（x0,y0）,(x1,y1),…,(xn-1,yn-1)確定,即沿頂點(diǎn)序列前行時(shí)內(nèi)部在左側(cè)。

對平面上坐標(biāo)為(xp,yp)的任意一點(diǎn)P,包含性檢驗(yàn)問題是判斷它是否在所給出簡單多邊形的內(nèi)部。第四十一頁第四十二頁，共76頁。

一個(gè)簡便的判斷方法是由P做豎直向下的射線,計(jì)算此射線與多邊形各邊交點(diǎn)的個(gè)數(shù)。第四十二頁第四十三頁，共76頁。

當(dāng)由點(diǎn)P豎直向下的射線恰好通過多邊形的頂點(diǎn)或某一邊時(shí),交點(diǎn)計(jì)數(shù)可采取簡單的"左閉右開"法來處理,即:當(dāng)多邊形一邊的兩個(gè)頂點(diǎn)的x坐標(biāo)都小于或等于點(diǎn)P的x坐標(biāo)時(shí),相應(yīng)交點(diǎn)不計(jì)算在內(nèi)。第四十三頁第四十四頁，共76頁。簡單多邊形包含性檢驗(yàn)的算法

1.〔準(zhǔn)備〕xn←x0,yn←y0,m←-1,i←0;2.〔排除必不相交情形〕若下列條件有一個(gè)成立,則到4。

2.1xp<xi并且xp<xi+1:2.2xp≥xi并且xp≥xi+1;2.3yp<yi并且yp<yi+1;3.〔計(jì)算交點(diǎn)〕y=yi+(xp-xi)(yi+1-yi)/(xi+1-xi),分二種情形:(1)若y=yp,則點(diǎn)P在多邊形邊界上,算法結(jié)束;(2)若y<yp",則m←(-1)?m;4.〔結(jié)束判斷〕i←i+1,若i<n",則返回到2,否則算法結(jié)束,此時(shí)若m=-1則點(diǎn)P在多邊形外部,m=1則在內(nèi)部。第四十四頁第四十五頁，共76頁。凸多邊形的包含算法

沿逆時(shí)針行進(jìn)，凸多邊形內(nèi)部均在其各邊所在直線的左側(cè),因此只要對詢問點(diǎn)P,逐個(gè)檢查它是否在凸多邊形每一邊所在直線的左側(cè)就可.第四十五頁第四十六頁，共76頁。判斷坐標(biāo)為(xp,yp)的點(diǎn)P是在直線的位置設(shè)直線的端點(diǎn)為(x1,y1)和(x2,y2),直線方向是由(x1,y1)到(x2,y2)的方向。直線的方程記為Ax+By+C=0,則有:A=y2-y1,B=x1-x2,C=x2y1-x1y2

計(jì)算D:D=Axp+Byp+C

若D<0,則點(diǎn)在直線左側(cè);

若D>0,則點(diǎn)在直線右側(cè);

若D=0,則點(diǎn)在直線上。

第四十六頁第四十七頁，共76頁。

再進(jìn)一步,引人“折半查找”思想,寫出下面更有效率的算法。設(shè)算法的輸入是一個(gè)凸多邊形的頂點(diǎn)序列Po,P1,…,Pn-1,詢問點(diǎn)P,可有包含性檢驗(yàn)算法如下:第四十七頁第四十八頁，共76頁。1.〔準(zhǔn)備〕i←1,j←n-1;2.〔查找是否結(jié)束〕若j-i=1則到4,否則繼續(xù);3.〔折半查找〕k←[(i+j)/2],檢查詢問點(diǎn)相對直線PoPk的位置關(guān)系,分三種情況:3.1在直線上,若點(diǎn)在線段PoPk上或內(nèi)部,則點(diǎn)在原凸多邊形內(nèi)部,,若點(diǎn)在線段PoPk延長線上,則在原凸多邊形外;輸出回答后算法結(jié)束;3.2在左側(cè),i←k返回步23.3在右側(cè),j←k返回步24.〔最后檢查〕檢查詢問點(diǎn)P對△P0PiPj的包含性,若在內(nèi)則也在原凸多邊形內(nèi)部,若在外則也在原凸多邊形外部,輸出回答后算法結(jié)束.第四十八頁第四十九頁，共76頁。凸多邊形重疊計(jì)算

兩個(gè)凸多邊形的重疊問題,這也就是對兩個(gè)凸多邊形求相交部分的問題。現(xiàn)在約定凸多邊形指它的邊界和內(nèi)部,凸多邊形仍用頂點(diǎn)坐標(biāo)的逆時(shí)針方向序列確定。設(shè)給出的兩個(gè)凸多邊形P和Q的頂點(diǎn)序列分別是P1,P2,…,PL和Q1,Q2,…,Qm。為說明簡便,假設(shè)P的邊界上不包含Q的項(xiàng)點(diǎn),Q的邊界也不包含P的頂點(diǎn)。第四十九頁第五十頁，共76頁。

有兩個(gè)問題需要解決,一個(gè)是如何有次序地求出各邊的所有交點(diǎn),一個(gè)是如何排列求出交點(diǎn)和原凸多邊形的頂點(diǎn),形成交得凸多邊形的頂點(diǎn)序列。

為了有次序地求出交點(diǎn),可以在兩個(gè)多邊形邊上交替地前進(jìn),原則是在哪個(gè)多邊形的邊上可能有交點(diǎn)就等待,在另一個(gè)多邊形的邊上前進(jìn)。初始從對邊P0P1與Q0Q1的求交開始,注意所有求交是線段的求交。這里規(guī)定了P0=PL,Q0=Qm。第五十頁第五十一頁，共76頁。第五十一頁第五十二頁，共76頁。情形(1)(2)(3)(4)(5)(6)(7)(8)Pi在Qj-1Qj左左右右右左右左Qj在Pi-1Pi右左右左左左右右前進(jìn)的多邊形QPQPPQPQ區(qū)分前四種情形還是后四種情形求矢量積Pi-1Pi×Qj-1Qj的z分量,若該分量大于等于0,是前四種情形,小于0是后四種情形。

第五十二頁第五十三頁，共76頁。AdvanceS←Pi-1Pi×Qj-1Qj的z分量;分二種情況處理,然后算法就結(jié)束;1.若S≥0,則做若Pi在Qj-1Qj左并且Qj在Pi-1Pi左(b),或者Pi在Qj-1Qj右并且Qj在pi-1Pi左(d),則i前進(jìn)1,否則j前進(jìn)1;2.若S<0,則做若Pi在Qj-1Qj右并且Qj在Pi-lPi左(e),或者Pi在Qj-1Qj右并且Qj在Pi-1Pi右(g),則i前進(jìn)1,否則j前進(jìn)1;

算法中"i前進(jìn)1",指若i<l,則前進(jìn)1是i+1;若i=L,則前進(jìn)1是1。這因?yàn)槎噙呅蜳是首尾相接的。類似地"j前進(jìn)1",j<m時(shí)是j+1;j=m時(shí)是1。i總在多邊形P上前進(jìn),j在Q上前進(jìn)。

第五十三頁第五十四頁，共76頁。

為了正確排列求出的交點(diǎn)并加入原兩個(gè)凸多邊形部分頂點(diǎn)以形成相交的凸多邊形,可以在每求出一個(gè)交點(diǎn)時(shí)進(jìn)行一次輸出。

求出的第一個(gè)交點(diǎn)可只做一下記錄,如果在以后交替前進(jìn)求交點(diǎn)的過程中再次求出與第一次求得相同的交點(diǎn),就知道整個(gè)求交過程已經(jīng)結(jié)束了。求得一個(gè)不是第一個(gè)的其它任何一個(gè)交點(diǎn)時(shí),為形成交得凸多邊形頂點(diǎn)序列,要區(qū)分邊Pi-lPi是進(jìn)入多邊形Q,還是走出Q兩種情況。第五十四頁第五十五頁，共76頁。Pi-1Pi正進(jìn)入多邊形Q,此時(shí)應(yīng)輸出本次求出交點(diǎn)前，上次求得交點(diǎn)后的多邊形Q上的各頂點(diǎn)，然后再輸出本次交點(diǎn)，因?yàn)檫@些點(diǎn)是交得凸多邊形的頂點(diǎn)。第五十五頁第五十六頁，共76頁。Pi-1Pi是走出Q,這時(shí)應(yīng)輸出本次求出交點(diǎn)前，上次求得交點(diǎn)后的多邊形P上的各頂點(diǎn),再輸出本次交點(diǎn)。這兩種情況區(qū)分,可通過檢查Pi在直線Qj-1Qj的左側(cè)還是右側(cè)來確定。Output

若本過程是第一次被調(diào)用,則做:R0←第一次求得的交點(diǎn),若Pi在Qj-1Qj左則

t←i,否則t←j；否則做:

若Pi在Qj-1Qj左,則做:輸出多邊形Q上t至j-1各頂點(diǎn),輸出當(dāng)前交點(diǎn),t←i;第五十六頁第五十七頁，共76頁。

否則做:輸出多邊形P上t至i-1各頂點(diǎn),輸出當(dāng)前交點(diǎn),t←j;兩個(gè)凸多邊形求交的完整算法:CONVEXPOLYGONINTERSECTION1.〔準(zhǔn)備〕i←1,j←1,k←1,P0←PL,Q0←Qm;2.〔交替前進(jìn)求交〕若k≤2*(l+m)并且所求出當(dāng)前交點(diǎn)不是第一次求得交點(diǎn)R0,則做

2.1~2.3循環(huán):2.1若線段Pi-1Pi與Qj-1Qj相交,則調(diào)用

Output;2.2調(diào)用Advance;2.3k←k+1;第五十七頁第五十八頁，共76頁。3.〔結(jié)束判斷〕若在步2找到過交點(diǎn),則交得凸多邊形頂點(diǎn)序列已在調(diào)用Output過程中輸出,算法結(jié)束;

否則,做如下檢查:

若P1包含于多邊形Q中,則輸出P包含于Q中,算法結(jié)束;

若Q1包含于多邊形P中,則輸出Q包含于P中,算法結(jié)束;

若上述兩個(gè)檢查都不成功,輸出交為空,兩多邊形分離,算法結(jié)束;第五十八頁第五十九頁，共76頁。交點(diǎn)個(gè)數(shù)最多為2(l+m)個(gè)第五十九頁第六十頁，共76頁。第五節(jié)簡單多邊形的三角剖分

簡單多邊形做三角剖分,是要求選出完全在內(nèi)部又互不相交的一組對角線，把整個(gè)多邊形劃分成一些三角形。這里對角線是不相鄰頂點(diǎn)間的連線,選出的對角線的集合稱為是簡單多邊形的三角剖分。對任意一個(gè)簡單多邊形,其三角剖分不是唯一的。

事實(shí)1

簡單多邊形必有一條對角線完全在其內(nèi)部。

事實(shí)2

簡單多邊形上必有連續(xù)的三個(gè)頂點(diǎn)A,B,C,使對角線AC完全在其內(nèi)部。第六十頁第六十一頁，共76頁。必有完全在內(nèi)部的對角線第六十一頁第六十二頁，共76頁。

簡單多邊形三角剖分的算法:考查連續(xù)三個(gè)頂點(diǎn)A,B,C,若AC完全在多邊形內(nèi)部,則可輸出△ABC為一個(gè)剖分后形成的三角形,刪除點(diǎn)B后再對少了一個(gè)頂點(diǎn)的多邊形繼續(xù)進(jìn)行。簡單多邊形的頂點(diǎn)序列為P0,P1,Pn-1,那么算法可描述如下:SIMPLEPOLYGONTRIANGULATION1.〔準(zhǔn)備〕Q0←P0;2.〔剖分〕若n>3，則做2.1~2.2,否則轉(zhuǎn)到步3:2.1Q1←點(diǎn)序列中Q0的下一個(gè)頂點(diǎn);Q2←點(diǎn)序列中Q1的下一個(gè)頂點(diǎn);2.2若Test(Q0,Q1,Q2)為真,則做:

輸出△Q0Q1Q2;第六十二頁第六十三頁，共76頁。

從點(diǎn)序列中刪除頂點(diǎn)Ql;n←n-1;

返回步2開頭;

否則做Q0←Q1,返回步2.1;3.〔最后輸出〕輸出點(diǎn)序列中剩下三點(diǎn)為最后一個(gè)三角形,然后算法結(jié)束。函數(shù)Test是對△Q0Q1Q2進(jìn)行檢查，分兩步實(shí)現(xiàn),第一步檢查Q0,Q1,Q2是否是一個(gè)在Ql的左轉(zhuǎn),若不然,是右轉(zhuǎn),則Q0Q2在多邊形外部而可以回答假而結(jié)束。第二步可對原多邊形中除去Q0,Q1,Q2這三點(diǎn)之外的其它點(diǎn)，對每一點(diǎn)都考查它對三角形的包含性,若有一點(diǎn)被包含則就可以回答假而結(jié)束,只有其它點(diǎn)都在三角形外部時(shí)才能回答真而結(jié)束。

第六十三頁第六十四頁，共76頁。最小權(quán)三角剖分或最小三角剖分如果一個(gè)三角剖分中選取的對角線的總長度最小。任意的凸多邊形最小三角剖分第六十四頁第六十五頁，共76頁。事實(shí)3在n邊形(n≥3)的任意一種三角剖分中,每一對相鄰頂點(diǎn)中至少有一個(gè)頂點(diǎn)是某條對角線的端點(diǎn)。因?yàn)槿粝噜忢旤c(diǎn)Vi,Vi+1都不是某條對角線的端點(diǎn),則區(qū)域(Vi-1,Vi,Vi+1,Vi+2)中沒有對角線,因而也就沒有被三角剖分。事實(shí)4如果ViVj是三角剖分的一條對角線,則一定存在某頂點(diǎn)Vk,使得ViVk和VkVj是多邊形的邊或?qū)蔷€。因?yàn)槿舨蝗?一定存在以ViVj為邊界的某個(gè)區(qū)域沒有被三角剖分。第六十五頁第六十六頁，共76頁。頂點(diǎn)序列V0,V1--,Vn-1確定的凸n邊形的最小三角剖分挑選兩個(gè)相鄰頂點(diǎn)比方選V0和V1,由事實(shí)3知道在最小三角剖分中,必有另一頂點(diǎn)Vk,或者使V1Vk是對角線,或者使V0VK是對角線。對有n個(gè)頂點(diǎn)的多邊形，Vk的選取方法有n-3種。對于每個(gè)可能的Vk用對角線V0Vk(或V1Vk)把原多邊形剖分成兩個(gè)較小的多邊形,這樣原問題就被分成為兩個(gè)子問題。往下需要尋找分成的兩個(gè)較小凸多邊形的最小三角剖分。（遞歸）

第六十六頁第六十七頁，共76頁。

選擇剖分方法,使得每次剖分后所得的子問題只涉及一條原多邊形的對角線。由事實(shí)4知在最小剖分中的對角線一定與另外一點(diǎn)構(gòu)成三角形。第六十七頁第六十八頁，共76頁。

現(xiàn)在一般地說明所要使用的剖分方法。引入記號Sis,表示一個(gè)子多邊形Vi,Vi+1,…,Vi+s-1的最小三角剖分問題。子多邊形由Vi開始的S個(gè)頂點(diǎn)按順時(shí)針向排列圍成。每個(gè)子問題Sis中都僅涉及原多邊形一條對角線。為了解Sis,必須考慮如下三種情況:1.選擇頂點(diǎn)Vi+S-2,這時(shí)構(gòu)成一個(gè)三角形ViVi+S-2Vi+S-1,得到一個(gè)子問題Si,S-12.選擇頂點(diǎn)Vi+1,這時(shí)構(gòu)成一個(gè)三角形ViVi+1Vi+S-1,得到一個(gè)子問題Si+1,S-1。

3.對2≤k≤S-3,選擇Vi+k這時(shí)構(gòu)成一個(gè)三角形ViVi+kVi+S-1,得到兩個(gè)子問題Si,k+1和Si+k,S-k。第六十八頁第六十九頁，共76頁。

實(shí)際上可以把三種情況概括為一句話,即對1≤k≤S-2,把Sis分解成兩個(gè)子問題Si,k+1和Si+k,S-k。容易驗(yàn)證k=1和k=S-2時(shí),各自有一個(gè)子問題不成其為問題,但這不影響一般的討論。

第六十九頁第七十頁，共76頁。CiS記子問題SiS的解

CiS的公式如下:CiS=min[Ci,k+1+Ci+k,S-k+D(V