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

平面区域填充算法是计算机图形学领域的一个很重要的算法,区域填充即给出一个区域的边界(也可以是没有边界,只是给出指定颜色),要求将边界范围内的所有象素单元都修改成指定的颜色(也可能是图案填充)。区域填充中最常用的是多边形填色,本文中我们就讨论几种多边形区域填充算法。

一、种子填充算法(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)

注入填充算法不特别强调区域的边界,它只是从指定位置开始,将所有联通区域内某种指定颜色的点都替换成另一种颜色,从而实现填充效果。注入填充算法能够实现颜色替换之类的功能,这在图像处理软件中都得到了广泛的应用。注入填充算法的实现非常简单,核心就是递归和搜索,以下就是注入填充算法的一个实现:

 void FloodSeedFill(int x, int y, int old_color, int new_color)
{
 if(GetPixelColor(x, y) == old_color)
 {
 SetPixelColor(x, y, new_color);
 for(int i = 0; i < COUNT_OF(direction_8); i++)
 {
 FloodSeedFill(x + direction_8[i].x_offset,
  y + direction_8[i].y_offset, old_color, new_color);
 }
 }
}

for循环实现了向8个联通方向的递归搜索,秘密就在direction_8的定义:

 typedef struct tagDIRECTION
 {
 int x_offset;
 int y_offset;
 }DIRECTION;

DIRECTION direction_8[] = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} };

这个是搜索类算法中常用的技巧,无需做太多说明,其实只要将其替换成如下direction_4的定义,就可以将算法改成4个联通方向填充算法:

80 DIRECTION direction_4[] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };

图2就是应用本算法实现的“4-联通”和“8-联通”填充效果:

图(2) 注入填充算法实现

1.2 边界填充算法(Boundary Fill Algorithm)

边界填充算法与注入填充算法的本质其实是一样的,都是递归和搜索,区别只在于对边界的确认,也就是递归的结束条件不一样。注入填充算法没有边界的概念,只是对联通区域内指定的颜色进行替换,而边界填充算法恰恰强调边界的存在,只要是边界内的点无论是什么颜色,都替换成指定的颜色。边界填充算法在应用上也非常的广泛,画图软件中的“油漆桶”功能就是边界填充算法的例子。以下就是边界填充算法的一个实现:

 void BoundarySeedFill(int x, int y, int new_color, int boundary_color)
{
 int curColor = GetPixelColor(x, y);
 if( (curColor != boundary_color)
 && (curColor != new_color) )
 {
 SetPixelColor(x, y, new_color);
 for(int i = 0; i < COUNT_OF(direction_8); i++)
 {
 BoundarySeedFill(x + direction_8[i].x_offset,
  y + direction_8[i].y_offset, new_color, boundary_color);
 }
 }
}

关于direction_8的说明请参考上一节,图3就是应用本算法实现的“4-联通”和“8-联通”填充效果(其中颜色值是1的点就是指定的边界):

图(3) 边界填充算法实现

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对我们的支持。

您可能感兴趣的文章:

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

相关推荐

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Android ListView填充数据的方法

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

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

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

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

    1.3扫描线种子填充算法 1.1和1.2节介绍的两种种子填充算法的优点是非常简单,缺点是使用了递归算法,这不但需要大量栈空间来存储相邻的点,而且效率不高.为了减少算法中的递归调用,节省栈空间的使用,人们提出了很多改进算法,其中一种就是扫描线种子填充算法.扫描线种子填充算法不再采用递归的方式处理"4-联通"和"8-联通"的相邻点,而是通过沿水平扫描线填充像素段,一段一段地来处理"4-联通"和"8-联通"的相邻点.这样算法处理过程

随机推荐