区域填充算法和多边形填充的扫描线算法
本文主要介绍几种区域填充算法，重点解释多边形的扫描线填充算法，最后实现了多边形填充算法，包括在附录文件中。在参考【5】中，作者详细介绍了一系列区域填充算法，可以查看相应网页。代码的下载地址为：https://github.com/twinklingstar20/twinklingstar_cn_region_polygon_fill_scanline/
1. 1. 区域的定义和填充
1.1 像素定义的区域（Pixel-Defined Region）
1.1.1 边界定义区域（boundary-defined）
定义某些像素是边界，边界包围着一块区域。填充所有在边界内的相连通的像素，主要分下面几个步骤：
- 从区域内部一个像素点开始
- 判断这个像素是否是一个边界像素点或者已经被填充了
- 如果都不是，就把它填充，然后开始设置邻居像素点。
用图片演示这个过程，如下面的幻灯片所示，代码片段如下所示：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void boundaryFill4 (int x, int y, int fill, int boundary){ int current; current = getPixel (x,y); if (current != boundary && current !=fill) { setColor(fill); setPixel(x,y); boundaryFill4 (x+1, y, fill, boundary); boundaryFill4 (x−1, y, fill, boundary); boundaryFill4(x, y+1, fill, boundary); bonddaryFill4(x, y−1, fill, boundary); }} |
1.1.2 内定义区域（interior-defined）
内定义区域的定义是：给定一个像素S，颜色是C，区域R指与S连通的且颜色都是C的像素集合（Region R is the set of all pixels having color C that are “connected” to a given pixel S）。
如果两个像素连通，则它们之间有一条“相邻（adjacent）”像素组成的连续路径，所以连通的概念就依赖“相邻”的定义。在图形学中，相邻通常有两种定义：
（1） 四相邻（4-Adjacent）:两个像素是四相邻的，则它们在彼此水平或者垂直相邻的位置上，如图1所示：
图1. 四相邻
（2） 八相邻（8-Adjacent）:两个像素是八相邻的，则它们在彼此水平、垂直或者是斜方向上相邻的位置，如图2所示：
图2. 八相邻
如果两个像素是四连通（4-connected），指它们之间有一条四相邻像素组成的连续路径；如果两个像素是八连通（8-connected），指它们之间有一条四相邻像素组成的连续路径。举个例子，如下图3所示，是由黑色、灰色和白色组成的像素图，给定一个像素点S，则由它定义的四连通区域共有20像素，由它定义的八连通区域共有28个像素。
图3 像素区域
这里介绍两种简单的填充算法：
（1） 一种称为洪水填充法。规定采用4连通的区域，下面用幻灯片演示了这个过程，下面的代码片段实现了该算法。由于没有使用到区域间的相关性，很多像素点可能会重复被填充。
- 从内部一个像素点开始，并用新的颜色替换它
- 填充四连通或者八连通区域，直到所有的内部点被替换了
|
1
2
3
4
5
6
7
8
9
10
11
12
|
void floodFill4 (int x, int y, int fill, int oldColor){ if (getPixel(x,y) == oldColor) { setColor(fill); setPixel(x,y); floodFill4 (x+1, y, fill, oldColor); floodFill4 (x−1, y, fill, oldColor); floodFill4(x, y+1, fill, oldColor); floodFill4(x, y−1, fill, oldColor); }} |
缺点是：1）大量的嵌套调用；2）很多像素点可能会被测试多次；3）难以清楚的掌控由于嵌套调用所占的内存大小；4）如果算法多次测试一个像素，会导致占用的内存扩大。
（2）利用像素间的相关性，可以提高算法的性能，并避免堆栈的溢出。每次填充在同一条扫描线上相邻的一排像素，同时把与它相邻的未填充的种子像素放在堆栈中，下面的幻灯片演示了这个过程。伪码如下所示：
|
1
2
3
4
5
6
7
8
9
|
Push address of seed pixel on the stack;while( stack not empty){ Pop the stack to provide the next seed; Fill the run defined by the seed; In the row above find interior runs reachable from this run; Push the addresses of the rightmost pixels of each such run; Do the same for the row below the current run;} |
1.2 符号定义的区域（Symbolically Defined Region）
这里简单介绍下符号定义的区域的分类，详细参见参考【4】，主要包括两类：
（1）用一系列的矩形方块表示的区域；
（2）通过一条表示一个区域边界的路径来界定一个区域:
1）用一个数学公式来定义边界，例如采用(x-122)^2+(y-36)^2=25来定义一个圆的区域
2）通过一系列的多边形顶点，像(x1,y1),(x2,y2),(x3,y3)…(xn,yn)来定义一个多边形区域
3）通过一系列相邻的像素来定义。
4）链码（chain code），这是一个很经典的方法，在参考【3】和【4】中都有简单的介绍，这里不详细介绍这块知识
5）其它
2. 多边形填充算法
2.1 算法思想
参考【5】，扫描线填充算法的基本思想是：每条水平扫描线与多边形的边产生一系列交点，交点之间形成一条一条的线段，该线段上的像素就是需要被填充的像素。将这些交点按照x坐标排序，将排序后的交点两两成对，作为线段的两个端点。水平扫描线从上到下（或从下到上）扫描由多条首尾相连的线段，使用要求的颜色填充该水平线段上的像素。多边形扫描完成后，颜色填充也就完成了。扫描线填充算法可以归纳为以下4个步骤：
（1） 求交，计算扫描线与多边形的交点；
（2） 交点排序，对第（1）步得到的交点按照x值从小到大进行排序；
（3） 颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进行颜色填充；
（4） 是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然后转第1步继续处理；
整个算法的关键是第1步，需要用尽量少的计算量求出交点，还要考虑交点是线段端点的特殊情况，最后，交点的计算最好是整数，便于光栅设备输出显示。对于每一条扫描线，如果每次都按照正常的线段与直线相交算法进行计算，则计算量大，而且效率低下，如图（4）所示：
图4. 扫描线算法
2.2 存在的问题
利用上述算法还存在几个问题，接下来分别讨论：
（1） 如果多个多边形相邻的话，它们可能会共享一条边，那么共享边可能会被绘制两次，图5和图6演示了该错误：
图5. 相邻的两个三角形共享边
图6. 左图是背景颜色与前景颜色混合的情况，右图是不绘制共享边的情况
对这个问题有一种很好的解决方案是：
原则1：每个多边形只拥有它左边的像素，即采用左闭右开的原则，如果边是水平的话，则只拥有底边。
图7. 共享边的解决方案
（2） 如图7所示，若采用Bresenham直线绘制算法，(参见文章，《布雷森汉姆直线算法》可能会出现一些像素超出边所在的范围：
原则2：在计算完扫描线与边的交点后，会形成一条条的首尾相连的线段，用xLeft表示左端点，xRight表示右端点，xLeft和xRight是实数，取大于等于xLeft的最小整数xNewLeft，取小于等于xRight的最大整数xNewRight，则绘制像素范围是[xNewLeft，xNewRight)，如果 xNewRight<xRight，则右端也封闭。
（3） 水平扫描线与端点发生相交的情况。如图8所示，穿过顶点H的扫描线，发生了两次相交（一次是与边GH，一次是与边HI），所以2.1描述的算法思想的第1步结束后，H点会存储两次，排完序后H两边的奇偶性会相同，因此会错误的将H右边的像素进行填充。（本图是从参考【4】中获取的，个人觉得该图解释这个问题，有点牵强。如果整个图左右翻转的话，解释这个问题就特别清楚了，算法思想的第1步结束后，该扫描线上共有三个交点：(H,H,右交点)，这样问题就明显了）。这里采用两条原则，可以很简单的解决这个问题：
图8. 填充多边形
原则3：忽略任何一条与水平边的相交计算；
原则4：如果交点是边的上端点，则把该端点忽略。
举个遵守该该原则的例子，如图9所示，得到每条边端点相交的数量：
图9. 一个多边形的端点相交的数量
2.3 数据结构设计
2.3.1活动边链表（Active-Edge List，AEL）
在计算相邻两条扫描线与一条边的相交时，可以利用它们之间的相关性。假设，一条边与的斜率是k，与扫描线y相交于x，则该边与扫描线y+1相交于x+1/k点的位置，利用这个特性可以减少运算量。为了方便进行该运算，有人提出了一种数据结构，称为活动边链表，链表的每个节点存储三个数据：（1）与当前水平扫描线的交点xint；（2）斜率m的倒数，1/m；（3）边的上端点的yhigh。举个例子来说该结构的存储方式，如图10所示，虚线代表了水平扫描线，在该水平扫描线上与多边形共有4个交点，则在AEL中会存储4个节点，4个结点按照xint从小到大排序。
图10. 活动边链表
2.3.2边表（Edge Table，ET）
边表存储的是边的信息，边表中每个节点的数据结构与AEL中每个节点的相同，同样存储了三个信息：（1）边下端点X坐标xbottom；（2）边斜率的倒数；（3）边上端点Y坐标yhigh。当AEL表进行更新时，边表这种数据结构提供了快速索引的功能。如图10中多边形的边信息，用边表表示，如图11所示，这里就记录了其中四条边的信息。首先用一个边节点的数组，一条边下端点的Y坐标值，表示该数组的索引。图10中，Y=20扫描线上，共有两条边（原则3，忽略水平边），所以把两条边的信息记录节点，该节点存储在数组索引号20的表项后面，注意：在我的实现中，要求这个链表中的节点也是按照xbottom从小到大的顺序排列的；例如扫描线39所示，不存在边的下端点在该扫描线上，则索引号39的表项后面为空。
图11. 边表
2.4 算法实现
如下面的代码片段所示，主要有如下几个步骤：
（1） 分配AEL的表头g_ptrAELHead和边表g_ptrEdgeTable[EDGE_TABLE_SIZE]的表头内存空间，由于现在显示器在垂直方向的分辨率一般不超过1024，所以这里不进行优化。
（2） 初始化边表
（3） 在当前扫描线上，在ET中是否存在表项，如果存在，则插入到AEL表中。
（4） 填充该扫描线
（5） 更新AEL。AEL中是否有边的y坐标值大于或者等于下一条扫描线（原则１：上边不进行绘制），由于AEL结点中保存有yhigh，这一步很容易判断，将相应的节点删除。
（6） 判断算法是否结束，否则的话重复(3)-(5)几个步骤。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
typedef struct _Edge{ double dbX; double dbDelta; int inMaxY; _Edge* ptrNext;}Edge;Edge* g_ptrEdgeTable[EDGE_TABLE_SIZE];Edge* g_ptrAELHead;void scanLineFill(Vector* ptrPolygon, int inNumPoly,DWORD inColor){ allocEdges(); initEdgeTable(ptrPolygon,inNumPoly); for(int y=g_inMinY ; y<g_inMaxY ; y++ ) { insertAEL(g_ptrAELHead,g_ptrEdgeTable[y]); fillAELScanLine(g_ptrAELHead,y,inColor); updateAEL(g_ptrAELHead,y+1); } deallocEdges();} |
2.5 算法结果演示
如图12所示，实现该算法，并用glut库实现了个简单的Demo，按’U’，’L’可以放大或者缩小图像，即放大缩小每个“像素”占据的像素大小。
图12. 算法演示
3. 参考
【1】http://www.cs.ucdavis.edu/~ma/ECS175_S00/Notes/0411_a.pdf
【2】http://www.cs.tufts.edu/~sarasu/courses/comp175-2009fa/pdf/comp175-04-region-filling.pdf
【3】冈萨雷斯《数字图像处理》
【4】F.S Hill, JR. 《Computer Graphics Using OpenGL, Second Edition》
