多邊形裁剪算法(共8頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上多邊形裁剪的SutherlandHodgman算法 1>. SutherlandHodgman多邊形裁剪算法思想該算法的基本思想是每次用窗口的一條邊界及其延長線來裁剪多邊形的各邊。多邊形通常由它的頂點(diǎn)序列來表示，經(jīng)過裁剪規(guī)則針對某條邊界裁剪后，結(jié)果形成新的頂點(diǎn)序列，又留待下條邊界進(jìn)行裁剪，直到窗口的所有邊界都裁剪完畢，算法形成最后的頂點(diǎn)序列，才是結(jié)果多邊形（它可能構(gòu)成一個(gè)或多個(gè)多邊形）。當(dāng)多邊形一個(gè)頂點(diǎn)Pi相對于窗口某條邊界及其延長線進(jìn)行剪裁時(shí)，不外乎下列四種情況（即裁剪規(guī)則）：1、頂點(diǎn)Pi在內(nèi)側(cè)，前一頂點(diǎn)Pi-1也在內(nèi)側(cè)，則將Pi納入新的頂點(diǎn)序列；2、頂點(diǎn)Pi

2、在內(nèi)側(cè)，前一頂點(diǎn)Pi-1在外側(cè)，則先求交點(diǎn)Q，再將Q、Pi依次納入新的頂點(diǎn)序列；3、頂點(diǎn)Pi在外側(cè)，前一頂點(diǎn)Pi-1在內(nèi)側(cè)，則先求交點(diǎn)Q，再將Q納入新的頂點(diǎn)序列；4、頂點(diǎn)Pi與前一頂點(diǎn)Pi-1均在外側(cè)，則頂點(diǎn)序列中不增加新的頂點(diǎn)。 2>. SutherlandHodgman多邊形裁剪算法步驟考慮多邊形相對于一條邊界及其延長線進(jìn)行裁剪的算法：1從主函數(shù)得到待裁剪多邊形的頂點(diǎn)序列P2、頂點(diǎn)序列數(shù)n、窗口一條邊界參數(shù)xl（假如為矩形窗口的左邊界）；2賦初值：將頂點(diǎn)序列中的最后一個(gè)頂點(diǎn)賦給前一頂點(diǎn)S；設(shè)置初始標(biāo)志flag：if(S在邊界內(nèi)側(cè))flag=0;else flag=1；設(shè)新的頂點(diǎn)序列數(shù)

3、j=0；3對多邊形各頂點(diǎn)進(jìn)行裁剪規(guī)則處理，結(jié)果放入新的多邊形頂點(diǎn)序列Q2中：for(對第一個(gè)頂點(diǎn)直到最后一個(gè)頂點(diǎn)，逐一處理）if(Pi在邊界內(nèi)側(cè))if(flag!=0)flag=0;求交點(diǎn)并放入新的多邊形頂點(diǎn)序列Qj中；j+；將當(dāng)前頂點(diǎn)放入新的多邊形頂點(diǎn)序列Qj中：Qj=Pi；j+；elseif(flag=0)flag=1;求交點(diǎn)并放入新的多邊形頂點(diǎn)序列Qj中；j+；將當(dāng)前頂點(diǎn)賦給S：S=Pi；4做返回準(zhǔn)備：將新的多邊形頂點(diǎn)序列Q又逐一放回原多邊形頂點(diǎn)序列P中：P=Q；將新的多邊形頂點(diǎn)數(shù)j放回原多邊形頂點(diǎn)數(shù)n中：n=j；/-多邊形裁剪的SutherlandHodgman算法-/void CMy

4、Clip_AView:ClipedgeL(CPoint polypoint, CPoint clipwindow, UINT polynum)/*其中參數(shù)polypoint為多邊形頂點(diǎn),clipwindow為裁剪窗口頂點(diǎn),polynum為多邊形頂點(diǎn)數(shù)目*/ /找出裁剪窗口邊界 long xl,xr,yt,yb; UINT i; xl=clipwindow0.x; xr=clipwindow0.x; yt=clipwindow0.y; yb=clipwindow0.y; for(i=1;i<=4;i+) if(xl>clipwindowi.x) xl=clipwindowi.x; i

5、f(xr<clipwindowi.x) xr=clipwindowi.x; if(yb>clipwindowi.y) yb=clipwindowi.y; if(yt<clipwindowi.y) yt=clipwindowi.y; / CPoint BPolygon_Num,CPolygon_Num; UINT m_nA,m_nB; int x,y; long tem1,tem2; m_nA=polynum;/*記載原始多邊形頂點(diǎn)頂點(diǎn)個(gè)數(shù)*/ m_nB=0;/*記載新生成多邊形頂點(diǎn)頂點(diǎn)個(gè)數(shù)*/ for(i=0;i<m_nA;i+) if(polypointi.x<

6、xl && polypointi+1.x<xl) /*判斷的多邊形邊兩個(gè)端點(diǎn)都在外部，不做處理*/ continue;/*如果是這種情況，那么就對繼續(xù)對下一條多邊形邊作判斷，也就是說下面的判斷不用做了*/ if(polypointi.x>=xl && polypointi+1.x>=xl) /*邊兩個(gè)端點(diǎn)都在內(nèi)部，保留*/ /*因?yàn)槊總€(gè)保留的點(diǎn)在數(shù)組中只出現(xiàn)一次，且下一次判斷時(shí)第二個(gè)端點(diǎn)一定會要取到，因此只保留的兩個(gè)點(diǎn)中的第一個(gè)*/ Bm_nB.x =polypointi.x ; Bm_nB.y =polypointi.y ; m_nB=m_n

7、B+1; continue; if(polypointi.x<xl && polypointi+1.x>=xl)/*邊兩個(gè)端點(diǎn)起點(diǎn)在外部，終點(diǎn)在內(nèi)部，求交點(diǎn)，然后交點(diǎn)，終點(diǎn)都應(yīng)該送入臨時(shí)數(shù)組*/ /*保留交點(diǎn)*/ x=xl; tem1=(xl-polypointi.x); /tem2=(xl-x1)*dy/dx+y1; /y/x=dy/dx->y=x*dy/dx tem2=tem1*(polypointi+1.y-polypointi.y)/(polypointi+1.x-polypointi.x)+polypointi.y; y=tem2; Bm_nB.x

8、=x; Bm_nB.y =y; m_nB=m_nB+1; continue; if(polypointi.x>=xl && polypointi+1.x<xl)/*起點(diǎn)在內(nèi)部，終點(diǎn)在外，求交點(diǎn)，然后起點(diǎn)，交點(diǎn)送入臨時(shí)數(shù)組*/ /*保留內(nèi)部點(diǎn)*/ Bm_nB.x =polypointi.x ; Bm_nB.y =polypointi.y ; m_nB=m_nB+1; /*保留交點(diǎn)*/ x=xl; tem1=(xl-polypointi.x); tem2=tem1*(polypointi+1.y-polypointi.y)/(polypointi+1.x-polypoi

9、nti.x)+polypointi.y; y=tem2; Bm_nB.x =x; Bm_nB.y =y; m_nB=m_nB+1; continue; /把第一個(gè)點(diǎn)的數(shù)據(jù)拷貝到最后 /形成裁剪后的多邊形 if(i=m_nA) Bm_nB=B0; /下- m_nA=0; for(i=0;i<m_nB;i+) if(Bi.y<yb && Bi+1.y<yb) /兩個(gè)點(diǎn)全在下方 continue;/下一條邊 if(Bi.y>=yb && Bi+1.y>=yb) /p1,p2都在yb上方 Cm_nA.x =Bi.x; Cm_nA.y =Bi

10、.y; m_nA+; continue; if(Bi.y<yb && Bi+1.y>=yb) /p1在下，P2在上,留交點(diǎn)，外內(nèi) y=yb; tem1=yb-Bi.y; /tem2=x1+(yb-y1)*dx/dy tem2=tem1*(Bi+1.x-Bi.x)/(Bi+1.y-Bi.y) + Bi.x; x=tem2; Cm_nA.x =x; Cm_nA.y =y; m_nA+; continue; if(Bi.y>=yb && Bi+1.y<yb) /p1在上方，P2在下方，留P1和交點(diǎn),內(nèi)外 /save p1 Cm_nA.x=Bi.

11、x; Cm_nA.y=Bi.y; m_nA+; /留交點(diǎn) y=yb; tem1=yb-Bi.y; /tem2=x1+(yb-y1)*dx/dy tem2=tem1*(Bi+1.x-Bi.x)/(Bi+1.y-Bi.y)+Bi.x; x=tem2; Cm_nA.x =x; Cm_nA.y =y; m_nA+; continue; /形成第二次裁剪多邊形 if(i=m_nB) Cm_nA=C0; /右- m_nB=0; for(i=0;i<m_nA;i+) if(Ci.x>xr && Ci+1.x>xr) /P1，P2都在右方-go next continue;

12、if(Ci.x<=xr && Ci+1.x<=xr) /P1，P2都在左方，留P1 Bm_nB.x =Ci.x; Bm_nB.y =Ci.y; m_nB+; continue; if(Ci.x>xr && Ci+1.x<=xr) /P1在右方，P2在左方，留交點(diǎn) x=xr; tem1=Ci.x-xr; tem2=Ci.y-tem1*(Ci+1.y-Ci.y)/(Ci+1.x-Ci.x); y=tem2; Bm_nB.x =x; Bm_nB.y =y; m_nB+; continue; if(Ci.x<=xr && C

13、i+1.x>xr) /P1在內(nèi)，P2在外，留P1和交點(diǎn) /save p1 Bm_nB.x =Ci.x; Bm_nB.y =Ci.y; m_nB+; /save 交點(diǎn) x=xr; tem1=Ci.x-xr; tem2=Ci.y-tem1*(Ci+1.y-Ci.y)/(Ci+1.x-Ci.x); y=tem2; Bm_nB.x =x; Bm_nB.y =y; m_nB+; continue; /三次裁剪后的新多邊形 if(i=m_nA) Bm_nB=B0; /上- m_nA=0; for(i=0;i<m_nB;i+) if(Bi.y>yt && Bi+1.y>

14、;yt) /p1,p2都在上方,next continue; if(Bi.y<=yt && Bi+1.y<=yt) /p1,p2都在下方,留P1 Cm_nA.x =Bi.x; Cm_nA.y =Bi.y; m_nA+; continue; if(Bi.y>yt && Bi+1.y<=yt) /P1在上方，P2在下方外內(nèi),留交點(diǎn) y=yt; tem1=Bi.y-yt; /tem2=x1+(yb-y1)*dx/dy tem2=Bi.x-tem1*(Bi+1.x-Bi.x)/(Bi+1.y-Bi.y); x=tem2; Cm_nA.x =x; Cm_nA.y =y; m_nA+; continue; if(Bi.y<=yt && Bi+1.y>yt) /P1在下方，P2在上方，內(nèi)外，留P1和交點(diǎn) /save p1, Cm_nA.x =Bi.x; Cm_nA.y =Bi.y; m_nA+; /save 交點(diǎn) y=yt; tem1=Bi.y-yt; /tem2=x1+(yb-y1)*dx/dy tem2=Bi.x-tem1*(Bi+1.x-Bi.x)/(Bi+1.y-Bi.y); x=tem2; Cm_