3.4 多边形的扫描转换及区域填充
3.4.1 多边形的扫描转换
多边形是指由首尾相接的直线段组成的封闭图形。形成的这个封闭区域是多边形的内部，封闭区域外侧是多边形的外部，多边形的顶点即由直线段的端点组成，组成多边形边的直线段之间不能发生交叉现象。根据形状特点，多边形可以分为下面三种类型：
（1）凸多边形
凸多边形指任意两个顶点的连线都在多边形内部的多边形，如图3.4-1（a）所示。
（2）凹多边形
凹多边形指任意两个顶点的连线有不在多边形内部的多边形，如图3.4-1（b）所示。
（3）带内环的多边形
带内环的多边形指多边形内部还嵌套有多边形，如图3.4-1（c）所示。这时的多边形内部是指最外侧的多边形和嵌套的多边形之间的区域，如果有多个嵌套的多边形，则要求嵌套的多边形之间不能交叉，也不能再嵌套。嵌套的多边形又称为内环，最外侧的多边形称为外环。
图3.4-1 多边形的类型
计算机中多边形的表示方法有两种。
（1）顶点表示法
用多边形的顶点序列来表示多边形，如图3.4-2所示。顶点表示法的特点是直观、几何意义强，易于图形变换，而且占用内存较少，但是不能区分多边形的内外部。
图3.4-2 顶点表示法
（2）点阵表示法
用位于多边形内部的像素点集来表示多边形，如图3.4-3所示。点阵表示法的特点是可以明确多边形的内部区域，并将内部区域的像素点显示成要求的颜色，但是缺少多边形顶点的几何信息。
图3.4-3 点阵表示法
多边形的扫描转换就是把多边形从顶点表示转换为点阵表示。多边形的扫描转换又称为多边形的区域填充，即从多边形的顶点信息出发，求出多边形的内部区域的像素点，并用要求的颜色显示出来。
扫描线算法是一种常用的多边形区域填充算法，其基本原理是按扫描顺序，计算每条扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作。区间的端点可以通过计算扫描线与多边形边界线的交点获得，如图3.4-4所示。
图3.4-4 扫描线多边形填充算法
扫描线算法的核心：须按x的递增顺序排列扫描线与多边形边线的交点序列，并形成区间。算法步骤如下。
（1）确定多边形所占有的最大扫描线数：得到顶点的最小和最大y值（ymin和ymax）。
（2）从y＝ymin到y＝ymax每次用一条扫描线进行填充。
（3）对一条扫描线填充的过程可分为四个步骤。
①求交：计算扫描线与多边形各个边的交点。
②排序：将所有交点按x值的递增顺序排序。
③交点配对：将交点按递增顺序两两配成区间对，例如第一点和第二点、第三点和第四点分别组成区间对。交点对之间构成的区间就是多边形内部的像素点。
④区间填色：将区间对内的像素点设置成要求的颜色。
扫描线算法的原理简单，实施时需要提高算法的准确度和填充效率。算法准确度主要是指当扫描线通过多边形的顶点时，由于顶点是相邻两个边的共有点，那么同一个交点会计算两次，这时会存在交点数的取舍问题。如图3.4-5所示，当y＝1，5，7，8，9，12时，会通过多边形的顶点，顶点即交点，只有取合适的交点数，才能正确形成区间对。
图3.4-5 交点取舍
解决方法是，若共享顶点的两条边分别在扫描线的两侧，则交点只算一个；若共享顶点的两条边在扫描线的同一侧，这时交点记为零个或两个。可以通过检查共享顶点的两条边的另外两个端点的y值，按这两个y值中大于交点y值的个数来决定交点数取0、1或者2。若共享顶点的两条边分别在扫描线的两侧，在代码中编程时，可以通过将每条边的ymax减少一个单位，或者将ymin增加一个单位，实现只计算一个交点，如图3.4-6所示。
图3.4-6 共享顶点的两个边的处理
在应用程序中实现多边形扫描转换时，首先需要构造多边形。根据多边形的类型，多边形的结构类如下：
通过鼠标拾取屏幕点，并连接前后点和首尾相接，获得多边形的外环和内环，利用多边形数组得到多组多边形，如图3.4-7所示。
图3.4-7 多边形
上述的多边形扫描转换算法函数代码参考如下：
在上述的扫描线多边形填充算法中，需要求扫描线和多边形边的交点，并对交点进行排序，其中扫描线和多边形边的交点即为水平线和线段的交点，函数代码如下：
交点x值排序函数代码如下：
利用上述算法对图3.4-7所示的多边形进行扫描转换，效果如图3.4-8所示。
图3.4-8 多边形扫描转换
由于扫描线填充算法的时间主要花费在计算扫描线与多边形各边的求交运算上，因此提高多边形填充效率的方法是减少与多边形求交点的边数和降低求交工作量，在处理一条扫描线时，仅对和当前扫描线相交的有效边上点组成的区间对进行填充。为此，可以通过构造边表来表示和扫描线对应的有效边。方法如下。
（1）构造一个多边形的边表（ET），这个边表按照每个边的最小y值的增量进行排序。如果边的最小y值相等，则按照x的增量排序，如果x值也相等，则按照每条边的直线斜率k的倒数的增量排序。
（2）当沿着扫描线yscan进行扫描时，从边表中顺序取出最小y值和扫描线y相等的边，组成有效边表（AET），并对有效边表按照（1）的方式进行排序。然后按照x的增量顺序组成两两区间对，并对区间进行填充。
（3）每一个有效边的x值修改为
，最小y值修改为y＝ymin＝ymin+1。
（4）令扫描线yscan＝yscan+1，然后判断有效边表中每个边的最大y值，如果ymax＜yscan，说明该边不再和扫描线相交，则将该边从有效边表中删除，然后，转入（2）。
（5）当有效边表中有效边的数量为空的时候，说明已经处理到多边形最大y值，扫描转换结束。
上述的有效边表扫描线算法，对于每一个扫描线，只处理扫描线通过的边，在求交点时，是利用递推公式
计算的，因此扫描效率更高。
在构造每条边的信息时，需要包括：该边当前最小y值、当前对应的x值、该边最大y值以及该边斜率的倒数。当该边为特殊位置直线水平线时，斜率倒数为无穷大，为了准确记录边的信息，此时还应该记录该边另外一个顶点的x值信息；如果斜率倒数不为无穷大，则另一个顶点的x值可不必记录。因此，构造边结构如下：
对应的边类为：
图3.4-9所示为一多边形以及根据上述方法构造的边表。
图3.4-9 多边形及边表
在边表中，由于斜率倒数没有无穷大的情况，因此边表中的x另这一列不用登记。其中，在构造直线P2P3的节点时，在最大顶点即（1，7）处，由于共享该顶点的多边形另外一条边即P1P2分布在扫描线y＝7的另外一侧，考虑交点的取舍为题，将该直线的ymax减少一个单位，即节点值为边表值的第一行：
当扫描线y＝1时，从边表中取出有效边，通过排序组成有效边表，将有效边表中的边的x值两两构成区间对填充，然后修改有效边的值：
，如图3.4-10所示。如果ymax＜ymin，则该边已经处理完，不再为有效边，将其从有效边表中删除。
图3.4-10 扫描线y＝1
以此类推，当扫描线y＝2时，首先判断边表中是否存在有效边。如有，则取出插入现有的有效边表中，并排序，同样将有效边表中的边的x值两两构成区间对，填充，然后修改有效边的值：
，判断是否ymax＜ymin的情况，如图3.4-11所示。
图3.4-11 扫描线y＝2
循环执行上述操作，当ymax＜ymin时，从有效边表中删除已经处理完的边，例如，y＝5时，将P3P4以及P4P5两个边从有效边表中删除，当y＝7时，将P1P2边从边表中取出，插入有效边表并排序，开始填充，并重复上述的修改边的值以及判断操作。当边表中的所有边都已经取出，而且有效边表也成为空表，说明所有边都已经处理，此时多边形内部全部填充完毕，扫描转换结束，如图3.4-12所示。
图3.4-12 多边形填充
上述的有效边表多边形扫描转换算法函数代码参考如下：
函数中在构造多边形边表和有效边表时，都需要对插入边进行排序，函数代码如下：
执行应用程序即可实现填充。在应用程序中，可以设计一个非模式对话框，来选择不同的扫描转换算法，实现多边形填充，效果如图3.4-13所示。
图3.4-13 多边形扫描转换实现
除了上述的扫描线算法外，多边形扫描转换算法还有边缘填充法、栅栏填充法以及边界标志法等。
边缘填充算法的基本思想：按任意顺序处理多边形的每条边。处理时，先求出该边与扫描线的交点，再对扫描线上交点右方的所有像素颜色取反。边缘填充算法思路简单，但对于复杂图形，每一像素可能被访问多次。
栅栏填充算法是借助栅栏的原理来实现的，栅栏指的是一条通过多边形顶点且与扫描线垂直的直线，它把多边形分为两半。算法基本思想：按任意顺序处理多边形的每一条边，当处理每条边与扫描线的交点时，将交点与栅栏之间的像素取反。这种算法尽管减少了被重复访问像素的数目，但仍有一些像素被重复访问。
边界标志算法的基本思想：先用特殊的颜色在帧缓存中将多边形的边界勾画出来，然后将着色的像素点依x坐标递增的顺序配对，再把每一对像素构成的区间置为填充色。边界标志算法分为两个步骤：打标记；填充。当用软件实现本算法时，速度与改进的有效边表算法相当，但本算法用硬件实现后速度会有很大提高。
限于篇幅，本书对这些算法不再详述。
3.4.2 区域填充
这里的区域指已经表示成点阵形式的填充图形，它是像素的集合。区域可采用内点表示和边界表示两种表示形式。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。
区域填充分为两类：多边形的扫描转换与种子填充。两者的前提条件不同，前者需提供多边形各顶点的坐标及填充色或图案；后者则要求给出边界颜色特征及区域内的一个点（称为种子点）的坐标。多边形的扫描转换主要是通过确定穿越区域的扫描线的覆盖区间来填充，种子填充是从给定的位置开始涂描直到指定的边界条件为止。
区域填充要求区域是连通的。区域连通有四向连通区域和八向连通区域两种，如图3.4-14所示。四向连通区域指的是从区域上一点出发，通过上、下、左、右移动，即可到达区域内的任意像素；八向连通区域除了四向连通区域的四个方向外，还需要通过左上、右上、左下、右下这四个方向，才能到达区域内的任意位置。
图3.4-14 四向连通和八向连通
一般来说，八向连通算法可以填充四向连通区域，而四向连通算法有时不能填充八向连通区域。例如，八向连通填充算法能够正确填充图3.4-15所示的区域内部，而四向连通填充算法只能完成该区域的部分填充。
图3.4-15 连通区域
在编程时，上面的连通算法可以通过递归函数的方式实现。例如八向连通算法的递归函数的代码参考如下：
上述递归算法简单，但是效率不高，区域内每一个像素都引起一次递归，有些像素会多次重复递归判断。这样不但降低了算法效率，而且占用了很大的内存空间，费时费内存，在实际实现时，当图像相对比较复杂时会存在内存溢出的现象。
递归算法的一种改进方法是扫描线种子填充算法，其基本过程如下：当给定种子点（x，y）时，首先分别向左和向右两个方向填充种子点所在扫描线上的位于给定区域的一个区段，同时记下这个区段的范围［xLeft，xRight］，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复进行这个过程，直到填充结束。
扫描线种子填充算法可由下列四个步骤实现。
（1）初始化一个空的栈用于存放种子点，将种子点（x，y）入栈。
（2）判断栈是否为空，如果栈为空则结束算法，否则取出栈顶元素作为当前扫描线的种子点（x，y），y是当前的扫描线。
（3）从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xLeft和xRight。
（4）分别检查与当前扫描线相邻的y－1和y+1两条扫描线在区间［xLeft，xRight］中的像素，从xLeft开始向xRight方向搜索，若存在非边界且未填充的像素点，则找出这些相邻的像素点中最右边的一个，并将其作为种子点压入栈中，然后返回第（2）步。
上述扫描线种子填充算法，可以实现在已知区域的边界像素颜色或者已知区域内部的颜色这两种情况下，将区域内部用新的颜色填充。下面是已知区域内部颜色的填充函数参考代码，对于已知区域边界像素颜色的情况，只需将函数中判断区域内部颜色的代码改成判断区域边界颜色的代码即可。
其中，在一条扫描线上填充当前区段的函数代码如下：
处理相邻两条扫描线，并获得新种子入栈的函数代码如下：
