第四章--多边形的扫描转换和区域填充

青岛农业大学青岛农业大学第4章多边形的扫描转换和区域填充青岛农业大学扫描转换和区域填充这个问题是怎样在离散的像素集上表示一个连续的二维图形。多边形有两种重要的表示方法：顶点表示和点阵表示。点阵表示P1P2P3P4P5顶点表示P6前言青岛农业大学前言顶点表示用多边形的顶点序列来刻画多边形特点表示方法直观，几何意义强，占内存空间少，但没明确指明哪些像素在多边形内，不能直接用于面着色。P1P2P3P4P5顶点表示P6青岛农业大学前言点阵表示点阵表示用位于多边形内部的像素集合来刻画多边形特点会失去很多重要的几何信息，不过它是光栅显示系统显示面着色时所需的图形表示形式。青岛农业大学前言把多边形的顶点表示转换为点阵表示，这种转换称为多边形的扫描转换。即，从多边形的给定边界出发，求出位于其内部的各个像素，并给帧缓存器内的各个对应元素设置相应的灰度或颜色。多边形扫描转换主要用来填充多边形区域以及由多边形拟合的其它简单曲线区域。取点阵表示的多边形区域的一点，并赋予指定的颜色和灰度，然后将该颜色和灰度扩展到整个区域内的过程。多边形的扫描转换区域填充主要用在具有复杂形状边界的多边形以及交互绘图系统中。青岛农业大学内容提要多边形的扫描转换区域填充技术直线的扫描转换反走样青岛农业大学4.1.1多边形的扫描转换多边形可以为凸多边形、凹多边形、含内环的多边形等：（1）凸多边形任意两顶点间的连线均在多边形内。（2）凹多边形任意两顶点间的连线有不在多边形内的部分。凸多边形凹多边形含内环的多边形青岛农业大学4.1.2逐点判断算法基本思想：逐个判断绘图窗口内的像素，确定它们是否在多边形区域内部，从而求出位于多边形区域内的像素的集合。常用方法射线法青岛农业大学4.1.2逐点判断算法•基本思想：由被测点向某方向作射线，计算此射线与多边形所有边的交点个数，用交点个数的奇偶性判别多边形与点的关系。•判断依据：若交点个数为奇数，则被测点在多边形内部；若交点个数为偶数（包括0），则该点在多边形的外部。射线法ACBDabdc青岛农业大学4.1.2逐点判断算法射线f过顶点，若将交点计数为2，则F点在多边形外。但若规定射线过顶点时，计数为1，则E在多边形内。efEF12345AB问题：当射线恰好通过多边形的顶点时，怎么判断？青岛农业大学4.1.2逐点判断算法点A:0个交点，在多边形外点B:1个交点，在多边形内点C：3个交点，在多边形内点D:1个交点，在多边形内点E:2个交点，在多边形外点F:1个交点，在多边形内（剔除重合边）f措施在射线左边的边与该射线相交时交点有效，应计数；而在射线右边的边与射线相交时交点无效，不计数。（左闭右开原则）青岛农业大学4.1.2逐点判断算法•算法实现voidFillPolygonPbyP(Polygon*P,intpolygonColor){intx,y;for(y=ymin;y=ymax;y++)for(x=xmin;x=xmax;x++)if(IsInside(P,x,y))PutPixel(x,y,polygonColor);elsePutPixel(x,y,backgroundColor);}/*endofFillPolygonPbyP()*/青岛农业大学4.1.2逐点判断算法•算法特点简单速度太慢由于该算法割断了各像素之间的联系，孤立地考察各像素与多边形的内外关系，使得几十万甚至几百万个像素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算，花费很多时间。青岛农业大学4.1.3扫描线算法♣一条扫描线上的像素存在着相关性♣在多边形边处，像素性质才发生变化♣将相邻像素放在一起测试，从而减少测试点的数目区域特点扫描线的连贯性青岛农业大学4.1.3扫描线算法–目标：利用相邻像素之间的连贯性，提高算法效率–处理对象：非自相交多边形（自相交多边形指一个顶点对应的边数大于2）青岛农业大学4.1.3扫描线算法基本思想对每一条扫描线，计算扫描线与多边形边界的交点，直接连接扫描线在多边形内的每两个相邻交点，其间的所有像素就一次显示了。然后扫描线上升（下降）一个像素，重复上述工作，直至完成全部填充工作。0246810122468101234青岛农业大学求出一根扫描线与多边形各边的交点：对求得的交点进行排序：奇偶配对求出扫描线与多边形的相交区间：对这些相交区间填充。012345671234567yx88910扫描线5P4P1P2P3P5扫描线2I1I2I3I4I4,I3,I2,I1I1,I2,I3,I4(I1,I2),(I3,I4)4.1.3扫描线算法青岛农业大学4.1.3扫描线算法存在问题当扫描线与多边形的顶点相交时，会出现异常情况。问题1：如何取舍重交点，保证交点正确配对？青岛农业大学4.1.3扫描线算法-顶点交点计数具体实现：检查重交点对应的两条边的另外两个端点的y值，按这两个y值中大于顶点y值的个数是0、1、2来决定交点是计0次、1次还是2次。解决方法重交点的两条边分别落在扫描线两边，取交点1次。重交点的两条边均高于扫描线，取交点2次。重交点的两条边均低于扫描线，取交点0次。检查重交点的两相邻边在扫描线的哪一侧青岛农业大学4.1.3扫描线算法012345671234567yx012345671234567yxP1P2P3P4填充扩大化：多边形边界上像素的也被填充。问题2：避免填充扩大化？存在问题青岛农业大学4.1.3扫描线算法-填充扩大化012345671234567yx012345671234567yxP1P2P3P4012345671234567yx012345671234567yxP1P2P3P4解决方法规定落在右/上边界的像素不予填充，而落在左/下边界的像素予以填充。具体实现：对扫描线与多边形的相交区间，取“左闭右开”，如【1，5），问题1保证了多边形的“下闭上开”青岛农业大学9.3.1扫描线填充算法可以从三方面考虑加以改进以提高算法效率：（1）在处理一条扫描线时，仅对和它相交的多边形的边（有效边）进行求交运算。（2）需要考虑多边形的连贯性，即当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序很可能相同或非常相似，这样在当前扫描线处理完毕之后，不必为下一条扫描线从头开始构造交点信息。青岛农业大学9.3.1扫描线填充算法（3）最后考虑边的连贯性，即当某条边与当前扫描线相交时，它很可能也与下一条扫描线相交。青岛农业大学4.1.3扫描线算法—数据结构随着扫描线的移动，扫描线与多边形的交点和上一次交点相关：设边的直线斜率为k，则，△x=1/k活性边表(AET)：把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中。结点内容x：当前扫描线与边交点的x坐标△x：从当前扫描线到下一条扫描线间x的增量ymax：该边所交的最高扫描线的坐标值ymax(xi,yi）1△x(xi+1,yi+1)即△x=1/k为常量。则下一条扫描线与该边的交点不要重新计算，只要加一个增量△x。如何判断多边形的一条边是否与扫描线相交？青岛农业大学x△xymaxnext其中x为当前扫描线与边的交点，ymax是边所在的最大扫描线值，通过它可以知道何时才能“抛弃”该边，△x表示从当前扫描线到下一条扫描线之间的x增量即斜率的倒数。next为指向下一条边的指针综上所述，活性边表AET的每个结点存放对应边的有关信息如下：4.1.3扫描线算法—数据结构注:对每条与多边形相交的扫描线都会有一个AET青岛农业大学0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)一个多边形与若干扫描线2073.5-1.57P6P1P5P6AB7281108P4P5P3P4CD△xymax△xymax△xymax△xymax看扫描线y=6的活性边表：4.1.3扫描线算法—数据结构青岛农业大学4.1.3扫描线算法—数据结构活性边表的更新节点更新新边插入旧边删除青岛农业大学4.1.3扫描线算法—数据结构为了方便活性边表的建立与更新，需构造一个新边表（NET），用来存放多边形的边的信息，分为3个步骤：（1）首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，对应多边形覆盖的每一条扫描线。（2）将每条边的信息链入与该边最小y坐标（ymin）相对应的桶处。也就是说，存放着该扫描线第一次出现的边。若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中。青岛农业大学4.1.3扫描线算法—数据结构（3）每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大y值ymax。x1/kymaxnext青岛农业大学4.1.3扫描线算法—数据结构0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)一个多边形与若干扫描线765432108P4P5P5P65285-1.57这个结构实际上是一个指针数组，数组的每个变量是个指针，这个指针指向所有的以这个y值作为起点的边。把多边形所有的边全部填成这样的结构，插到这个指针数组里面来。如y=1,y=5指向哪些边？5-32P1P2P2P35332071108P6P1P3P4青岛农业大学4.1.3扫描线算法步骤1、建立NET表；2、将扫描线纵坐标y的初值置为NET中非空元素的最小序号3、置AET为空；4、执行下列步骤直至NET和AET都为空．4.1、如NET中的第y类非空，则将其中的所有边取出并插入AET中；4.2、如果有新边插入AET，则对AET中各边排序；4.3、对AET中的边两两配对，获得有效填充区段，再填充．4.4、将当前扫描线纵坐标y值递增1；4.5、将AET中满足ymax≤y边删去4.6、对AET中剩下的每一条边的x递增Δx，即x=x+Δx．青岛农业大学4.1.3扫描线算法新边表876543210∧∧∧∧∧528.5-1.57∧1108∧207∧3∧5-32.53P4P5P5P6P3P4P6P1P1P2P2P34x0123456789101112345678P6P4P1P5P2P3533∧P1P2P2P35-32.y=1207.833∧P6P1P2P3y=2207.1108∧P6P1P3P4y=3528.P4P51108∧P3P45-1.57P5P6207.P6P1y=5728.P4P51108∧P3P43.5-1.57P5P6207.P6P1y=6青岛农业大学4.1.3扫描线算法算法的执行过程5335-32.P1P2P2P3y=1∧207.833∧P6P1P2P3y=2207.1108∧P6P1P3P4y=3从新边表中取出与扫描线y=1相交的初始边排序放入活性边表中，填充交点之间的区域更新边表，删除P1P2，插入新边P6P1，填充交点之间的区域更新边表，删除P2P3，插入新边P3P4，填充交点之间的区域青岛农业大学4.1.3扫描线算法528.P4P51108∧P3P45-1.57P5P6207.P6P1y=5728.P4P51108∧P3P43.5-1.57P5P6207.P6P1y=6928.P4P51108∧P3P4y=7更新边表，插入新边P5P6和P4P5，填充两对交点之间的区域更新边表，填充两对交点之间的区域更新边表，删除P6P1和P5P6，填充交点之间的区域更新边表，删除P4P5和P3P4，活性边表为空，没有新边，填充算法结束y=8如何填充?青岛农业大学4舍？还是5入?当交点的x坐标值是小数时需进行舍入运算。(b)左端点:向上取整(a)右端点:向下取整青岛农业大学4.1.3扫描线算法例：如下图所示多边形，若采用扫描线算法进行填充，试写出该多边形的新边表（NET表）和当扫描线Y=3时的活性边表（AET表）。x3A(2,1)C(6,5)B(6,1)D(4,3)E(2,5)F(1,4)y01