线段与多边形的裁剪题库

1、一、实验目标1. CohenSutherland 线段裁剪；2. LiangBarsky 线段裁剪；3. SutherlandHodgeman 多边形裁剪；二、实验内容一、实验内容在给定的 MFC 程序模板中添加Cohen_Sutherland 线段裁剪、Liang_Barsky x线段裁 剪、 Sutherland_Hodgeman 多边形裁剪， 生成 新的程 序窗口中要有Cohen_Sutherland 线段裁剪、Liang_Barsky x 线段裁剪、Sutherland_Hodgeman 多边形裁剪的菜单 按钮 ，点 击按 钮分 别弹出Cohen_Sutherland 线段裁剪、Lia

2、ng_Barsky 线段裁剪、 Sutherland_Hodgeman 多边形裁剪的窗口， 通过点击鼠标操作实现裁剪框和线段以及多边形的定义和裁剪。二、实验原理1. Cohen_Sutherland 线段裁剪该算法也称为编码算法，首先对线段的两个端点按所在的区域进行分区编码，根据编码可以迅速地判明全部在窗口内的线段和全部在某边界外侧的线段。只有不属于这两种情况的线段， 才需要求出线段与窗口边界的交点， 求出交点后，舍去窗外部分。对剩余部分，把它作为新的线段看待，又从头开始考虑。两遍循环之后，就能确定该线段是部分截留下来，还是全部舍弃。编码延长裁剪边框将二维平面分成九个区域， 每个区域各用一个四

3、位二进制代码标识。各区代码值如图中所示。四位二进制代码的编码规则是：(1) 第一位置 1：区域在左边界外侧 (2) 第二位置 1：区域在右边界外侧(3) 第三位置 1：区域在下边界外侧(4) 第四位置 1：区域在上边界外侧1裁剪窗口内（包括边界上）的区域，四位二进制代码均为 0。设线段的两个端点为 P1（x1，y1）和 P2（x2，y2），根据上述规则，可以求出 P1 和 P2 所在区域的分区代码 C1 和 C2。判别根据 C1 和 C2 的具体值，可以有三种情况：（1）C1=C20，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。（2）C1&C20（两端点代码按位作逻辑乘不为0

4、），即 C1 和 C2 至少有某一位同时为 1，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。（3）不属于上面两种情况，均需要求交点。求交点假设算法按照：左、右、下、上边界的顺序进行求交处理，对每一个边界求完交点，并相关处理后，算法转向第 2 步，重新判断，如果需要接着进入下一边界的处理。为了规范算法，令线段的端点 P1 为外端点，如果不是这样，就需要 P1 和 P2 交换端点。当条件 (C1&0001 0) 成立时，表示端点 P1 位于窗口左边界外侧，按照下面的求交公式，进行对左边界的求交运算。依次类推，对位于右、下、上边界外侧的判别， 应将条件式中的0001

5、 分别改为 0010、0100、1000 即可。求出交点 P 后，用 P1=P来舍去线段的窗外部分，并对P1 重新编码得到 C1，接下来算法转回第2 步继续对其它边界进行判别。22 .Liang Barsky 线段裁剪我们知道，一条两端点为P1（x1，y1）、 P2（x2，y2）的线段可以用参数方程形式表示：式中，x=x21 ，y=y21，参数 u 在 01 之间取值， P（ x，y）代表了该-x-y线段上的一个点，其值由参数u 确定，由公式可知，当u=0 时，该点为 P1（ x1，y1），当 u=1 时，该点为 P2（x2， y2）。如果点 P（x， y）位于由坐标（ xwmin ，ywmi

6、n）和（ xw max， ywmax）所确定的窗口内，那么下式成立：这四个不等式可以表示为：其中， p、q 定义为：从（3-12）式可以知道：任何平行于窗口某边界的直线，其pk，k值对应=0于相应的边界（ k=1，2， 3，4 对应于左、右、下、上边界）。如果还满足qk ，<0则线段完全在边界外，应舍弃该线段。如果pk=0并且 k0，则线段平行于窗口q某边界并在窗口内，见图中所示。公式（3-12）式还告诉我们：31、当 pk<0 时，线段从裁剪边界延长线的外部延伸到内部；2、当 pk>0 时，线段从裁剪边界延长线的内部延伸到外部；当 x0时，对于左边界 p1<0（ p1

7、=-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 的值由线段

8、从内到外遇到的矩形边界所决定（pk>0），对这些边界计算 rk=qk/pk，u2 取 0 和各个 r 值之中的最小值。3、如果 u1>u2，则线段完全落在裁剪窗口之外，应当被舍弃；否则，被裁剪线段的端点可以由u1 和 u2 计算出来。3 .Sutherland Hodgeman 多边形裁剪每次用窗口的一条边界 ( 包括延长线 ) 对要裁剪的多边形进行裁剪，裁剪时，顺序地测试多边形各顶点，保留边界内侧的顶点，删除外侧的顶点，同时，适时地插入新的顶点： 即交点和窗口顶点， 从而得到一个新的多边形顶点序列。然后4以此新的顶点序列作为输入， 相对第二条窗边界线进行裁剪， 又得到一个更新的多

9、边形顶点序列。依次下去，相对于第三条、第四条边界线进行裁剪，最后输出的多边形顶点序列即为所求的裁剪好了的多边形。如下图所示：新的多边形顶点序列产生规则：在用窗口一条边界及其延长线裁剪一个多边形时， 该边界线把平面分成两个部分：一部分称为边界内侧；另一部分称为边界外侧。如下图所示 , 依序考虑多边形的各条边。假设当前处理的多边形的边为SP(箭头表示顺序关系， S 为前一点， P 为当前点 ) ，边 SP与裁剪线的位置关系只有下面四种情况：1. S 在外侧， P 在内侧。则交点 Q、当前点 P 保存到新多边形中2. S 、P 均在内侧，则当前点 P 保存到新多边形中。3. S 在内侧， P 在外侧

10、。则交点 Q保存到新多边形中。4. S 、P 均在外侧。则没有点被保存到新多边形中。5三、实验步骤1. 打开程序模板，在资源视图中点击 cgdemo，在下拉文件中点击 menu，然后双击 IDR_MAINFRAME ，在右边打开的窗口中分别添加 Cohen_Sutherland线段裁剪、 Liang_Barsky 线段裁剪、 Sutherland_Hodgeman 多边形裁剪菜单按钮并编辑；2. 在解决方案资源管理器中，点击 cgdemo，在下拉文件 Header Files中点击 cgdemoView.h，在 cgdemoView.h 头文件中添加 Cohen_Sutherland 线段裁剪

11、、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

12、)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 = CO

13、HEN_SUTHERLAND;Invalidate(true);6void CcgdemoView:OnLiangBarsky()/ TODO: Add your command handler code here m_drawstyle = LIANG_BARSKY; Invalidate(true);void CcgdemoView:OnSutherlandHodgeman()/ TODO: Add your command handler code here m_drawstyle = SUTHERLAND_HODGEMAN; Invalidate(true);4. 在 cgdemoVi

14、ew.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. 运行调试程序。四、实验遇到的

15、问题及其解决方法(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_

16、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);7由于求新的裁剪后线段终点坐标时， 受到上面已经改变的新的起点坐标的影响，使得第二个点求的不正确， 在程序运行效果时候表现为： 第二个裁剪点明显不符合预期的效果。后更改程序如下，则求新的起始点和新的终点坐标互不影响，程序运行正常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)poin