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

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

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

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

4、ipedgeL(CPoint polypoint, CPoint clipwindow, UINT polynum)/*其中參數(shù)polypoint為多邊形頂點,clipwindow為裁剪窗口頂點,polynum為多邊形頂點數(shù)目*/            /找出裁剪窗口邊界        long xl,xr,yt,yb;        UINT i

5、;        xl=clipwindow0.x;        xr=clipwindow0.x;         yt=clipwindow0.y;        yb=clipwindow0.y;         for(

6、i=1;i<=4;i+)                     if(xl>clipwindowi.x)                 xl=clipwindowi.x;     &#

7、160;      if(xr<clipwindowi.x)                 xr=clipwindowi.x;             if(yb>clipwindowi.y)     &#

8、160;          yb=clipwindowi.y;            if(yt<clipwindowi.y)                 yt=clipwindowi.y;   &#

9、160;            /        CPoint BPolygon_Num,CPolygon_Num;        UINT m_nA,m_nB;            int x,y;   &

10、#160;    long tem1,tem2;            m_nA=polynum;/*記載原始多邊形頂點頂點個數(shù)*/        m_nB=0;/*記載新生成多邊形頂點頂點個數(shù)*/        for(i=0;i<m_nA;i+)     &#

11、160;              if(polypointi.x<xl && polypointi+1.x<xl) /*判斷的多邊形邊兩個端點都在外部，不做處理*/                        

12、0;   continue;/*如果是這種情況，那么就對繼續(xù)對下一條多邊形邊作判斷，也就是說下面的判斷不用做了*/                        if(polypointi.x>=xl && polypointi+1.x>=xl) /*邊兩個端點都在內(nèi)部，保留*/    &#

13、160;           /*因為每個保留的點在數(shù)組中只出現(xiàn)一次，且下一次判斷時第二個端點一定會要取到，因此只保留的兩個點中的第一個*/                            Bm_nB.x =polypointi.x

14、;                Bm_nB.y =polypointi.y ;                m_nB=m_nB+1;            continue; 

15、                       if(polypointi.x<xl && polypointi+1.x>=xl)/*邊兩個端點起點在外部，終點在內(nèi)部，求交點，然后交點，終點都應(yīng)該送入臨時數(shù)組*/             

16、60;              /*保留交點*/                x=xl;                tem1=(xl-polypointi.x);

17、                /tem2=(xl-x1)*dy/dx+y1;                /y/x=dy/dx->y=x*dy/dx            

18、;    tem2=tem1*(polypointi+1.y-polypointi.y)/(polypointi+1.x-polypointi.x)+polypointi.y;                y=tem2;                Bm_nB.x

19、=x;                Bm_nB.y =y;                m_nB=m_nB+1;            continue;  

20、0;                     if(polypointi.x>=xl && polypointi+1.x<xl)/*起點在內(nèi)部，終點在外，求交點，然后起點，交點送入臨時數(shù)組*/                

21、0;  /*保留內(nèi)部點*/                Bm_nB.x =polypointi.x ;                Bm_nB.y =polypointi.y ;         

22、       m_nB=m_nB+1;                /*保留交點*/                x=xl;         &#

23、160;      tem1=(xl-polypointi.x);                tem2=tem1*(polypointi+1.y-polypointi.y)/(polypointi+1.x-polypointi.x)+polypointi.y;           &#

24、160;    y=tem2;                Bm_nB.x =x;                Bm_nB.y =y;           

25、     m_nB=m_nB+1;            continue;                            /把第一個點的數(shù)據(jù)拷貝到最后   &#

26、160;    /形成裁剪后的多邊形        if(i=m_nA)                    Bm_nB=B0;                /下- 

27、       m_nA=0;        for(i=0;i<m_nB;i+)                    if(Bi.y<yb && Bi+1.y<yb)       &#

28、160;        /兩個點全在下方                            continue;/下一條邊             

29、                   if(Bi.y>=yb && Bi+1.y>=yb)                /p1,p2都在yb上方        

30、                        Cm_nA.x =Bi.x;                Cm_nA.y =Bi.y;        

31、;        m_nA+;            continue;                              

32、;  if(Bi.y<yb && Bi+1.y>=yb)            /p1在下，P2在上,留交點，外內(nèi)                            y=yb; 

33、               tem1=yb-Bi.y;                /tem2=x1+(yb-y1)*dx/dy               

34、; tem2=tem1*(Bi+1.x-Bi.x)/(Bi+1.y-Bi.y) + Bi.x;                x=tem2;                Cm_nA.x =x;         

35、;       Cm_nA.y =y;                m_nA+;            continue;              

36、;          if(Bi.y>=yb && Bi+1.y<yb)            /p1在上方，P2在下方，留P1和交點,內(nèi)外                    &

37、#160;       /save p1                Cm_nA.x=Bi.x;                Cm_nA.y=Bi.y;       

38、         m_nA+;                /留交點                y=yb;         

39、       tem1=yb-Bi.y;                /tem2=x1+(yb-y1)*dx/dy                tem2=tem1*(Bi+1.x-Bi.x)/(Bi+1.y-Bi.y)+Bi.x;

40、60;               x=tem2;                Cm_nA.x =x;                Cm_nA.y =y;&

41、#160;               m_nA+;            continue;                       

42、     /形成第二次裁剪多邊形        if(i=m_nB)                    Cm_nA=C0;                /右-

43、60;       m_nB=0;        for(i=0;i<m_nA;i+)                    if(Ci.x>xr && Ci+1.x>xr)       

44、;     /P1，P2都在右方-go next                             continue;               

45、60;        if(Ci.x<=xr && Ci+1.x<=xr)            /P1，P2都在左方，留P1                       

46、     Bm_nB.x =Ci.x;                Bm_nB.y =Ci.y;                m_nB+;          

47、;  continue;                        if(Ci.x>xr && Ci+1.x<=xr)            /P1在右方，P2在左方，留交點    

48、60;                       x=xr;                tem1=Ci.x-xr;          

49、      tem2=Ci.y-tem1*(Ci+1.y-Ci.y)/(Ci+1.x-Ci.x);                y=tem2;                Bm_nB.x =x;    &#

50、160;           Bm_nB.y =y;                m_nB+;            continue;        

51、60;               if(Ci.x<=xr && Ci+1.x>xr)            /P1在內(nèi)，P2在外，留P1和交點                

52、60;           /save p1                Bm_nB.x =Ci.x;                Bm_nB.y =Ci.y;   

53、             m_nB+;                /save 交點                x=xr;    &#

54、160;           tem1=Ci.x-xr;                tem2=Ci.y-tem1*(Ci+1.y-Ci.y)/(Ci+1.x-Ci.x);              

55、0; y=tem2;                Bm_nB.x =x;                Bm_nB.y =y;              &#

56、160; m_nB+;            continue;                            /三次裁剪后的新多邊形        if(i=m

57、_nA)                    Bm_nB=B0;                /上-        m_nA=0;      &#

58、160; for(i=0;i<m_nB;i+)                    if(Bi.y>yt && Bi+1.y>yt)            /p1,p2都在上方,next       &#

59、160;                    continue;                        if(Bi.y<=yt && Bi+1.y<=yt)

60、60;           /p1,p2都在下方,留P1                            Cm_nA.x =Bi.x;        &#

61、160;       Cm_nA.y =Bi.y;                m_nA+;            continue;             

62、;           if(Bi.y>yt && Bi+1.y<=yt)            /P1在上方，P2在下方外內(nèi),留交點                    

63、;        y=yt;                tem1=Bi.y-yt;                /tem2=x1+(yb-y1)*dx/dy     

64、0;          tem2=Bi.x-tem1*(Bi+1.x-Bi.x)/(Bi+1.y-Bi.y);                x=tem2;                Cm_nA.x =x;

65、                Cm_nA.y =y;                m_nA+;            continue;    &

66、#160;                   if(Bi.y<=yt && Bi+1.y>yt)            /P1在下方，P2在上方，內(nèi)外，留P1和交點                            /save p1,                Cm_nA.x =Bi.x;