計(jì)算機(jī)圖形學(xué)（第3版）課件：圖形運(yùn)算

2024/12/141計(jì)算機(jī)圖形學(xué)

圖形運(yùn)算第一節(jié)線段的交點(diǎn)計(jì)算第二節(jié)多邊形表面的交線計(jì)算第三節(jié)平面中的凸殼算法第四節(jié)包含與重疊第五節(jié)簡(jiǎn)單多邊形的三角剖分第一節(jié)線段的交點(diǎn)計(jì)算

一、兩條線段求交 設(shè)有兩線段AB和CD,其端點(diǎn)坐標(biāo)分別為(xa,ya),(xb,yb)和(xc,yc),(xd,yd),它們所在直線的參數(shù)方程分別為：若兩線段相交,則交點(diǎn)的參數(shù)值,應(yīng)滿足:即因此,若行列式表示兩線段AB和CD重合或平行。一般做為它們不相交來(lái)處理。如果≠0,則可求出交點(diǎn)對(duì)應(yīng)的兩個(gè)參數(shù)值:需要注意,只有0≤λ≤1,0≤μ≤1時(shí)兩線段才真正相交。否則,交點(diǎn)在兩線段或其中某一條線段的延長(zhǎng)線上,這時(shí)仍然認(rèn)為是兩線段不相交。兩線段AB和CD交點(diǎn)的算法

intLineSegmentIntersection(POINTa,POINTb,POINTc,POINTd,POINTp)/*POINT平面點(diǎn)類型，

a,b,c,d兩直線的端點(diǎn),p求解的交點(diǎn)*/{ floatt,t1,t2; t=(b.x-a.x))*(c.y-d.y)-(c.x-d.x))*(b.y-a.y);//計(jì)算行列式

if(fabs(t)<=1.0e-3)return0;//平行或重合，無(wú)解返回

t1=((c.x-a.x))*(c.y-d.y)-(c.x-d.x))*(c.y-a.y)/t;//計(jì)算參數(shù)

if(t1<0||t1>1)return0;//無(wú)解返回

t2=((b.x-a.x))*(c.y-a.y)-(c.x-a.x))*(b.y-a.y)/t;//計(jì)算參數(shù)

if(t2<0||t2>1)return0;//無(wú)解返回

p.x=a.x+t1*(b.x-a.x); p.y=a.y+t1*(b.y-a.y); return1;}二.多條線段求交

①窮舉法(很多線段不相交時(shí)，效率低，計(jì)算浪費(fèi)）②掃描線思想求交（高效算法只對(duì)有可能相交的兩線段計(jì)算交點(diǎn),對(duì)不可能相交的線段不計(jì)算交點(diǎn)）定義關(guān)系線段之間是可比較的（兩條線段與同一垂線有交點(diǎn)）x處的“上面”關(guān)系為：在x處,線段S1在S2的上面,記為S1>xS2,如果在x處可比較,且S1與垂直線的交點(diǎn)位于S2與垂直線的交點(diǎn)的上面。其中，S2>uS4,S1>νS2,S2>νS4,S1>νS4

假設(shè)：為簡(jiǎn)便起見(jiàn)，要求交點(diǎn)的n條線段中沒(méi)有垂直的線段(規(guī)定的次序關(guān)系對(duì)垂直的線段不適合)，也沒(méi)有三條以上的線段交于一點(diǎn)的情況。兩線段相交的必要條件： 若兩線段相交,則必然存在某個(gè)x,使它們?cè)谝?guī)定的次序關(guān)系>x下是相鄰的。

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

的交點(diǎn),這時(shí)在次序關(guān)系中S1和S2交換位置。算法的數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)過(guò)程:算法實(shí)施需要兩個(gè)基本的數(shù)據(jù)結(jié)構(gòu):

掃描線狀態(tài)表和事件點(diǎn)進(jìn)度表掃描線狀態(tài)表L：存放按次序關(guān)系>x排序的線段的序列。初始為空,掃描過(guò)程中當(dāng)關(guān)系>x改變時(shí)變化。事件點(diǎn)：掃描過(guò)程中可能使次序關(guān)系>x發(fā)生變化的點(diǎn),事件點(diǎn)進(jìn)度表E：存放事件點(diǎn)的表，初始為n條線段的2n個(gè)端點(diǎn)，在平面掃描過(guò)程中求出的交點(diǎn)，應(yīng)及時(shí)地插入到事件點(diǎn)進(jìn)度表中。掃描線狀態(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上面緊接著的線段的編號(hào)。(4)BELOW(S,L),返回次序關(guān)系中S下面緊接著的線段的編號(hào)。

事件點(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中。算法:intLINE_INTERSECTION(LINELine[n],POINT*Q){/*Line線段數(shù)組Q交點(diǎn)集合

L掃描線狀態(tài)表E事件點(diǎn)進(jìn)度表*/ SORT(Line,E);//將線段Line數(shù)組的n個(gè)端點(diǎn)按x,y字典排序保存至E中；

L=null;Q=null A=null;//A初始為空，暫時(shí)保存當(dāng)前L表中線段的交點(diǎn)

while(!EMPTY(E)){//若E非空

P=MIN(E);//取出當(dāng)前事件點(diǎn)S=BELONGTO(Line,P);//P屬于線段S上的一點(diǎn)

if(LEFT(P,Line,S)){//P為L(zhǎng)ine中線段S左端點(diǎn)

INSERT(S,L)；//將S插入L中

S1=ABOVE(S,L); S2=BELOW(S,L); q=INTERSECTION(S,S1);//計(jì)算交點(diǎn)并存入A中

if(q!=NULL)INSERT(q,A);

q=INTERSECTION(S,S2);//計(jì)算交點(diǎn)并存入A中

if(q!=NULL)INSERT(q,A);

}elseif(RIGHT(P,Line,S)){//P為L(zhǎng)ine中線段S右端點(diǎn)

S1=ABOVE(S,L); S2=BELOW(S,L); q=INTERSECTION(S1,S2);//若S1和S2相交于P的右邊，交點(diǎn)送入A集合 if((q!=NULL)&&(q->x>P->x))INSERT(q,A);

DELETE(S,L);//在L中刪去S線段S1S2PSS1S2PS算法:

}else{//P為線段之交點(diǎn)

[S1,S2]=BELONGTO(Line,P);//P為S1和S2的交點(diǎn),

且在P的左邊,S1位于S2的上面 S3=ABOVE(S1,L); S4=BELOW(S2,L); q=INTERSECTION(S3,S2);//計(jì)算交點(diǎn)并存入A中

if(q!=NULL)INSERT(q,A);

q=INTERSECTION(S4,S1);//計(jì)算交點(diǎn)并存入A中

if(q!=NULL)INSERT(q,A);

SWAP(S1,S2,L);//在L中交換S1和S2的位置

} while(!EMPTY(A)){ x=GETFIRST(A);//取出A中的交點(diǎn),得到x坐標(biāo)

if(!MEMBER(x,E)){

//交點(diǎn)第一次計(jì)算得出

INSERT(x,E);//交點(diǎn)送入E中

INSERT(x,Q);//交點(diǎn)送入Q中 }}}}S2PS1S4S32024/12/1414算法:

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,分三種情況:2024/12/1415(1)若P是邊S的左端點(diǎn),則做：INSERT(S,L);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)；S1S2PSS1S2PS2024/12/1416(3)若P是邊S1和S2的交點(diǎn)，且在P的左邊

S1=ABOVE(S2),則做

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);(交點(diǎn)是不是第一次求得）S2PS1S4S3

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

(1,1),(5,3,),(2,3),(4,1),(6,4),(8,2).要計(jì)算所有交點(diǎn)。

算法初始形成的事件點(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,2),S3右端點(diǎn)))算法步驟從表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))(S2,S1)發(fā)生S1,S2求交,求出交點(diǎn)(3,2)插入E((4,1),S2右端點(diǎn))前3.2(3)((3,2),S1和S2的交點(diǎn)(S1,S2)

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,2),S3右端點(diǎn))()

交換位置第二節(jié)多邊形表面的交線計(jì)算

多邊形：設(shè)空間多面體的表面為凸多邊形表面,分別由它們的頂點(diǎn)坐標(biāo)逆時(shí)針?lè)较虻男蛄写_定,即約定按頂點(diǎn)序列前行時(shí)內(nèi)部在左側(cè)。求交步驟：(已知兩個(gè)多邊形頂點(diǎn)序列）1.根據(jù)頂點(diǎn)坐標(biāo)求出兩個(gè)多邊形表面分別所在平面的方程2.根據(jù)平面方程判斷多邊形所在平面是否相交3.確定出交線同時(shí)在兩個(gè)多邊形表面內(nèi)部的部分1.求平面方程

采用多個(gè)頂點(diǎn)位置坐標(biāo)來(lái)計(jì)算平面方程可以減少由于不共面而引起的偏差。設(shè)要求出通過(guò)若干頂點(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)平面上投影的面積成比例

多邊形在z=0平面上投影的面積S可如下求出:

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

類似地可計(jì)算多邊形表面在x=0和y=0平面上投影的面積,從而確定A,B,然后D可通過(guò)代入平面上一點(diǎn)坐標(biāo)數(shù)值來(lái)求出。

若給出空間若干點(diǎn)的坐標(biāo)(x1,y1,z1),(x2,y2,z2),….,(xn,yn,zn),注意這里沒(méi)有要求這些點(diǎn)共面或圍成了凸多邊形,都可以求出通過(guò)或接近這些點(diǎn)的一個(gè)平面方程Ax+By+Cz+D=0:

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

兩平面重合或平行,沒(méi)有交點(diǎn)否則，兩平面方程聯(lián)立，可以認(rèn)為是空間的交線式方程2.平面方程的求交A1x+B1y+C1z+D1=0A2x+B2y+C2z+D2=03.確定交線同時(shí)在兩個(gè)多邊形內(nèi)部的部分分別對(duì)每個(gè)多邊形表面各邊相應(yīng)的線段,計(jì)算它與另一個(gè)多邊形表面所在平面的交點(diǎn)。注意：求線段（有限）與平面（無(wú)限）的交點(diǎn),即交點(diǎn)在線段延長(zhǎng)線上時(shí)算不相交。假定兩個(gè)多邊形表面都是凸的,故共可以交出四個(gè)交點(diǎn)。交得的四個(gè)交點(diǎn)可按x,y,z坐標(biāo)字典式排序，中間兩個(gè)交點(diǎn)的連線是兩個(gè)多邊形表面相交所得的線段。 ABCDABCD

求線段（有限）與平面（無(wú)限）的交點(diǎn) 空間線段兩個(gè)端點(diǎn)的坐標(biāo)(x1,y1,z1)和(x2,y2,z2)給出,平面方程Ax+By+Cz+D=0。代入平面方程,得: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即(A,B,C)和(x2-x1,y2-y1,z2-z1)點(diǎn)積為零，則所給線段在平面上或與平面平行，沒(méi)有唯一確定的交點(diǎn)。否則，交點(diǎn)對(duì)應(yīng)的參數(shù)t可以求出:若t<0或t>1,交點(diǎn)在線段延長(zhǎng)線上，沒(méi)有交點(diǎn)若0≤t≤1，將參數(shù)t代回直線的參數(shù)方程求出交點(diǎn)的坐標(biāo)intPolygon_Polygon(POINTP[],intn,POINTQ[],intm){/*P、Q表示空間兩多邊形，n、m表示邊數(shù)目*/ PLANE(P,n,A1,B1,C1,D1);//計(jì)算P的平面方程

PLANE(Q,m,A2,B2,C2,D2);//計(jì)算Q的平面方程

//無(wú)交線，算法結(jié)束

if(A1/A2==B1/B2&&A1/A2==C1/C2)return0;

//計(jì)算P中每邊與Q面的交點(diǎn)，若有保存兩交點(diǎn),s為交點(diǎn)個(gè)數(shù)

CACULATE(P,n,A2,B2,C2,D2,P1,P2,s); if(s==0)return0;//無(wú)交線，算法結(jié)束

//計(jì)算Q中每邊與P面的交點(diǎn)，若有保存兩交點(diǎn),s為交點(diǎn)個(gè)數(shù)

CACULATE(Q,m,A1,B1,C1,D1,P3,P4,s); if(s==0)return0;//無(wú)交線，算法結(jié)束

//測(cè)試四點(diǎn)的位置關(guān)系，輸出交線部分

OUTPUT(P1,P2,P3,P4);}空間兩多邊形的交線計(jì)算算法如下：第三節(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)且面積最小。求點(diǎn)集S的凸殼：

1）在S中選出殼上的點(diǎn)

2）給出圍成凸多邊形的序列。1.Graham掃描算法 思想：設(shè)有一內(nèi)點(diǎn)O，設(shè)為原點(diǎn),對(duì)點(diǎn)集S中所有的點(diǎn)計(jì)算與OX軸的傾角，并按照傾角遞增排序,若某一點(diǎn)不是凸頂點(diǎn),則它必然在兩個(gè)殼頂點(diǎn)與點(diǎn)O形成的三角形內(nèi)部,則刪除這個(gè)內(nèi)點(diǎn)。

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

由于是按傾角遞增排序,可知若連續(xù)三個(gè)頂點(diǎn)P1,P2,P3是一個(gè)“右轉(zhuǎn)”，則P2是一個(gè)應(yīng)去掉的內(nèi)點(diǎn)。對(duì)給出的三點(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ù)號(hào)的三角形P1P2P3面積的,因此若△>0,則P1,P2,P3是左轉(zhuǎn);△<0,則是右轉(zhuǎn);△=0,則三點(diǎn)共線。內(nèi)點(diǎn)O:S中x坐標(biāo)最小的點(diǎn)voidGraham(POINTS[],intn){//S為點(diǎn)集數(shù)組，n為點(diǎn)的個(gè)數(shù) //依據(jù)邊界點(diǎn)O將S中點(diǎn)按傾角排成序放置在Q中，

//Q中起始點(diǎn)為O sortangle(S,n,Q); v=first(Q);//取出Q中起始點(diǎn)

//若Q中v的下一個(gè)點(diǎn)不是起始點(diǎn)

while(next(v,Q)!=first(Q)){ //若連續(xù)三點(diǎn)左轉(zhuǎn) if(left(pred(v,Q),v,next(v,Q))

v=next(v,Q);//v前進(jìn)至下一個(gè)點(diǎn)

else{ delete(next(v,Q),Q);//刪除v的下一個(gè)點(diǎn)

v=pred(v,Q);//v退回至前一個(gè)點(diǎn)

} }}next(v)：返回點(diǎn)序列中的v的下一個(gè)點(diǎn)（后繼節(jié)點(diǎn)）pred(v)：返回點(diǎn)序列中的v的前一個(gè)點(diǎn)（前驅(qū)節(jié)點(diǎn)）循環(huán)鏈表：next(Qn)=Q1,pred(Q1)=QnP4P3P2P1P0P1P2P3左轉(zhuǎn)，P2P3P4右轉(zhuǎn)，P1P2P4右轉(zhuǎn),P0P1P4左轉(zhuǎn)，P0P1P2左轉(zhuǎn)，P1P2P3左轉(zhuǎn)，P2P3P4右轉(zhuǎn)，P1P2P4右轉(zhuǎn)。算法中v←PRED(v)的作用：例子說(shuō)明P4P3P2P1P0傾角計(jì)算 記P點(diǎn)坐標(biāo)為(Xp,Yp),O點(diǎn)坐標(biāo)(X0,Y0),這個(gè)角度數(shù)可如下簡(jiǎn)單地計(jì)算:B=yp-y0若B≥0，則角度數(shù)=1-A,若B<0，則角度數(shù)=3+A。這里A是向量OP與OX向上單位向量的內(nèi)積,因此是傾角的余弦數(shù)值。B用以判斷該傾角是否大于180度。 2.Jarvis行進(jìn)算法 思想：若相繼兩點(diǎn)構(gòu)成的邊是凸殼的一條邊則對(duì)于過(guò)該邊的直線，所有凸殼中點(diǎn)集中的點(diǎn)在該直線同側(cè)。因此若找到pq是殼上一邊,則以q為端點(diǎn)的下一條殼邊qr可以如下求出：計(jì)算點(diǎn)集中其余各點(diǎn)相對(duì)q點(diǎn)發(fā)出沿向量pq向的射線的傾角,若傾角最小者對(duì)應(yīng)的點(diǎn)是r,則qr是下一條殼邊。 第一條殼邊的確定：把點(diǎn)集S中所有點(diǎn)按x,y字典式排序，取最低點(diǎn)，該點(diǎn)必定是一個(gè)殼頂點(diǎn)。從該點(diǎn)引一條豎直向下的射線，在此做一個(gè)行進(jìn)步就找到了第一條殼邊。Jarvis算法voidJarvis(POINTS[],intn){//S為點(diǎn)集數(shù)組，n為點(diǎn)的個(gè)數(shù)

v0=xy_minsort(S,n);//xy_minsort求S中xy排序最小點(diǎn)

d=(0,-1);//d送豎直向下向量

Q=null;//隊(duì)列Q置空

add(Q,v0);//v0添加到隊(duì)列Q中

S1=delete(v0,S);//將S1設(shè)置成僅在S集合中刪去v0點(diǎn)的集合

u=v0; //取出S1中與u點(diǎn)連接并與d方向夾角最小的點(diǎn)，若角度一樣取最遠(yuǎn)點(diǎn)

v1=wrapping(u,d,S1); while(v1!=v0){ add(Q,v1);//v1加入隊(duì)列Q中

//S1置為刪除v1、u兩點(diǎn)的后包含其余點(diǎn)的點(diǎn)集合

S1=delete(v1,S);S1=delete(u,S1); d=vector(u,v1);//d置為由u到v1的向量

u=v1; v1=wrapping(u,d,S1); }}uv1duv1dv1ud

函數(shù)Wrapping來(lái)實(shí)現(xiàn)一步行進(jìn)。此函數(shù)的工作是,對(duì)S1中所有各點(diǎn),計(jì)算射線d與自u(píng)向各頂點(diǎn)發(fā)出的射線所成傾角。在所有傾角中取最小，若有多個(gè)，則選與u距離最遠(yuǎn)的那個(gè)，它對(duì)應(yīng)的點(diǎn)為函數(shù)的返回值。因此在步2求得的v1是一個(gè)行進(jìn)步找到的下一個(gè)凸殼頂點(diǎn)。 若點(diǎn)集S中只有較少數(shù)點(diǎn)在殼上,則Jarvis算法效率很高。若點(diǎn)集S中絕大多數(shù)點(diǎn)都在殼上,算法的效率一般來(lái)說(shuō)就不如Graham掃描了。

uv1d第四節(jié)包含與重疊

一.點(diǎn)對(duì)簡(jiǎn)單多邊形的包含算法平面上的簡(jiǎn)單多邊形是不相鄰的邊不能相交的多邊形。設(shè)它用頂點(diǎn)坐標(biāo)的逆時(shí)針序列(x0,y0),(x1,y1),…,(xn-1,yn-1)確定，即沿頂點(diǎn)序列前行時(shí)內(nèi)部在左側(cè)。對(duì)平面上坐標(biāo)為(xp,yp)的任意一點(diǎn)P,包含性檢驗(yàn)問(wèn)題是判斷該點(diǎn)是否在所給出簡(jiǎn)單多邊形的內(nèi)部。思想：由P豎直向下引射線,計(jì)算此射線與多邊形各邊交點(diǎn)的個(gè)數(shù)。

奇數(shù)：P在多邊形內(nèi)部

偶數(shù)：P在多邊形外部特殊情況處理：當(dāng)由點(diǎn)P豎直向下的射線恰好通過(guò)多邊形的頂點(diǎn)或某一邊時(shí),交點(diǎn)計(jì)數(shù)可采取簡(jiǎn)單的"左閉右開(kāi)"法來(lái)處理即:當(dāng)點(diǎn)P的x坐標(biāo)大于或等于多邊形一邊的兩個(gè)頂點(diǎn)的x坐標(biāo)時(shí),相應(yīng)交點(diǎn)不計(jì)算在內(nèi)（左閉）只要點(diǎn)P的x坐標(biāo)小于多邊形一邊兩端點(diǎn)的一個(gè)x坐標(biāo)，交點(diǎn)就計(jì)數(shù)（右開(kāi)）注意：射線均為豎直向下的為了減少計(jì)算量，可判斷不可能相交的情況（1）xp<xi并且xp<xi+1:

（2）xp≥xi并且xp≥xi+1;

（3）yp<yi并且yp<yi+1;算法中用m代表奇偶性：初始m=-1，m(-1)c

C為偶數(shù)m負(fù)點(diǎn)在多邊形外部C為奇數(shù)m正點(diǎn)在多邊形內(nèi)部簡(jiǎn)單多邊形包含性檢驗(yàn)的算法

intinner(POINTq[],intn,POINTp){//q為多邊形頂點(diǎn)數(shù)組p為待測(cè)點(diǎn)

intm,i,y; q[n]=q[0]; m=-1;i=0; while(i<n) { if((p.x<q[i].x&&p.x<q[i+1].x)||(p.x>=q[i].x&& p.x>=q[i+1].x)||(p.y<q[i].y&&p.y<q[i+1].y)); else{ y=q[i].y+(p.x-q[i].x)*(q[i+1].y-q[i].y)/(q[i+1].x-q[i].x); if(y==p.y)return1; if(y<p.y)m=m*(-1); } ++i; } if(m==-1)return0;//點(diǎn)P在多邊形外部

elsereturn1;//點(diǎn)P在多邊形內(nèi)部}二.凸多邊形的包含算法思想：沿逆時(shí)針行進(jìn)，凸多邊形內(nèi)部均在其各邊所在直線的左側(cè),因此只要對(duì)點(diǎn)P,逐個(gè)檢查它是否在凸多邊形每一邊所在直線的左側(cè)就可。判斷坐標(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)在直線上?！罢郯氩檎摇?*p凸多邊形頂點(diǎn)數(shù)組n多邊形邊數(shù)q待測(cè)點(diǎn)*/intinner1(POINTp[],intn,POINTq){ inti,j,k; i=1;j=n-1; while(j-i>1){ k=(i+j)/2;//折半查找

if(test(q,p,0,k)==0)return1;//q在p[0]和p[k]線段內(nèi)部

elseif(test(q,p,0,k)==1)return0;//q在p[0]和p[k]線段延長(zhǎng)線上

elseif(test(q,p,0,k)==2)i=k;//q在在p[0]和p[k]線段左側(cè)

elseif(test(q,p,0,k)==3)j=k;//q在在p[0]和p[k]線段右側(cè)

} if(test3(q,p,0,i,j))return1;//q在p[0]p[i]p[j]三角形內(nèi)

elsereturn0;}P0PkPjPiQP0PiPjQQ三.凸多邊形重疊計(jì)算

兩個(gè)凸多邊形的重疊問(wèn)題就是對(duì)兩個(gè)凸多邊形求相交部分的問(wèn)題。約定凸多邊形指它的邊界和內(nèi)部,凸多邊形仍用頂點(diǎn)坐標(biāo)的逆時(shí)針?lè)较蛐蛄写_定。 設(shè)給出的兩個(gè)凸多邊形P和Q的頂點(diǎn)序列分別是P1,P2,…,PL和Q1,Q2,…,Qm。

假設(shè)P的邊界上不包含Q的頂點(diǎn),Q的邊界也不包含P的頂點(diǎn)。有兩個(gè)問(wèn)題需要解決：

1.如何有次序地求出各邊的所有交點(diǎn), 2.如何排列求出的交點(diǎn)和原凸多邊形的頂點(diǎn),

形成新的凸多邊形的頂點(diǎn)序列。1.求交點(diǎn):

為了有次序地求出交點(diǎn),可以在兩個(gè)多邊形邊上交替地前進(jìn),原則是在哪個(gè)多邊形的邊上可能有交點(diǎn)就等待,在另一個(gè)多邊形的邊上前進(jìn)。初始從對(duì)邊P0P1與Q0Q1的求交開(kāi)始,注意所有求交是線段的求交。這里規(guī)定了P0=PL,Q0=Qm。 設(shè)已經(jīng)算得Pi-1Pi和Qj-1Qj的交點(diǎn)，依可能性判定接下去計(jì)算的是PiPi+1與Qj-1Qj的交點(diǎn)還是Pi-1Pi和QjQj+1的交點(diǎn) 此外還需考慮Pi

和Qj之間的夾角是否大于180度 初始從對(duì)邊P0P1與Q0Q1的求交開(kāi)始,注意所有求交是線段的求交。情形(1)(2)(3)(4)(5)(6)(7)(8)Pi在Qj-1Qj左左右右右左右左Qj在Pi-1Pi

右左右左左左右右前進(jìn)的多邊形QPQPPQPQ情形(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是后四種情形。

/*P、Q為多邊形頂點(diǎn)數(shù)組，l、m為頂點(diǎn)個(gè)數(shù)*/VoidAdvance(PONITP[],intl,POINTQ[],intm){ ints; s=vector3(P,Q,i,j);//s置成PiPi-1與QjQj-1的叉乘的z值

if(s>=0){ if((left(P,i,Q,j)&&left(Q,j,P,i))||(right(P,i,Q,j)&&left(Q,j,P,i))){ if(i<l)i++; elsei=1; }else{ if(j<m)j++; elsej=1; } }else{ if((right(P,i,Q,j)&&left(Q,j,P,i))||(right(P,i,Q,j)&&right(Q,j,P,i))){ if(i<l)i++; elsei=1; }else{ if(j<m)j++; elsej=1; } }}情形(1)(2)(3)(4)(5)(6)(7)(8)Pi在Qj-1Qj左左右右右左右左Qj在Pi-1Pi

右左右左左左右右前進(jìn)的多邊形QPQPPQPQ

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

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

Pi-1Pi正進(jìn)入多邊形Q,此時(shí)應(yīng)輸出本次求出交點(diǎn)前，上次求得交點(diǎn)后的多邊形Q上的各頂點(diǎn)，然后再輸出本次交點(diǎn)，因?yàn)檫@些點(diǎn)是交得凸多邊形的頂點(diǎn)。/*P、Q為多邊形頂點(diǎn)數(shù)組，l、m為頂點(diǎn)個(gè)數(shù)*/voidOutput(PONITP[],intl,POINTQ[],intm){ POINTr0;intt; if(本過(guò)程第一次調(diào)用){ r0=intersect(P,i,Q,j);//r0置成Pi-1Pi與Qj-1Qj之交點(diǎn)

if(left(P,i,Q,j))//Pi在Qj-1Qj左

t=i; else t=j; }else{ if(left(P,i,Q,j)){//若Pi在Qj-1Qj左，輸出Q中t至j-1頂點(diǎn)，輸出Pi-1Pi與Qj-1Qj之交點(diǎn)

out(Q,t,j-1);t=i; }else{//輸出P中t至i-1頂點(diǎn)，輸出Pi-1Pi與Qj-1Qj之交點(diǎn)

out(P,t,i-1);t=j; } }}P和Q，P中的每一條邊與P相交最多兩個(gè)交點(diǎn)，故Q最多與P交2m個(gè)交點(diǎn)，同理，P最多與Q交2l個(gè)交點(diǎn)，故2(l+m)步是足夠的,max(2l,2m)即可兩個(gè)凸多邊形求交的完整算法:/*P、Q為多邊形頂點(diǎn)數(shù)組，l、m為多邊形邊數(shù)*/voidConvex_polygon_intersection(POINTP[],intl,POINTQ[],intm){ inti,j,k,P0,Q0; i=1;j=1;k=1;P0=P[l];Q0=Q[m];//初始化

while(k<=2*(l+m)&&(求得的交點(diǎn)不是第一個(gè)交點(diǎn)R0))//交替前進(jìn)求交

{ if(Pi-1Pi與Qj-1Qj相交)Output(P,l,Q,m);//若相交，則調(diào)用Output Advance(P,l,Q,m); k++; } if(找到過(guò)交點(diǎn)){ Output(P,l,Q,m); return; }else{ if(inner(Q,m,P[1]))printf("P在Q中"); elseif(inner(P,l,Q[1]))printf("Q在P中"); elseprintf("P與Q分離"); }}第五節(jié)簡(jiǎn)單多邊形的三角剖分

簡(jiǎn)單多邊形做三角剖分,是要求選出完全在內(nèi)部又互不相交的一組對(duì)角線，把整個(gè)多邊形劃分成一些三角形。 對(duì)角線是不相鄰頂點(diǎn)間的連線,選出的對(duì)角線的集合稱為是簡(jiǎn)單多邊形的三角剖分。對(duì)任意一個(gè)簡(jiǎn)單多邊形,其三角剖分不唯一。 事實(shí)1簡(jiǎn)單多邊形必有一條對(duì)角線完全在其內(nèi)部。 事實(shí)2簡(jiǎn)單多邊形上必有連續(xù)的三個(gè)頂點(diǎn)A,B,C,使對(duì)角線AC完全在其內(nèi)部。必有完全在內(nèi)部的對(duì)角線簡(jiǎn)單多邊形三角剖分的算法:考查連續(xù)三個(gè)頂點(diǎn)A,B,C,若AC完全在多邊形內(nèi)部,則可輸出△ABC為一個(gè)剖分后形成的三角形,刪除點(diǎn)B后再對(duì)少了一個(gè)頂點(diǎn)的多邊形繼續(xù)進(jìn)行。ABCL(1)ACABCL(2)ABCL(3)AVBVVVX簡(jiǎn)單多邊形的頂點(diǎn)序列為P0,P1,Pn-1,那么算法可描述如下:/*P為指向多邊形鏈表的首指針n為多邊形頂點(diǎn)數(shù)*/voidSimple_polygon_triangulation(POINT*P,intn){ Q0=P;m=n; while(m>3) { Q1=next(Q0);Q2=next(Q1); if(Test(Q0,Q1,Q2){ Output(Q0);//輸出三角形Q0Q1Q2; m--; delete(Q1);//刪除頂點(diǎn)Q1 } else Q0=Q1; } Output(Q0);//輸出Q0開(kāi)始的剩下的三角形；}

函數(shù)Test是對(duì)△Q0Q1Q2進(jìn)行檢查，分兩步實(shí)現(xiàn)：

第一步檢查Q0,Q1,Q2是否是一個(gè)在Ql的左轉(zhuǎn),若是右轉(zhuǎn),則Q0Q2在多邊形外部,可以輸出假而結(jié)束。

第二步檢查可對(duì)原多邊形中除去Q0,Q1,Q2這三點(diǎn)的其它點(diǎn)，對(duì)每一點(diǎn)都考查它對(duì)三角形的包含性,若有一點(diǎn)被包含則就可以輸出假而結(jié)束,只有其它點(diǎn)都在三角形外部時(shí)才能輸出真而結(jié)束。

Q0Q1Q2Q0Q1Q2最小權(quán)三角剖分或最小三角剖分如果一個(gè)三角剖分中選取的對(duì)角線的總長(zhǎng)度最小。任意的凸多邊形最小三角剖分（簡(jiǎn)化問(wèn)題）同一個(gè)凸多邊形的兩種三角剖分事實(shí)3在n邊形(n≥3)的任意一種三角剖分中,每一對(duì)相鄰頂點(diǎn)中至少有一個(gè)頂點(diǎn)是某條對(duì)角線的端點(diǎn)。 因?yàn)槿粝噜忢旤c(diǎn)Vi,Vi+1都不是某條對(duì)角線的端點(diǎn),則區(qū)域(Vi-1,Vi,Vi+1,Vi+2)中沒(méi)有對(duì)角線,因而也就沒(méi)有被三角剖分。

Vi-1ViVi+1Vi+2事實(shí)4如果ViVj是三角剖分的一條對(duì)角線,則一定存在某頂點(diǎn)Vk,使得ViVk和VkVj是多邊形的邊或?qū)蔷€。 因?yàn)槿舨蝗?一定存在以ViVj為邊界的某個(gè)區(qū)域沒(méi)有被三角剖分。ViVjVk頂點(diǎn)序列V0,V1,…,Vn-1確定的凸n邊形的最小三角剖分 挑選兩個(gè)相鄰頂點(diǎn)V0和Vn-1,由事實(shí)3知道在最小三角剖分中,必有另一頂點(diǎn)Vk,或者使V0Vk是對(duì)角線,或者使Vn-1Vk是對(duì)角線。 對(duì)有n(如n=7)個(gè)頂點(diǎn)的多邊形，Vk的選取方法有n-2種(1≤k≤n-2)。V6V5V4V3V2V1V0

對(duì)于每個(gè)可能的Vk用對(duì)角線V0Vk(或V6Vk)把原多邊形剖分成兩個(gè)較小的多邊形,這樣原問(wèn)題就被分成為兩個(gè)子問(wèn)題。 往下需要尋找分成的兩個(gè)較小凸多邊形的最小三角剖分。（遞歸）

V6V5V4V3V2V1V0V0V6V6V5V4V3V3V2V1V0V3V6V5V4V3V2V1V0

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

引人記號(hào)Sis,表示一個(gè)子多邊形Vi,Vi+1,…,Vi+s-1的最小三角剖分問(wèn)題。子多邊形由Vi開(kāi)始的S個(gè)頂點(diǎn)按順時(shí)針向排列圍成。（圖中S04,S34） 解Sis,必須考慮如下三種情況:

對(duì)1≤k≤S-2,選擇Vi+k(例如k=3,s=7)這時(shí)構(gòu)成一個(gè)三角形ViVi+kVi+S-1,得到兩個(gè)子問(wèn)題Si,k+1和Si+k,S-k。V6V5V4V3V2V1V0

對(duì)1≤k≤S-2,選擇Vi+k(例如k=4)這時(shí)構(gòu)成一個(gè)三角形ViVi+kVi+S-1,得到兩個(gè)子問(wèn)題Si,k+1和Si+k,S-k。

1.當(dāng)k=S-2時(shí)，選擇頂點(diǎn)Vi+S-2,這時(shí)構(gòu)成一個(gè)三角形ViVi+S-2Vi+S-1,得到一個(gè)子問(wèn)題Si,S-1 2.當(dāng)k=1時(shí)，選擇頂點(diǎn)Vi+1,這時(shí)構(gòu)成一個(gè)三角形ViVi+1Vi+S-1,得到一個(gè)子問(wèn)題Si+1,S-1。

V6V5V4V3V2V1V0V6V5V4V3V2V1V0V6V5V4V3V2V1V0CiS記為子問(wèn)題SiS的解CiS的公式如下:CiS=min[Ci,k+1+Ci+k,S-k+D(ViVi+k)+D(Vi+kVi+S-1)]

1≤k≤S-2若VpVq是對(duì)角線,則D(VpVq)是它的長(zhǎng)度;若VpVq是原多邊形的邊,則D(VpVq)=0;若S<4,則CiS=0。這因?yàn)镃iS是最小三角剖分中所有對(duì)角線的總長(zhǎng)度,原多邊形的邊不是對(duì)角