多边形裁剪的Sutherland―Hodgman算法
时间:2008-11-24 00:12:20 来源:Internet 作者: 点击量:993
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[], UINT polynum)
/*其中参数polypoint[]为多边形顶点,clipwindow[]为裁剪窗口顶点,polynum为多边形顶点数目*/
{
- 1
- 2
前往页