线段与多边形的裁剪题库.doc

一、实验目标1. CohenSutherland 线段裁剪；2. LiangBarsky线段裁剪；3. SutherlandHodgeman 多边形裁剪；二、实验内容一、实验内容在给定的MFC程序模板中添加Cohen_Sutherland 线段裁剪、Liang_Barsky x线段裁剪、Sutherland_Hodgeman 多边形裁剪，生成新的程序窗口中要有Cohen_Sutherland 线段裁剪、Liang_Barsky x线段裁剪、Sutherland_Hodgeman 多边形裁剪的菜单按钮，点击按钮分别弹出Cohen_Sutherland 线段裁剪、Liang_Barsky 线段裁剪、Sutherland_Hodgeman 多边形裁剪的窗口，通过点击鼠标操作实现裁剪框和线段以及多边形的定义和裁剪。 二、实验原理 1. Cohen_Sutherland 线段裁剪 该算法也称为编码算法，首先对线段的两个端点按所在的区域进行分区编码，根据编码可以迅速地判明全部在窗口内的线段和全部在某边界外侧的线段。只有不属于这两种情况的线段，才需要求出线段与窗口边界的交点，求出交点后，舍去窗外部分。对剩余部分，把它作为新的线段看待，又从头开始考虑。两遍循环之后，就能确定该线段是部分截留下来，还是全部舍弃。n 编码延长裁剪边框将二维平面分成九个区域，每个区域各用一个四位二进制代码标识。各区代码值如图中所示。四位二进制代码的编码规则是：(1)第一位置1：区域在左边界外侧 (2)第二位置1：区域在右边界外侧(3)第三位置1：区域在下边界外侧 (4)第四位置1：区域在上边界外侧裁剪窗口内（包括边界上）的区域，四位二进制代码均为0。设线段的两个端点为P1（x1，y1）和P2（x2，y2），根据上述规则，可以求出P1和P2所在区域的分区代码C1和C2。n 判别根据C1和C2的具体值，可以有三种情况：（1）C1=C20，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。（2）C1&C20（两端点代码按位作逻辑乘不为0），即C1和C2至少有某一位同时为1，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。（3）不属于上面两种情况，均需要求交点。n 求交点假设算法按照：左、右、下、上边界的顺序进行求交处理，对每一个边界求完交点，并相关处理后，算法转向第2步，重新判断，如果需要接着进入下一边界的处理。为了规范算法，令线段的端点P1为外端点，如果不是这样，就需要P1和P2交换端点。当条件 (C1&00010) 成立时，表示端点P1位于窗口左边界外侧，按照下面的求交公式，进行对左边界的求交运算。依次类推，对位于右、下、上边界外侧的判别，应将条件式中的0001分别改为0010、0100、1000即可。求出交点P后，用P1=P来舍去线段的窗外部分，并对P1重新编码得到C1，接下来算法转回第2步继续对其它边界进行判别。2 .Liang Barsky 线段裁剪我们知道，一条两端点为P1（x1，y1）、P2（x2，y2）的线段可以用参数方程形式表示：式中，x=x2-x1，y=y2-y1，参数u在01之间取值，P（x，y）代表了该线段上的一个点，其值由参数u确定，由公式可知，当u=0时，该点为P1（x1，y1），当u=1时，该点为P2（x2，y2）。如果点P（x，y）位于由坐标（xwmin，ywmin）和（xwmax，ywmax）所确定的窗口内，那么下式成立：这四个不等式可以表示为：其中，p、q定义为：从（3-12）式可以知道：任何平行于窗口某边界的直线，其pk=0，k值对应于相应的边界（k=1，2，3，4对应于左、右、下、上边界）。如果还满足qk<0，则线段完全在边界外，应舍弃该线段。如果pk=0并且qk0，则线段平行于窗口某边界并在窗口内，见图中所示。公式（3-12）式还告诉我们：1、当pk<0时，线段从裁剪边界延长线的外部延伸到内部；2、当pk>0时，线段从裁剪边界延长线的内部延伸到外部；当x0时，对于左边界p1<0（p1=-x），线段从左边界的外部到内部；对于右边界p2>0（p2=x），线段从右边界的内部到外部。当y<0时，对于下边界p3>0（p3=-y），线段从下边界的内部到外部；对于上边界p4<0（p4=y），线段从上边界的外部到内部。当pK0时，可以计算出参数u的值，它对应于无限延伸的直线与延伸的窗口边界k的交点，即：对于每条直线，可以计算出参数u1和u2，该值定义了位于窗口内的线段部分：1、u1的值由线段从外到内遇到的矩形边界所决定（pk<0），对这些边界计算rk=qk/pk，u1取0和各个r值之中的最大值。2、u2的值由线段从内到外遇到的矩形边界所决定（pk>0），对这些边界计算rk=qk/pk，u2取0和各个r值之中的最小值。3、如果u1>u2，则线段完全落在裁剪窗口之外，应当被舍弃；否则，被裁剪线段的端点可以由u1和u2计算出来。3 .Sutherland Hodgeman 多边形裁剪每次用窗口的一条边界(包括延长线)对要裁剪的多边形进行裁剪，裁剪时，顺序地测试多边形各顶点，保留边界内侧的顶点，删除外侧的顶点，同时，适时地插入新的顶点：即交点和窗口顶点，从而得到一个新的多边形顶点序列。然后以此新的顶点序列作为输入，相对第二条窗边界线进行裁剪，又得到一个更新的多边形顶点序列。依次下去，相对于第三条、第四条边界线进行裁剪，最后输出的多边形顶点序列即为所求的裁剪好了的多边形。如下图所示：新的多边形顶点序列产生规则：在用窗口一条边界及其延长线裁剪一个多边形时，该边界线把平面分成两个部分：一部分称为边界内侧；另一部分称为边界外侧。如下图所示,依序考虑多边形的各条边。假设当前处理的多边形的边为SP(箭头表示顺序关系，S为前一点，P为当前点)，边SP与裁剪线的位置关系只有下面四种情况：1. S在外侧，P在内侧。则交点Q、当前点P保存到新多边形中2. S、P均在内侧，则当前点P保存到新多边形中。3. S在内侧，P在外侧。则交点Q保存到新多边形中。4. S、P均在外侧。则没有点被保存到新多边形中。三、实验步骤 1. 打开程序模板，在资源视图中点击cgdemo，在下拉文件中点击menu，然后双击IDR_MAINFRAME，在右边打开的窗口中分别添加Cohen_Sutherland 线段裁剪、Liang_Barsky 线段裁剪、Sutherland_Hodgeman 多边形裁剪菜单按钮并编辑；2. 在解决方案资源管理器中，点击cgdemo，在下拉文件Header Files中点击cgdemoView.h，在cgdemoView.h头文件中添加Cohen_Sutherland 线段裁剪、Liang_Barsky x线段裁剪、Sutherland_Hodgeman 多边形裁剪的一些定义；再双击下拉文件Source Files中的cgdemoView.cpp，在标准打印命令中分别添加ON_COMMAND(ID_COHEN_SUTHERLAND, &CcgdemoView:OnCohenSutherland)ON_COMMAND(ID_LIANG_BARSKY, &CcgdemoView:OnLiangBarsky)ON_COMMAND(ID_SUTHERLAND_HODGEMAN,&CcgdemoView:OnSutherlandHodgeman)3. 在CcgdemoView 绘制中分别添加绘制递归种子填充、简单种子填充、扫描线种子填充，区域图案填充的else if语句；在CcgdemoView 消息处理程序中添加Cohen_Sutherland 线段裁剪、Liang_Barsky x线段裁剪、Sutherland_Hodgeman 多边形裁剪的case语句；CcgdemoView 事件处理程序中分别定义了：void CcgdemoView:OnCohenSutherland()/ TODO: Add your command handler code herem_drawstyle = COHEN_SUTHERLAND;Invalidate(true);void CcgdemoView:OnLiangBarsky()/ TODO: Add your command handler code herem_drawstyle = LIANG_BARSKY;Invalidate(true);void CcgdemoView:OnSutherlandHodgeman()/ TODO: Add your command handler code herem_drawstyle = SUTHERLAND_HODGEMAN;Invalidate(true);4. 在cgdemoView.cpp的最后分别编写Cohen_Sutherland 线段裁剪的程序：void CohenSutherland(CDC* pDC, CPoint P_begin, CPoint P_end);Liang_Barsky线段裁剪的程序：void LiangBarsky(CDC* pDC, CPoint P_begin, CPoint P_end);Sutheland_Hodgeman多边形裁剪程序：void SutherlandHodgeman(CDC* pDC, CArray<CPoint,CPoint&>&arr_pt);5. 运行调试程序。四、实验遇到的问题及其解决方法(1) 在调试程序时发现程序运行完并正确达到裁减效果，可是窗口点击放大后，裁剪画面消失；为此将画图的程序语句放在裁剪程序框架外，以解决此问题。(2) 在CohenSutherland 线段裁剪程序编写时，由于k = float (P_end.y - P_begin.y) / float (P_end.x - P_begin.x);求斜率的程序语句未添加float 将k 整型，使得线段短点逐渐靠近裁剪框交点的过程中，误差变化越来越大，裁减效果不是预期想要的效果。(3) 在LiangBarsky 线段裁剪程序编写时，在根据最后得到的U1和U2求新端点坐标的程序语句编写如下：P_begin.x = P_begin.x - u1 * (P_begin.x - P_end.x);P_begin.y = P_begin.y - u1 * (P_begin.y - P_end.y);P_end.x = P_begin.x - u2 * (P_begin.x - P_end.x);P_end.y = P_begin.y - u2 * (P_begin.y - P_end.y);由于求新的裁剪后线段终点坐标时，受到上面已经改变的新的起点坐标的影响，使得第二个点求的不正确，在程序运行效果时候表现为：第二个裁剪点明显不符合预期的效果。后更改程序如下，则求新的起始点和新的终点坐标互不影响，程序运行正常P1.x = P_begin.x - u1 * (P_begin.x - P_end.x);P1.y = P_begin.y - u1 * (P_begin.y - P_end.y);P2.x = P_begin.x - u2 * (P_begin.x - P_end.x);P2.y = P_begin.y - u2 * (P_begin.y - P_end.y);(4) 在SutherlandHodgeman 多边形裁剪的程序编写时：if (i =0)point_pre = arr_ptn-1; / 当前顶点的前一个点else point_pre = arr_pti-1; / 当前顶点的前一个点由于将 if判断语句 if (i = 0) 误写为if (i = 0)，使得程序运行出现错误五、实验结论和收获1. 通过本次实验进一步加深了对VS2008的编程环境的了解以及MFC编程的流程更加熟悉；2. 通过编写程序加深了对Cohen_Sutherland 线段裁剪、Liang_Barsky x线段裁剪、Sutherland_Hodgeman 多边形裁剪的算法原理的理解。8