多邊形裁剪的Sutherland―Hodgman算法(計(jì)算機(jī)圖形學(xué))

1、多邊形裁剪的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在內(nèi)側(cè)，前一頂點(diǎn)Pi-1在外側(cè)

2、，則先求交點(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;elseflag=1；設(shè)新的頂點(diǎn)序列數(shù)j=0；3對多邊形各頂點(diǎn)進(jìn)行裁剪規(guī)

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

4、geL(CPointpolypoint,CPointclipwindow,UINTpolynum)/*其中參數(shù)polypoint為多邊形頂點(diǎn),clipwindow為裁剪窗口頂點(diǎn),polynum為多邊形頂點(diǎn)數(shù)目*/找出裁剪窗口邊界longxl,xr,yt,yb;UINTi;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;if(xr<clipwindowi.x)xr=clipwindowi

5、.x;if(yb>clipwindowi.y)yb=clipwindowi.y;if(yt<clipwindowi.y)yt=clipwindowi.y;/CPointBPolygon_Num,CPolygon_Num;UINTm_nA,m_nB;intx,y;longtem1,tem2;m_nA=polynum;/*記載原始多邊形頂點(diǎn)個(gè)數(shù)*/m_nB=0;/*記載新生成多邊形頂點(diǎn)個(gè)數(shù)*/for(i=0;i<m_nA;i+)if(polypointi.x<xl&&polypointi+1.x<xl)/*判斷的多邊形邊兩個(gè)端點(diǎn)都在外部，不做處理*/c

6、ontinue;/*如果是這種情況，那么就對繼續(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_nB+1;continue;if(polypointi.x<xl&&polypointi+1.x>=xl)/*邊兩個(gè)端點(diǎn)起點(diǎn)

7、在外部，終點(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/dxtem2=tem1*(polypointi+1.y-polypointi.y)/(polypointi+1.x-polypointi.x)+polypointi.y;y=tem2;Bm_nB.x=x;Bm_nB.y=y;m_nB=m_nB+1;continue;if(polypointi.x>=xl&&polypointi+1.x<xl)/*起

8、點(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-polypointi.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

9、;/下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.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/dytem2=tem1*(Bi+1.x-Bi.x

10、)/(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)外/saveplCm_nA.x=Bi.x;Cm_nA.y=Bi.y;m_nA+;/留交點(diǎn)y=yb;tem1=yb-Bi.y;/tem2=x1+(yb-y1)*dx/dytem2=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;/形成第二次裁剪多邊

11、形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都在右方-gonextcontinue;if(Ci.x<=xr&&Ci+1.x<=xr)/P1,P2都在左方，留P1Bm_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

12、.y)/(Ci+1.x-Ci.x);y=tem2;Bm_nB.x=x;Bm_nB.y=y;m_nB+;continue;if(Ci.x<=xr&&Ci+1.x>xr)P1在內(nèi)，P2在外，留P1和交點(diǎn)saveplBm_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;f

13、or(i=0;i<m_nB;i+)if(Bi.y>yt&&Bi+1.y>yt)/p1,p2都在上方,nextcontinue;if(Bi.y<=yt&&Bi+1.y<=yt)/p1,p2都在下方,留P1Cm_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/dytem2=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)/savep1,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/dytem2=Bi.x-tem1*(Bi+1.x-Bi.x)/(Bi+1.y-Bi.y);x=tem