多边形裁剪算法.doc

文档介绍：多边形裁剪的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多边形裁剪算法步骤
考虑多边形相对于一条边界及其延长线进行裁剪的算法:
[][2]、顶点序列数n、窗口一条边界参数xl(假如为矩形窗口的左边界);
:将顶点序列中的最后一个顶点赋给前一顶点S;
设置初始标志flag:
if(S在边界内侧)flag=0;
else flag=1;
设新的顶点序列数j=0;
,结果放入新的多边形顶点序列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;
}
:
将新的多边形顶点序列Q又逐一放回原多边形顶点序列P中:P=Q;
将新的多边形顶点数j放回原多边形顶点数n中:n=j;
//////////////////////////////////////////////////////////////////////////////////////
//-----多边形裁剪的Sutherland—Hodgman算法---------//
/////////////////////////////////////////////////////////////////////////////////////
void CMyClip_AView::ClipedgeL(CPoint polypoint[], CPoint clipwindow[], UINT polynum)
/*其中参数polypoint[]为多边形顶点,clipwindow[]为裁剪窗口顶点,polynum为多边形顶点数目*/
{
//找出裁剪窗口边界
long xl,xr,yt,yb;
UINT i;
xl=clipwindow[0].x;