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多边形区域扫描线种子填充算法的示例
时间: 2018-05-06

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多边形区域扫描线种子填充算法的示例

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

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不规则封闭区域填充色彩的实例代码

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

Android ListView填充数据的方法

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

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

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

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

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

VB.NET中使用种子填充算法实现给图片着色的例子

某人最近在使用C#写一个类似Windows的画图工具,在填色的部分卡住了.劳资要他使用种子填充算法着色(不要调用Windows提供的API,否则还锻炼个毛线),现在我把这个功能实现了,程序的效率很高.现在在这里大概写一下实现方法. 程序是用VB.NET写的,C#写法类似(而且还不需要使用Marshal类访问非托管资源,更加方便).程序的运行结果如下: 种子填充算法说白了就是宽度优先搜索算法(BFS),如果你不知道这是什么东西,那说明你数据结构根本就没有学,请自行补充相应的知识. 第一步:实现"铅

Opencv学习教程之漫水填充算法实例详解

前言 基本思想是自动选中了和种子点相连的区域,接着将该区域替换成指定的颜色,经常用来标记或者分离图像的一部分进行处理或分析.漫水填充也可以用来从输入图像获取掩码区域,掩码会加速处理过程,或者只处理掩码指定的像素点.其中掩膜Mask用于进一步控制那些区域将被填充颜色(比如说当对同一图像进行多次填充时). int floodFill(inputoutputArray,inputoutputMask,seedPoint,Scalar newVal,Rect* rect=0,Scalar loDiff=

Android数据加密之Base64编码算法的简单实现

前面学习总结了平时开发中遇见的各种数据加密方式,最终都会对加密后的二进制数据进行Base64编码,起到一种二次加密的效果,其实呢Base64从严格意义上来说的话不是一种加密算法,而是一种编码算法,为何要使用Base64编码呢?它解决了什么问题?这也是本文探讨的东西? 什么Base64算法? Base64是网络上最常见的用于传输8Bit字节代码的编码方式之一,Base64并不是安全领域的加密算法,其实Base64只能算是一个编码算法,对数据内容进行编码来适合传输.标准Base64编码解码无需额外信

Python实现螺旋矩阵的填充算法示例

本文实例讲述了Python实现螺旋矩阵的填充算法.分享给大家供大家参考,具体如下: afanty的分析: 关于矩阵(二维数组)填充问题自己动手推推,分析下两个下表的移动规律就很容易咯. 对于螺旋矩阵,不管它是什么鬼,反正就是依次向右.向下.向右.向上移动. 向右移动:横坐标不变,纵坐标加1 向下移动:纵坐标不变,横坐标加1 向右移动:横坐标不变,纵坐标减1 向上移动:纵坐标不变,横坐标减1 代码实现: #coding=utf-8 import numpy ''''' Author: afanty

利用JS实现一个同Excel表现的智能填充算法

前言 本文介绍了关于利用JS实现同Excel表现的智能填充算法的相关内容,分享出供大家参考学习,下面话不多说了,来一起看看详细的介绍吧 在使用Excel的时候,发现它的"智能填充"功能非常有趣,能够智能地分析我当前的内容,然后准确预测出我期望得到的值.排除了AI的加成,发现这个功能其实也可以通过数学理论和简单代码来实现.经过一番折腾,终于用JS实现了大致的功能,然后我把它名为smart-predictor. 项目地址:https://github.com/jrainlau/s...(本

python扫描线填充算法详解

本文实例为大家分享了python扫描线填充算法,供大家参考,具体内容如下 介绍 1.用水平扫描线从上到下扫描由点线段构成的多段构成的多边形. 2.每根扫描线与多边形各边产生一系列交点.将这些交点按照x坐标进行分类,将分类后的交点成对取出,作为两个端点,以所填的色彩画水平直线. 3.多边形被扫描完毕后,填色也就完成. 数据结构 活性边表: 新边表: 代码(使用数组) import numpy as np from PIL import Image from PIL import ImageDraw

OpenGL扫描线填充算法详解

本文实例为大家分享了OpenGL扫描线填充算法,供大家参考,具体内容如下 说明 把最近一系列的图形学经典算法实现了一下.课业繁忙,关于该系列的推导随后再写.但是在注释里已经有较为充分的分析. 分情况讨论 注意对于横线需要特别讨论,但是对于垂直线却不必特别讨论.想一想为什么? 代码 #include <iostream> #include <GLUT/GLUT.h> #include <map> #include <vector> #include <l