28852人阅读
算法系列（37）
1.3扫描线种子填充算法&&&&&&& 1.1和1.2节介绍的两种种子填充算法的优点是非常简单，缺点是使用了递归算法，这不但需要大量栈空间来存储相邻的点，而且效率不高。为了减少算法中的递归调用，节省栈空间的使用，人们提出了很多改进算法，其中一种就是扫描线种子填充算法。扫描线种子填充算法不再采用递归的方式处理“4-联通”和“8-联通”的相邻点，而是通过沿水平扫描线填充像素段，一段一段地来处理“4-联通”和“8-联通”的相邻点。这样算法处理过程中就只需要将每个水平像素段的起始点位置压入一个特殊的栈，而不需要象递归算法那样将当前位置周围尚未处理的所有相邻点都压入堆栈，从而可以节省堆栈空间。应该说，扫描线填充算法只是一种避免递归，提高效率的思想，前面提到的注入填充算法和边界填充算法都可以改进成扫描线填充算法，下面介绍的就是结合了边界填充算法的扫描线种子填充算法。&&&&&&& 扫描线种子填充算法的基本过程如下：当给定种子点(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）步；&这个算法中最关键的是第（4）步，就是从当前扫描线的上一条扫描线和下一条扫描线中寻找新的种子点。这里比较难理解的一点就是为什么只是检查新扫描线上区间[xLeft, xRight]中的像素？如果新扫描线的实际范围比这个区间大（而且不连续）怎么处理？我查了很多计算机图形学的书籍和论文，好像都没有对此做过特殊说明，这使得很多人在学习这门课程时对此有挥之不去的疑惑。本着“毁人”不倦的思想，本文就罗嗦解释一下，希望能解除大家的疑惑。&&&&&&& 如果新扫描线上实际点的区间比当前扫描线的[xLeft, xRight]区间大，而且是连续的情况下，算法的第（3）步就处理了这种情况。如图（4）所示：图（4） 新扫描线区间增大且连续的情况假设当前处理的扫描线是黄色点所在的第7行，则经过第3步处理后可以得到一个区间[6,10]。然后第4步操作，从相邻的第6行和第8行两条扫描线的第6列开始向右搜索，确定红色的两个点分别是第6行和第8行的种子点，于是按照顺序将（6, 10）和（8, 10）两个种子点入栈。接下来的循环会处理（8, 10）这个种子点，根据算法第3步说明，会从（8, 10）开始向左和向右填充，由于中间没有边界点，因此填充会直到遇到边界为止，所以尽管第8行实际区域比第7行的区间[6,10]大，但是仍然得到了正确的填充。&&&&&&& 如果新扫描线上实际点的区间比当前扫描线的[xLeft, xRight]区间大，而且中间有边界点的情况，算法又是怎么处理呢？算法描述中虽然没有明确对这种情况的处理方法，但是第4步确定上、下相邻扫描线的种子点的方法，以及靠右取点的原则，实际上暗含了从相邻扫描线绕过障碍点的方法。下面以图（5）为例说明：图（5） 新扫描线区间增大且不连续的情况算法第3步处理完第5行后，确定了区间[7, 9]，相邻的第4行虽然实际范围比区间[7, 9]大，但是因为被（4, 6）这个边界点阻碍，使得在确定种子点（4, 9）后向左填充只能填充右边的第7列到第10列之间的区域，而左边的第3列到第5列之间的区域没有填充。虽然作为第5行的相邻行，第一次对第4行的扫描根据靠右原则只确定了（4, 9）一个种子点。但是对第3行处理完后，第4行的左边部分作为第3行下边的相邻行，再次得到扫描的机会。第3行的区间是[3, 9]，向左跨过了第6列这个障碍点，第2次扫描第4行的时候就从第3列开始，向右找，可以确定种子点（4, 5）。这样第4行就有了两个种子点，就可以被完整地填充了。&&&&&&& 由此可见，对于有障碍点的行，通过相邻边的关系，可以跨越障碍点，通过多次扫描得到完整的填充，算法已经隐含了对这种情况的处理。根据本节总结的四个步骤，扫描线种子填充算法的实现如下：263&void ScanLineSeedFill(int x, int y, int new_color, int boundary_color)264&{265&&&& std::stack&Point& stk;266&267&&&& stk.push(Point(x, y)); //第1步，种子点入站268&&&& while(!stk.empty()) 269&&&& {270&&&& &&& Point seed = stk.top(); //第2步，取当前种子点271&&&& &&& stk.pop();272&273&&&& &&& //第3步，向左右填充274&&&& &&& int count = FillLineRight(seed.x, seed.y, new_color, boundary_color);//向'cf?右'd3?填'cc?充'b3?275&&&& &&& int xRight = seed.x + count - 1;276&&&& &&& count = FillLineLeft(seed.x - 1, seed.y, new_color, boundary_color);//向'cf?左'd7?填'cc?充'b3?277&&&& &&& int xLeft = seed.x - count;278&279&&&& &&& //第4步，处理相邻两条扫描线280&&&& &&& SearchLineNewSeed(stk, xLeft, xRight, seed.y - 1, new_color, boundary_color); 281&&&& &&& SearchLineNewSeed(stk, xLeft, xRight, seed.y + 1, new_color, boundary_color); 282&&&& }283&}FillLineRight()和FillLineLeft()两个函数就是从种子点分别向右和向左填充颜色，直到遇到边界点，同时返回填充的点的个数。这两个函数返回填充点的个数是为了正确调整当前种子点所在的扫描线的区间[xLeft, xRight]。SearchLineNewSeed()函数完成算法第4步所描述的操作，就是在新扫描线上寻找种子点，并将种子点入栈，新扫描线的区间是xLeft和xRight参数确定的：234&void SearchLineNewSeed(std::stack&Point&& stk, int xLeft, int xRight, 235&&&& &&& &&& &&& &&& && int y, int new_color, int boundary_color)236&{237&&&& int xt = xLeft;238&&&& bool findNewSeed = false;239&240&&&& while(xt &= xRight)241&&&& {242&&&& &&& findNewSeed = false;243&&&& &&& while(IsPixelValid(xt, y, new_color, boundary_color) && (xt & xRight))244&&&& &&& {245&&&& &&& &&& findNewSeed = true;246&&&& &&& &&& xt++;247&&&& &&& }248&&&& &&& if(findNewSeed)249&&&& &&& {250&&&& &&& &&& if(IsPixelValid(xt, y, new_color, boundary_color) && (xt == xRight))251&&&& &&& &&& &&& stk.push(Point(xt, y));252&&&& &&& &&& else253&&&& &&& &&& &&& stk.push(Point(xt - 1, y));254&&&& &&& }255&256&&&& &&& /*向右跳过内部的无效点（处理区间右端有障碍点的情况）*/257&&&& &&& int xspan = SkipInvalidInLine(xt, y, xRight, new_color, boundary_color);258&&&& &&& xt += (xspan == 0) ? 1 : xspan;259&&&& &&& /*处理特殊情况,以退出while(x&=xright)循环*/260&&&& }261&}&最外层的while循环是为了保证区间[xLeft, xRight]右端被障碍点分隔成多段的情况能够得到正确处理，通过外层while循环，可以确保为每一段都找到一个种子点（对于障碍点在区间左端的情况，请参考图（5）所示实例的解释，是隐含在算法中完成的）。内层的while循环只是为了找到每一段最右端的一个可填充点作为种子点。SkipInvalidInLine()函数的作用就是跳过区间内的障碍点，确定下一个分隔段的开始位置。循环内的最后一行代码有点奇怪，其实只是用了一个小“诡计”，确保在遇到真正的边界点时循环能够正确退出。这不是一个值得称道的做法，实现此类软件控制有更好的方法，本文这样做的目的只是为了使代码简短一些，让读者把注意力集中在算法处理逻辑上，而不是冗杂难懂的循环控制条件上。&&&&&&&&算法的实现其实就在ScanLineSeedFill()和SearchLineNewSeed()两个函数中，神秘的扫描线种子填充算法也并不复杂，对吧？至此，种子填充算法的几种常见算法都已经介绍完毕，接下来将介绍两种适合矢量图形区域填充的填充算法，分别是扫描线算法和边标志填充算法，注意适合矢量图形的扫描线填充算法有时又被称为“有序边表法”，和扫描线种子填充算法是有区别的。&&下一篇：扫描线算法（有序边表法）&&&
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1289747次
积分：13353
积分：13353
排名：第734名
原创：104篇
译文：12篇
评论：1160条
阅读：60429
文章：31篇
阅读：712375
(2)(1)(1)(2)(1)(2)(1)(1)(1)(1)(1)(2)(1)(1)(2)(1)(1)(5)(2)(4)(1)(1)(5)(1)(1)(2)(3)(1)(1)(1)(1)(1)(3)(1)(1)(5)(1)(1)(1)(1)(3)(1)(1)(2)(1)(1)(2)(3)(1)(3)(2)(3)(8)(8)(1)(2)(2)(1)(5)实验2：多边形区域扫描线填充或种子填充_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
实验2：多边形区域扫描线填充或种子填充
上传于||文档简介
&&计算机图形学实验2：多边形区域扫描线填充或种子填充
阅读已结束，如果下载本文需要使用2下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩2页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢您的位置： &
一种新的扫描线种子填充算法
优质期刊推荐数据结构与算法分析（14）
&&&&&&&&& 平面区域填充算法是计算机图形学领域的一个很重要的算法，区域填充即给出一个区域的边界（也可以是没有边界，只是给出指定颜色），要求将边界范围内的所有象素单元都修改成指定的颜色（也可能是图案填充）。区域填充中最常用的是多边形填色，本文中我们就讨论几种多边形区域填充算法。
一、种子填充算法（Seed Filling）
&&&&&&& 如果要填充的区域是以图像元数据方式给出的，通常使用种子填充算法（Seed Filling）进行区域填充。种子填充算法需要给出图像数据的区域，以及区域内的一个点，这种算法比较适合人机交互方式进行的图像填充操作，不适合计算机自动处理和判断填色。根据对图像区域边界定义方式以及对点的颜色修改方式，种子填充又可细分为几类，比如注入填充算法（Flood Fill Algorithm）、边界填充算法（Boundary Fill Algorithm）以及为减少递归和压栈次数而改进的扫描线种子填充算法等等。
&&&&&&& 所有种子填充算法的核心其实就是一个递归算法，都是从指定的种子点开始，向各个方向上搜索，逐个像素进行处理，直到遇到边界，各种种子填充算法只是在处理颜色和边界的方式上有所不同。在开始介绍种子填充算法之前，首先也介绍两个概念，就是“4-联通算法”和“8-联通算法”。既然是搜索就涉及到搜索的方向问题，从区域内任意一点出发，如果只是通过上、下、左、右四个方向搜索到达区域内的任意像素，则用这种方法填充的区域就称为四连通域，这种填充方法就称为“4-联通算法”。如果从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下全部八个方向到达区域内的任意像素，则这种方法填充的区域就称为八连通域，这种填充方法就称为“8-联通算法”。如图1（a）所示，假设中心的蓝色点是当前处理的点，如果是“4-联通算法”，则只搜索处理周围蓝色标识的四个点，如果是“8-联通算法”则除了处理上、下、左、右四个蓝色标识的点，还搜索处理四个红色标识的点。两种搜索算法的填充效果分别如如图1（b）和图1（c）所示，假如都是从黄色点开始填充，则“4-联通算法”如图1（b）所示只搜索填充左下角的区域，而“8-联通算法”则如图1（c）所示，将左下角和右上角的区域都填充了。
图（1） “4-联通”和“8-联通”填充效果
&&&&&&& 并不能仅仅因为图1的填充效果就认为“8-联通算法”一定比“4-联通算法”好，应该根据应用环境和实际的需求选择联通搜索方式，在很多情况下，只有“4-联通算法”才能得到正确的结果。
1.1 注入填充算法（Flood Fill Algorithm）
&&&&&&& 注入填充算法不特别强调区域的边界，它只是从指定位置开始，将所有联通区域内某种指定颜色的点都替换成另一种颜色，从而实现填充效果。注入填充算法能够实现颜色替换之类的功能，这在图像处理软件中都得到了广泛的应用。注入填充算法的实现非常简单，核心就是递归和搜索，以下就是注入填充算法的一个实现：
164&void FloodSeedFill(int x,
int old_color, int new_color)
if(GetPixelColor(x, y)
== old_color)
168&&&& &&& SetPixelColor(x, y, new_color);
169&&&& &&&
& COUNT_OF(direction_8); i++)
170&&&& &&&
171&&&& &&& &&& FloodSeedFill(x
+ direction_8[i].x_offset,
172&&&& &&& &&& &&& &&& &&& & y
+ direction_8[i].y_offset, old_color, new_color);
173&&&& &&&
&for循环实现了向8个联通方向的递归搜索，秘密就在direction_8的定义：
15&typedef
struct tagDIRECTION
int x_offset;
int y_offset;
19&}DIRECTION;
79&DIRECTION direction_8[]
这个是搜索类算法中常用的技巧，无需做太多说明，其实只要将其替换成如下direction_4的定义，就可以将算法改成4个联通方向填充算法：
80&DIRECTION direction_4[]
图2就是应用本算法实现的“4-联通”和“8-联通”填充效果：
图（2） 注入填充算法实现
1.2 边界填充算法（Boundary Fill Algorithm）
&&&&&&& 边界填充算法与注入填充算法的本质其实是一样的，都是递归和搜索，区别只在于对边界的确认，也就是递归的结束条件不一样。注入填充算法没有边界的概念，只是对联通区域内指定的颜色进行替换，而边界填充算法恰恰强调边界的存在，只要是边界内的点无论是什么颜色，都替换成指定的颜色。边界填充算法在应用上也非常的广泛，画图软件中的“油漆桶”功能就是边界填充算法的例子。以下就是边界填充算法的一个实现：
177&void BoundarySeedFill(int x,
int new_color, int boundary_color)
int curColor = GetPixelColor(x, y);
if( (curColor
!= boundary_color)
181&&&& &&&
&& (curColor != new_color)
183&&&& &&& SetPixelColor(x, y, new_color);
184&&&& &&&
& COUNT_OF(direction_8); i++)
185&&&& &&&
186&&&& &&& &&& BoundarySeedFill(x
+ direction_8[i].x_offset,
187&&&& &&& &&& &&& &&& &&& &&&& y
+ direction_8[i].y_offset, new_color, boundary_color);
188&&&& &&&
关于direction_8的说明请参考上一节，图3就是应用本算法实现的“4-联通”和“8-联通”填充效果（其中颜色值是1的点就是指定的边界）：
图（3） 边界填充算法实现
&下一篇：扫描线种子填充算法&
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：23256次
排名：千里之外
转载：134篇
(13)(8)(24)(1)(2)(6)(8)(4)(17)(19)(5)(1)(9)(20)