<强>一、概述
在上一篇的叙述中,我们通过图层的方式完成了图片颜色的填充(详情请戳:Android不规则图像填充颜色小游戏),不过在着色游戏中更多的还是基于边界的图像的填充。本篇博客将详细描述。
图像的填充有2种经典算法。
种子填充法理论上能够填充任意区域和图形,但是这种算法存在大量的反复入栈和大规模的递归,降低了填充效率。
注意:实际上图像填充的算法还是很多的,有兴趣可以去谷歌学术上去搜一搜。
好的,下面先看看今天的效果图:
好的,可以看到这样的颜色填充比上一篇的基于层的在素材的准备上要简单很多~ ~ ~
<强>二,原理分析
首先我们简述下原理,我们在点击的时候拿到点击点的颜“色”,然后按照我们选择的算法进行填色即可。
算法1:种子填充法,四联通/八联通
算法简介:假设要将某个区域填充成红色。
从用户点击点的像素开始,上下左右(八联通还有左上,左下,右上,右下)去判断颜色,如果四个方向上的颜色与当前点击点的像素一致,则改变颜色至目标色,然后继续上述这个过程。
好的,可以看到这是一个递归的过程,1个点到4个,4个到16个不断的去延伸。如果按照这种算法,你会写出类似这样的代码:
/* *
* @param像素像素数组
* @param w宽度
* @param h高度
* @param像素当前点的颜色
* @param newColor填充色
* @param我横坐标
* @param j纵坐标
*/私人空间fillColor01 (int[]像素,int w, int h, int像素,int newColor, int, int j)
{
int指数=j * w +我;
如果(像素(指数)!=像素| |我在w=| |我& lt;0 | | & lt;0 | | j祝辞=h)
返回;
像素(指数)=newColor;//上
fillColor01(像素,w h,像素,newColor, i, j - 1);//右
fillColor01(像素,w h,像素,newColor i + 1, j);//下
fillColor01(像素,w h,像素,newColor, i, j + 1);//左
fillColor01(像素,w h,像素,newColor, i - 1 j);
}
之前
代码很简单,但是如果你去运行,会发生StackOverflowException异常,这个异常主要是因为大量的递归造成的。虽然简单,但是在移动设备上使用该方法不行。
于是,我就想,这个方法不是递归深度过多么,那么我可以使用一个栈去存像素点,减少递归的深度和次数,于是我把代码改成如下的方式:
/* *
* @param像素像素数组
* @param w宽度
* @param h高度
* @param像素当前点的颜色
* @param newColor填充色
* @param我横坐标
* @param j纵坐标
*/私人空间fillColor (int[]像素,int w, int h, int像素,int newColor, int, int j)
{
mStacks。(新推点(i, j));
而(! mStacks.isEmpty ())
{
点种子=mStacks.pop ();
日志。e(“标签”,“种子=" +种子。x +”,种子=" + seed.y);
int指数=种子。y * w + seed.x;
像素(指数)=newColor;
如果种子。y比;0)
{
int顶级=指数- w;
如果(像素(顶级)==像素)
{
mStacks。(新推点(种子。x,种子。y - 1));
}
}
如果种子。y & lt;h - 1)
{
int=指数+ w;
如果[下]==(像素像素)
{
mStacks。(新推点(种子。x,种子。y + 1));
}
}
如果种子。x比;0)
{
int左=指数- 1;
如果(像素(左)==像素)
{
mStacks。(新推点(种子。x - 1, seed.y));
}
}
如果种子。x & lt;w - 1)
{
int右=指数+ 1;
如果[右]==(像素像素)
{
mStacks。(新推点(种子。x + 1, seed.y));
}
}
}
}
之前
方法的思想也比较简单,将当前像素点入栈,然后出栈着色,接下来分别判断四个方向的,如果符合条件也进行入栈(只要栈不为空持续运行)对吧,这个方法我也尝试跑了下,恩,这次不会报错了,但是速度特别的慢~ ~ ~ ~慢得我是不可接受的。(有兴趣可以尝试,记得如果ANR,点击等待)。
这样来看,第一种算法,我们是不考虑了,没有办法使用,主要原因是假设对于矩形同色区域,都是需要填充的,而算法一依然是各种入栈。于是考虑第二种算法
