多边形裁剪的Sutherland—Hodgman 算法 1>. Sutherland—Hodgman 多边形裁剪算法思想 该算法的基本思想是每次用窗口的一条边界及其延长线来裁剪多边形的各边。多边形通常由它的顶点序列来表示,经过裁剪规则针对某条边界裁剪后,结果形成新的顶点序列,又留待下条边界进行裁剪,…,直到窗口的所有边界都裁剪完毕,算法形成最后的顶点序列,才是结果多边形(它可能构成一个或多个多边形)。 当多边形一个顶点 Pi 相对于窗口某条边界及其延长线进行剪裁时,不外乎下列四种情况(即裁剪规则): 1、顶点 Pi 在内侧,前一顶点 Pi-1 也在内侧,则将 Pi 纳入新的顶点序列; 2、顶点 Pi 在内侧,前一顶点 Pi-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; else flag=1; 设新的顶点序列数 j=0; 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; ////////////////////////////////////////////////////////////////////////////////////// //-----多边形裁剪的Sutherland—Hodgman 算法---------// ///////////////////////////////////////////////////////////////////////////////////// void CMyClip_AView::ClipedgeL(CPoint polypoint[], CPoint clipwindow[],...