多边形裁剪的Sutherland—Hodgman算法(计算机图形学)

《多边形裁剪的Sutherland—Hodgman算法(计算机图形学)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、多边形裁剪的Sutherland—Hodgman算法1>.Sutherland—Hodgman多边形裁剪算法思想该算法的基本思想是每次用窗口的一条边界及其延长线来裁剪多边形的各边。多边形通常由它的顶点序列来表示，经过裁剪规则针对某条边界裁剪后，结果形成新的顶点序列，又留待下条边界进行裁剪，…，直到窗口的所有边界都裁剪完毕，算法形成最后的顶点序列，才是结果多边形（它可能构成一个或多个多边形）。当多边形一个顶点Pi相对于窗口某条边界及其延长线进行剪裁时，不外乎下列四种情况（即裁剪规则）：1、顶点Pi在内侧，前一顶点Pi-1也在内侧，则将Pi纳入新的顶点序列；2、顶点Pi在内侧，前一顶点Pi

2、-1在外侧，则先求交点Q，再将Q、Pi依次纳入新的顶点序列；3、顶点Pi在外侧，前一顶点Pi-1在内侧，则先求交点Q，再将Q纳入新的顶点序列；4、顶点Pi与前一顶点Pi-1均在外侧，则顶点序列中不增加新的顶点。2>.Sutherland—Hodgman多边形裁剪算法步骤考虑多边形相对于一条边界及其延长线进行裁剪的算法：1．从主函数得到待裁剪多边形的顶点序列P[][2]、顶点序列数n、窗口一条边界参数xl（假如为矩形窗口的左边界）；2．赋初值：将顶点序列中的最后一个顶点赋给前一顶点S；设置初始标志flag：if(S在边界内侧)flag=0;elseflag=1；设新的顶点序列数j=0；3

3、．对多边形各顶点进行裁剪规则处理，结果放入新的多边形顶点序列Q[][2]中：for(对第一个顶点直到最后一个顶点，逐一处理）{if(Pi在边界内侧){if(flag!=0){flag=0;求交点并放入新的多边形顶点序列Qj中；j++；}将当前顶点放入新的多边形顶点序列Qj中：Qj=Pi；j++；}else{if(flag==0){flag=1;求交点并放入新的多边形顶点序列Qj中；j++；}}将当前顶点赋给S：S=Pi；}4．做返回准备：将新的多边形顶点序列Q又逐一放回原多边形顶点序列P中：P=Q；将新的多边形顶点数j放回原多边形顶点数n中：n=j；//////////////////

4、//////////////////////////////////////////////////////////////////////-----多边形裁剪的Sutherland—Hodgman算法---------///////////////////////////////////////////////////////////////////////////////////////voidCMyClip_AView::ClipedgeL(CPointpolypoint[],CPointclipwindow[],UINTpolynum)/*其中参数polypoint[]为多边形

5、顶点,clipwindow[]为裁剪窗口顶点,polynum为多边形顶点数目*/{           //找出裁剪窗口边界       longxl,xr,yt,yb;       UINTi;       xl=clipwindow[0].x;       xr=clipwindow[0].x;        yt=clipwindow[0].y;       yb=clipwindow[0].y;        for(i=1;i<=4;i++)        {           if(xl>clipwindow[i].x)                xl=clipwin

6、dow[i].x;           if(xrclipwindow[i].y)               yb=clipwindow[i].y;           if(yt

7、          intx,y;       longtem1,tem2;           m_nA=polynum;/*记载原始多边形顶点顶点个数*/       m_nB=0;/*记载新生成多边形顶点顶点个数*/       for(i=0;i