多邊形裁剪的Sutherland―Hodgman算法(計算機圖形學)

1、多邊形裁剪的SutherlandHodgman算法1>.SutherlandHodgman多邊形裁剪算法思想該算法的基本思想是每次用窗口的一條邊界及其延長線來裁剪多邊形的各邊。多邊形通常由它的頂點序列來表示，經(jīng)過裁剪規(guī)則針對某條邊界裁剪后，結果形成新的頂點序列，又留待下條邊界進行裁剪，直到窗口的所有邊界都裁剪完畢，算法形成最后的頂點序列，才是結果多邊形（它可能構成一個或多個多邊形）。當多邊形一個頂點Pi相對于窗口某條邊界及其延長線進行剪裁時，不外乎下列四種情況（即裁剪規(guī)則）：1、頂點Pi在內側，前一頂點Pi-1也在內側，則將Pi納入新的頂點序列；2、頂點Pi在內側，前一頂點Pi-1在外側

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

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

4、geL(CPointpolypoint,CPointclipwindow,UINTpolynum)/*其中參數(shù)polypoint為多邊形頂點,clipwindow為裁剪窗口頂點,polynum為多邊形頂點數(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;/*記載原始多邊形頂點個數(shù)*/m_nB=0;/*記載新生成多邊形頂點個數(shù)*/for(i=0;i<m_nA;i+)if(polypointi.x<xl&&polypointi+1.x<xl)/*判斷的多邊形邊兩個端點都在外部，不做處理*/c

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

7、在外部，終點在內部，求交點，然后交點，終點都應該送入臨時數(shù)組*/*保留交點*/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、點在內部，終點在外，求交點，然后起點，交點送入臨時數(shù)組*/*保留內部點*/Bm_nB.x=polypointi.x;Bm_nB.y=polypointi.y;m_nB=m_nB+1;/*保留交點*/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;/把第一個點的數(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)/兩個點全在下方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在上，留交點，外>內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和交點，內外/saveplCm_nA.x=Bi.x;Cm_nA.y=Bi.y;m_nA+;/留交點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在左方，留交點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在內，P2在外，留P1和交點saveplBm_nB.x=Ci.x;Bm_nB.y=Ci.y;m_nB+;/save交點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在下方外>內，留交點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在上方，內>外，留P1和交點/savep1,Cm_nA.x=Bi.x;Cm_nA.y=Bi.y;m_nA+;/save交點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