没有合适的资源?快使用搜索试试~ 我知道了~
多边形裁剪算法 计算机图形学
5星 · 超过95%的资源 需积分: 15 110 下载量 174 浏览量
2011-06-09
21:58:12
上传
评论 3
收藏 140KB DOC 举报
温馨提示
试读
13页
逐次多边形裁剪算法算法的思想发窗口四条边界单一逐次对多边形进行裁剪,每次用窗口的一条边界(包括延长线)对要裁剪的多边形进行裁剪,裁剪时,顺序地测试多边形各顶点,保留边界内侧的顶点,删除外侧的顶点,同时,适时地插入新的顶点:即交点和窗口顶点,从而得到一个新的多边形顶点序列。然后以此新的顶点序列作为输入,相对第二条窗边界线进行裁剪,又得到一个更新的多边形顶点序列依次下去,相对于第三条、第四条边界线进行裁剪,最后输出的多边形顶点序列即为所求的裁剪好了的多边形。
资源推荐
资源详情
资源评论
实验三 多边形裁剪算法
一、 实验原理:
逐次多边形裁剪算法算法的思想发窗口四条边界单一逐次对多边形进行裁剪,每次用窗口的一条边
界(包括延长线)对要裁剪的多边形进行裁剪,裁剪时,顺序地测试多边形各顶点,保留边界内侧的顶点,
删除外侧的顶点,同时,适时地插入新的顶点:即交点和窗口顶点,从而得到一个新的多边形顶点序列。
然后以此新的顶点序列作为输入,相对第二条窗边界线进行裁剪,又得到一个更新的多边形顶点序列依
次下去,相对于第三条、第四条边界线进行裁剪,最后输出的多边形顶点序列即为所求的裁剪好了的多
边形。
二、算法推导:
新的多边形顶点序列产生规则:
在用窗口一条边界及其延长线裁剪一个多边形时,该边界线把平面分成两个部分:一部分称为
边界内侧;另一部分称为边界外侧。
如下图所示,依序考虑多边形的各条边。假设当前处理的多边形的边为 SP(箭头表示顺序关系,
S 为前一点,P 为当前点),边 SP 与裁剪线的位置关系只有下面四种情况:
1、S 在外侧,P 在内侧。则交点 Q、当前点 P 保存到新多边形中。
2、S、P 均在内侧,则当前点 P 保存到新多边形中。
3、S 在内侧,P 在外侧。则交点 Q 保存到新多边形中。
4、S、P 均在外侧。则没有点被保存到新多边形中。
1、已知:多边形顶点数组 p[ ][2],顶点个数 n,
裁剪边界 xmin(假设对左边界进行裁剪),
定义新多边形顶点数组 q[][2]。
2、赋初值:被裁多边形顶点数组的下标变量 i=0;
新多边形顶点数组的下标变量 j=-1;
前一个点 S 的 x 方向分量 s[0]=p[n-1][0];
S 的 y 方向分量 s[1]=p[n-1][1];
前一个点 S 的内外标志,用变量 ag 来标识:
0 表示在内侧,1 表示在外侧。
if(s 在边界内侧) /*例如对左边界:s[0]>=xmin*/
ag=0;
第 1 页 共 13 页
else
ag=1;
3、对多边形的 n 条边进行处理,对当前点号的考虑为:0~n-1。
for(i=0;i<n;i++)
{
if(当前第 i 个顶点是否在边界内侧?) /*对左边界:p[i][0]>=xmin */
{
if(ag!=0) /*前一个点在外侧吗?*/
{
ag=0;/*从外到内的情况,将标志置 0,作为下一次循环的前一点标志*/
j++;
q[j][0]=求出交点的 x 方向分量; /*将交点 q 放入新多边形*/
q[j][1]=求出交点的 y 方向分量;
}
j++;
q[j][0]= p[i][0]; /*将当前点 pi 放入新多边形*/
q[j][1]= p[i][1];
}
else
{
if(ag==0) /*前一个点在内侧吗?*/
{
ag=1;/*从内到外的情况,将标志置 1,作为下一次循环的前一点标志*/
j++;
q[j][0]=求出交点的 x 方向分量; /*将交点 q 放入新多边形*/
q[j][1]=求出交点的 y 方向分量;
}
}
s[0]=p[i][0]; /*将当前点作为下次循环的前一点*/
第 2 页 共 13 页
s[1]=p[i][1];
}
二、 程序流程图
三、 详细算法:
void CMy200915303View::Duobianxingcut(CRect rect)
{
CPoint rectPoint[4];
rectPoint[0].x = rect.left;
rectPoint[0].y = rect.top;
rectPoint[1].x = rect.right;
rectPoint[1].y = rect.top;
rectPoint[3].x = rect.left;
rectPoint[3].y = rect.bottom;
rectPoint[2].x = rect.right;
rectPoint[2].y = rect.bottom;
第 3 页 共 13 页
开始
画边形并保存所有结点
确定裁剪区域
判断两点 A B 与
边界相交
Y
求 A.B 与裁剪线的交点
保存点
n
输出
结束
剩余12页未读,继续阅读
rui_tao
- 粉丝: 1
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
- 1
- 2
前往页