实验三指导书

实验三区域填充与直线的裁剪1．实验目的：1）实现种子填充法或扫描线算法中的一种。2）任选一种算法实现直线的裁剪。2．实验内容：编写区域填充和直线裁剪的源程序，并能在计算机上编译运行，画出正确的图形。3．实验步骤：1）对区域填充的几种算法进行理解；2）编程实现绘制多边形；3）对直线裁剪的几种算法进行理解；4）编程实现直线的裁剪；5）画出程序流程图；6）编写程序的源程序；7）编辑源程序并进行调试；8）进行特殊模式的运行测试，并结合情况进行调整。9）打印源程序或把源程序以文件的形式提交。4．实验报告：1）按格式书写实验报告；2）提交源程序文件或打印件。算法描述区域填充1)多边形由一系列首尾相连的直线段构成的图形称为多边形。如果在多边形内任意选取不相同的两点，其连线上的所有点均在该多边形内，这样的多边形称为凸多边形；否则，称为凹多边形。2)种子填充算法种子填充算法又称为边界填充算法。其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。种子填充算法常用四连通域和八连通域技术进行填充操作。从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。用这种方法填充的区域就称为四连通域；这种填充方法称为四向连通算法。从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。一般来说，八向连通算法可以填充四向连通区域，而四向连通算法有时不能填充八向连通区域。例如，八向连通填充算法能够正确填充如图2.4a所示的区域的内部，而四向连通填充算法只能完成如图2.4b的部分填充。四向连通填充算法a)连通域及其内点b)填充四连通域四向连通填充算法：a）种子像素压入栈中；b）如果栈为空，则转e)；否则转c)；c）弹出一个像素，并将该像素置成填充色；并判断该像素相邻的四连通像素是否为边界色或已经置成多边形的填充色，若不是，则将该像素压入栈；d）转b）；e）结束。四向连通填充方法可以用递归函数实现如下：四向连通递归填充算法：voidBoundaryFill4(intx,inty,longFilledColor,longBoundaryColor){ntColor!=BoundaryColor&&CurrentColor!=FilledColor)-1,y,FilledColor,BoundaryColor);daryColor);-1,FilledColor,BoundaryColor);}上述算法的优点是非常简单，缺点是需要大量栈空间来存储相邻的点。一个改进的方法就是：通过沿扫描线填充水平像素段，来处理四连通或八连通相邻点，这样就仅仅只需要将每个水平像素段的起始位置压入栈，而不需要将当前位置周围尚未处理的相邻像素都压入栈，从而可以节省大量的栈空间。3)其它填充算法扫描线填充算法是另一个常用的多边形填充算法。其基本思想是：对于一个给定的多边形，用一组水平或垂直的扫描线进行扫描，分别求出每条扫描线与多边形的交点，这些交点将扫描线分割为相间排列的落在多边形内和多边形外的线段，将落在多边形内的所有线段上的每个像素点赋以给定的多边形填充色。直线裁剪一、Cohen-Sutherland裁剪算法这个算法的特点是：通过初始测试来快速判断线段与视区的关系，以便减少线段求交的次数，从而提高裁剪算法的速度。区域编码假定以相对的两个角点（xmin，ymin）和（xmax，ymax）来表示一个矩形裁剪区域。如图3.9所示，将二维平面分区，中间的矩形为裁剪区域。每个区以四位代码（称为区域码）表示，代码的编号从右到左，各位与坐标区域的关系为：位1：左；位2：右；位3：下；位4：上。如果某一位赋值为1，则表示端点落在相应的位置上，否则该位值为0。通过比较端点的坐标与裁剪边界的坐标，可以迅速地决定区域码各位的值。例如：如果xxmin，则第一位置1；其它三位的值依此类推。对某线段的两个端点的区域码进行位与运算，可以快速判断哪条线段完全在裁剪窗口内，哪条线段完全在裁剪窗口外。完全在裁剪窗口内的线段的两个端点的区域码均为0000，该线段应当保留。两个端点的区域码的相同位的值都为1的线段则完全落在裁剪区域之外，该线段应当去除。例如，若线段的两端点的区域码分别为：code1=0101,code2=0110，则code1&code2=0100，表示该线段位于裁剪窗口的下方。显然，我们有：对线段的两个端点的区域码进行位与运算，若其结果不为0000，则线段完全位于裁剪窗口之外；若两个端点的区域码均为0000，则线段位于裁剪窗口内；否则，需要进一步计算线段与裁剪边界的交点，然后才能确定线段是完全位于裁剪窗口之外，还是一部分位于裁剪窗口之外另一部分位于裁剪窗口之内。Cohen-SutherLand裁剪算法的基本思想：对每条线段P1P2：1）判断端点在裁剪区域内、外：P1P2完全在视区内，保存之；P1P2完全在视区外，舍弃之；2）上述两条件均不满足，则计算图形与裁剪边界的交点，将该线段分为分别位于裁剪区域内、外的两段，再重复1）。在分段时，依据端点的区域码分别计算线段与各条裁剪边界的交点，如图3.10所示，对P1就需要分别计算交点P3和P4；即只要按顺序检测端点区域码的每一位，当某位不为0时，才把线段与对应的裁剪边界进行求交。二、中点分割算法与Cohen-Sutherland算法基本原理相似，只不过在第III种情况下是将线段分为均匀两段，分别测试，直至每条线段完全在裁剪区域内或裁剪区域外为止。中点分割裁剪算法设要被裁剪的线段是P0P1。为了避免将线段裁剪为许多零碎小段，只需分别计算距两个端点P0和P1最近的可见点A和B即可；这两个可见点的连线AB就是原线段的可见部分。从P0出发，计算其最近可见点的算法如下：1)计算出P0P1的中点Pm；2)计算P0和Pm的区域码的位与，若结果不等于0，则取PmP1代替P0P1；否则，取P0Pm代替P0P1；3)如果P1Pm的长度小于给定的容差，即|P1Pm|ε，转步4）；否则转步1）；4)结果输出：Pm就是P0的最近可见点。5)算法结束。如果将P0和P1交换，上述算法即为求P1点的最近可见点的算法。三、Liang-Barsky算法假设要被裁剪的线段为P0P1,如图3.12所示。线段P0P1的参数方程为：其中，Δx=x1-x0，Δy=y1-y0。该线段与裁剪边界的交于A、B、C和D四点，算法的核心是：从A、B和P0三点中找出离P1最近的点，以及从C、D和P1三点中找出离P0最近的点。图3.12中的P0和C点就是所要找的点。P0C就是原线段的可见部分。下面给出算法步骤：Liang-Barsky算法步骤：1)令u1=0.0，u2=1.0，k=1；2)按参数化形式写出裁剪条件：这4个表达式可以统一表示为：；其中，p1=-Δx,q1=x0-xmin;p2=Δx,q2=xmax-x0;p3=-Δy,q3=y0-ymin;p4=Δy,q4=ymax-y0。3)如果pk≠0：a)如果pk0，u1=max{u1,rk=qk/pk};b)如果pk0，u2=min{u2,rk=qk/pk};c)如果u1u2，则线段位于裁剪区域之外，舍弃之，转8)；否则，转5）；4)如果pk=0，则表示直线平行于第k条裁剪边界（k=1,2,3,4分别对应于左、右、下、上边界）。a)如果同时还满足qk0，则该线段完全在裁剪边界外，舍弃之，转8)；否则，转5）；5)k++;6)如果k≤4，转3）；否则，转7）；7)t∈[u1,u2]的线段就是原线段P0P1的可见部分，应当保存或显示；8)结束。Liang-Barsky算法四、参数化裁剪算法参数化裁剪算法又称为CyrusBeck裁剪算法。假设裁剪区域是一个凸多边形（见图3.13），其边数为n。Ai是它的第i条边界Ei上的一点，Ni为此处的法矢量。边界Ei将平面分为两半：Ni指向该边界的内侧半平面，它的反方向则称为该边界的外侧半平面。线段的参数方程为：。对于线段上的任意一点P(t)：1）0，P(t)在多边形内；2）=0，P(t)在多边形边界及其延长线上；3）0，P(t)在多边形外；P(t)在凸多边形内的充要条件是：≥0，，i=1,2,…,n。图3.13参数化裁剪即。令D＝P2-P1。如果Ni·D＝0，则表明：或者P1＝P2，即线段P1P2是一个点；或者线段P1P2与边界Ei平行（一般视为无交点，可以忽略）。如果P1＝P2，那麽：当0时，点P1位于裁剪区域内部；当＝0时，点P1位于裁剪边界上；当0时，点P1位于裁剪区域外部。如果Ni·D≠0，可以从上式得到线段P1P2与裁剪边界Ei的交点参数：。时，表明线段P1P2与裁剪边界Ei或Ei的延长线有交点；否则它们没有交点，可以忽略。虽然线段与凸多边形至多有2个交点，但是满足（）的交点可能有多个，每个交点对应于凸多边形的一条边界。当Ni·D0时，如果我们沿线段L1的端点P1向P2移动，就会跨越裁剪边界Ei而进入该边界的内侧半平面，其交点用PE表示（见图3.13，其交点参数值为t1。请在图中用动画表示出来。），它靠近线段的起点；这样的交点参数值的集合可以表示为PE（ti）＝{ti|Ni·D0，}。反之，Ni·D0时，如果我们沿线段L1的端点P1向P2移动，就会跨越裁剪边界Ei而离开该边界的内侧半平面，其交点用PL表示（见图3.12，其交点参数值为t5。请在图中用动画表示出来。），它靠近线段的终点；我们把这样的交点参数值的集合表示为PL（ti）＝{ti|Ni·D0，}。我们只要从PE（ti）中选出最大值，从PL（ti）中选取最小值，由参数范围（，）所定义的线段就是裁剪后的结果。考虑到参数的有效范围，我们有，。如果tEtL，如图3.12中的线段L2所示，则表明线段P1P2位于裁剪区域以外，整条线段都应当舍弃。当凸多边形为矩形且矩形的边平行于坐标轴时，上述算法可简化为Liang-Barsky算法。