洪水填充算法_区域填充算法和多边形填充的扫描线算法-白红宇

洪水填充算法_区域填充算法和多边形填充的扫描线算法

阅读量：6361 次

发布时间：2019-06-23

本文共 5377 字，大约阅读时间需要 17 分钟。

本文主要介绍几种区域填充算法，重点解释多边形的扫描线填充算法，最后实现了多边形填充算法，包括在附录文件中。在参考【5】中，作者详细介绍了一系列区域填充算法，可以查看相应网页。代码的下载地址为：https://github.com/twinklingstar20/twinklingstar_cn_region_polygon_fill_scanline/

1. 1.区域的定义和填充

1.1像素定义的区域(Pixel-Defined Region)

1.1.1 边界定义区域(boundary-defined)

定义某些像素是边界，边界包围着一块区域。填充所有在边界内的相连通的像素，主要分下面几个步骤：

从区域内部一个像素点开始

判断这个像素是否是一个边界像素点或者已经被填充了

如果都不是，就把它填充，然后开始设置邻居像素点。

用图片演示这个过程，如下面的幻灯片所示，代码片段如下所示：

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连通的区域，下面用幻灯片演示了这个过程，下面的代码片段实现了该算法。由于没有使用到区域间的相关性，很多像素点可能会重复被填充。

从内部一个像素点开始，并用新的颜色替换它

填充四连通或者八连通区域，直到所有的内部点被替换了

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)利用像素间的相关性，可以提高算法的性能，并避免堆栈的溢出。每次填充在同一条扫描线上相邻的一排像素，同时把与它相邻的未填充的种子像素放在堆栈中，下面的幻灯片演示了这个过程。伪码如下所示：

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

(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)几个步骤。

typedef struct _Edge

{

doubledbX;