Android多边形区域扫描线种子填充算法的示例

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行就有了两个种子点,就可以被完整地填充了。

由此可见,对于有障碍点的行,通过相邻边的关系,可以跨越障碍点,通过多次扫描得到完整的填充,算法已经隐含了对这种情况的处理。根据本节总结的四个步骤,扫描线种子填充算法的实现如下:

void SearchLineNewSeed(std::stack<Point>& stk, int xLeft, int xRight,
 int y, int new_color, int boundary_color)
 {
 int xt = xLeft;
 bool findNewSeed = false;
 while(xt <= xRight)
 {
 findNewSeed = false;

 while(IsPixelValid(xt, y, new_color, boundary_color) && (xt < xRight))
 {
 findNewSeed = true;
 xt++;
 }
 if(findNewSeed)
 {
 if(IsPixelValid(xt, y, new_color, boundary_color) && (xt == xRight))

 stk.push(Point(xt, y));
 else
 stk.push(Point(xt - 1, y));
 }

 /*向右跳过内部的无效点(处理区间右端有障碍点的情况)*/
 int xspan = SkipInvalidInLine(xt, y, xRight, new_color, boundary_color);
 xt += (xspan == 0) ? 1 : xspan;
 /*处理特殊情况,以退出while(x<=xright)循环*/
 }
}

FillLineRight()和FillLineLeft()两个函数就是从种子点分别向右和向左填充颜色,直到遇到边界点,同时返回填充的点的个数。这两个函数返回填充点的个数是为了正确调整当前种子点所在的扫描线的区间[xLeft, xRight]。

SearchLineNewSeed()函数完成算法第4步所描述的操作,就是在新扫描线上寻找种子点,并将种子点入栈,新扫描线的区间是xLeft和xRight参数确定的:

void SearchLineNewSeed(std::stack<Point>& stk, int xLeft, int xRight,
 int y, int new_color, int boundary_color)
 {
 int xt = xLeft;
 bool findNewSeed = false;
 while(xt <= xRight)
 {
 findNewSeed = false;

 while(IsPixelValid(xt, y, new_color, boundary_color) && (xt < xRight))
 {
 findNewSeed = true;
 xt++;
 }
 if(findNewSeed)
 {
 if(IsPixelValid(xt, y, new_color, boundary_color) && (xt == xRight))

 stk.push(Point(xt, y));
 else
 stk.push(Point(xt - 1, y));
 }

 /*向右跳过内部的无效点(处理区间右端有障碍点的情况)*/
 int xspan = SkipInvalidInLine(xt, y, xRight, new_color, boundary_color);
 xt += (xspan == 0) ? 1 : xspan;
 /*处理特殊情况,以退出while(x<=xright)循环*/
 }
}

最外层的while循环是为了保证区间[xLeft, xRight]右端被障碍点分隔成多段的情况能够得到正确处理,通过外层while循环,可以确保为每一段都找到一个种子点(对于障碍点在区间左端的情况,请参考图(5)所示实例的解释,是隐含在算法中完成的)。内层的while循环只是为了找到每一段最右端的一个可填充点作为种子点。SkipInvalidInLine()函数的作用就是跳过区间内的障碍点,确定下一个分隔段的开始位置。循环内的最后一行代码有点奇怪,其实只是用了一个小“诡计”,确保在遇到真正的边界点时循环能够正确退出。这不是一个值得称道的做法,实现此类软件控制有更好的方法,本文这样做的目的只是为了使代码简短一些,让读者把注意力集中在算法处理逻辑上,而不是冗杂难懂的循环控制条件上。

算法的实现其实就在ScanLineSeedFill()和SearchLineNewSeed()两个函数中,神秘的扫描线种子填充算法也并不复杂,对吧?至此,种子填充算法的几种常见算法都已经介绍完毕,接下来将介绍两种适合矢量图形区域填充的填充算法,分别是扫描线算法和边标志填充算法,注意适合矢量图形的扫描线填充算法有时又被称为“有序边表法”,和扫描线种子填充算法是有区别的。

您可能感兴趣的文章:

  • Android Studio使用小技巧:布局预览时填充数据
  • 基于Android中的 AutoCompleteTextView实现自动填充
  • Android矢量图之VectorDrawable类自由填充色彩
  • Android ListView填充数据的方法
  • Android ScrollView无法填充满屏幕的解决办法
  • Android图片等比例缩放和填充屏幕效果
  • Android不规则图像填充颜色小游戏
  • Android图像处理之泛洪填充算法
  • Android多边形区域递归种子填充算法的示例代码
  • Android不规则封闭区域填充色彩的实例代码
(0)

相关推荐

  • Android多边形区域递归种子填充算法的示例代码

    平面区域填充算法是计算机图形学领域的一个很重要的算法,区域填充即给出一个区域的边界(也可以是没有边界,只是给出指定颜色),要求将边界范围内的所有象素单元都修改成指定的颜色(也可能是图案填充).区域填充中最常用的是多边形填色,本文中我们就讨论几种多边形区域填充算法. 一.种子填充算法(Seed Filling) 如果要填充的区域是以图像元数据方式给出的,通常使用种子填充算法(Seed Filling)进行区域填充.种子填充算法需要给出图像数据的区域,以及区域内的一个点,这种算法比较适合人机交互方式

  • Android图像处理之泛洪填充算法

    泛洪填充算法(Flood Fill Algorithm) 泛洪填充算法又称洪水填充算法是在很多图形绘制软件中常用的填充算法,最熟悉不过就是windows paint的油漆桶功能.算法的原理很简单,就是从一个点开始附近像素点,填充成新的颜色,直到封闭区域内的所有像素点都被填充新颜色为止.泛红填充实现最常见有四邻域像素填充法,八邻域像素填充法,基于扫描线的像素填充方法.根据实现又可以分为递归与非递归(基于栈). 在介绍算法的三种实现方式之前,首先来看一下测试该算法的UI实现.基本思路是选择一张要填充

  • Android图片等比例缩放和填充屏幕效果

    本文实例为大家分享了Android图片等比例缩放和填充屏幕的具体代码,供大家参考,具体内容如下 第一种方法:在ImageView的t同事设置两个属性 android:adjustViewBounds="true" android:scaleType="fitXY 第二中方法:用IamgeView的 android:scaleType  设置属性的时候  填充屏幕出现的各种问题 /** * 将图片等比例缩放 setAdjustViewBounds setMaxWidth set

  • Android ScrollView无法填充满屏幕的解决办法

    Android ScrollView无法填充满屏幕的解决办法 ScrollView滚动视图是指当拥有很多内容.屏幕显示不完时.需要通过滚动跳来显示的视图.Scrollview的一般用法如下 以下代码在Scrollview里面放了一个RelativeLayout.并且是设置为Android:layout_height="match_parent"填充全屏的和RelativeLayout里面放置了一个TextView背景设为了一张图片.按照代码理解.图片应该是居于屏幕的最下方的 <S

  • Android Studio使用小技巧:布局预览时填充数据

    我们都知道Android Studio用起来很棒,其中布局预览更棒.我们在调UI的时候基本是需要实时预览来看效果的,在Android Studio中只需要切换到Design就可以看到,而且我们需要在布局上填充数据预览效果更好,比如我们在TextView中设定text属性来看下字体大小与布局是否正确,但是呢正式环境我们又需要移除这些额外的数据,不然看着很不舒服,这个时候就用到了本篇博客介绍的一个技巧. 废话不多说,直接上图: 上述示例中只需要在xml布局文件中添加tools命名空间的text属性就

  • Android矢量图之VectorDrawable类自由填充色彩

    2014年6月26日的I/O 2014开发者大会上谷歌正式推出了Android L,它带来了全新的设计语言Material Design,新的API也提供了这个类VectorDrawable .也就是android支持SVG类型的资源也就是矢量图.想到矢量图,自然就会想到位图,何为矢量图,何为位图?先来说说位图吧,我们经常用的png,jpg就是位图了,他是由一个单元一个单元的像素组成的.当小icon遇到大屏幕手机的时候,icon如果被撑开那就是马赛克一样啦.这可不是我们想要的.而矢量图正式和它相

  • Android ListView填充数据的方法

    Android ListView填充数据的方法 因为多人开发,为了是自己开发的模块方便融合到主框架中,同时也为了减小apk的大小,要求尽可能少的使用xml的布局文件,开发中需要在ListView中显示数据,网上查到的几乎所有的示例,都是通过xml文件来为ListView的Item提供布局样式,甚是不方便. 能不能将自己通过代码创建的布局(如View,LinearLayout)等动态的布局到ListView呢?当然可以. 为了给ListView提供数据,我们需要为其设置一个适配,我们可以从Base

  • 基于Android中的 AutoCompleteTextView实现自动填充

    现在我们上网会用百度或者谷歌搜索信息,当我们在输入框里输入一两个字后,就会自动提示我们想要的信息,这种效果在Android 是通过Android 的AutoCompleteTextView Widget 搭配ArrayAdapter 设计同类似Google 搜索提示的效果. 先在Layout 当中布局一个AutoCompleteTextView Widget ,然后通过预先设置好的字符串数组,将此字符串数组放入ArrayAdapter ,最后利用AutoCompleteTextView.setA

  • Android不规则封闭区域填充色彩的实例代码

    一.概述 在上一篇的叙述中,我们通过图层的方式完成了图片颜色的填充(详情请戳:Android不规则图像填充颜色小游戏),不过在着色游戏中更多的还是基于边界的图像的填充.本篇博客将详细描述. 图像的填充有2种经典算法. 一种是种子填充法. 种子填充法理论上能够填充任意区域和图形,但是这种算法存在大量的反复入栈和大规模的递归,降低了填充效率. 另一种是扫描线填充法. 注意:实际上图像填充的算法还是很多的,有兴趣可以去Google学术上去搜一搜. ok,下面先看看今天的效果图: ok,可以看到这样的颜

  • Android不规则图像填充颜色小游戏

    一.概述 近期群里偶然看到一哥们在群里聊不规则图像填充什么四联通.八联通什么的,就本身好学务实的态度去查阅了相关资料.对于这类着色的资料,最好的就是去搜索些相关app,根据我的观察呢,不规则图像填充在着色游戏里面应用居多,不过大致可以分为两种: 基于层的的填充 基于边界的填充 那么针对上述两种,我们会通过两篇博文来讲解,本篇就是叙述基于层的填充方式,那么什么基于层的填充方式呢?其实就是一张图实际上是由多个层组成的,每个层显示部分图像(无图像部分为透明),多层叠加后形成一张完整的图案,图层间是叠加

随机推荐