一、概述
在上一篇的叙述中，我们通过图层的方式完成了图片颜色的填充（详情请戳：Android不规则图像填充颜色小游戏），不过在着色游戏中更多的还是基于边界的图像的填充。本篇博客将详细描述。
图像的填充有2种经典算法。
一种是种子填充法。
种子填充法理论上能够填充任意区域和图形,但是这种算法存在大量的反复入栈和大规模的递归,降低了填充效率。
另一种是扫描线填充法。
注意：实际上图像填充的算法还是很多的，有兴趣可以去Google学术上去搜一搜。
ok，下面先看看今天的效果图：
ok，可以看到这样的颜色填充比上一篇的基于层的在素材的准备上要easy 很多~~~
二、原理分析
首先我们简述下原理，我们在点击的时候拿到点击点的”颜色”，然后按照我们选择的算法进行填色即可。
算法1：种子填充法，四联通/八联通
算法简介：假设要将某个区域填充成红色。
从用户点击点的像素开始，上下左右（八联通还有左上，左下，右上，右下）去判断颜色，如果四个方向上的颜色与当前点击点的像素一致，则改变颜色至目标色。然后继续上述这个过程。
ok，可以看到这是一个递归的过程，1个点到4个，4个到16个不断的去延伸。如果按照这种算法，你会写出类似这样的代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
/** * @param pixels 像素数组 * @param w 宽度 * @param h 高度 * @param pixel 当前点的颜色 * @param newColor 填充色 * @param i 横坐标 * @param j 纵坐标 */ private void fillColor01(int[] pixels, int w, int h, int pixel, int newColor, int i, int j) { int index = j * w + i; if (pixels[index] != pixel || i >= w || i < 0 || j < 0 || j >= h) return; pixels[index] = newColor; //上 fillColor01(pixels, w, h, pixel, newColor, i, j - 1); //右 fillColor01(pixels, w, h, pixel, newColor, i + 1, j); //下 fillColor01(pixels, w, h, pixel, newColor, i, j + 1); //左 fillColor01(pixels, w, h, pixel, newColor, i - 1, j); } |
代码很简单，但是如果你去运行，会发生StackOverflowException异常，这个异常主要是因为大量的递归造成的。虽然简单，但是在移动设备上使用该方法不行。
于是，我就想，这个方法不是递归深度过多么，那么我可以使用一个Stack去存像素点，减少递归的深度和次数，于是我把代码改成如下的方式：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
/** * @param pixels 像素数组 * @param w 宽度 * @param h 高度 * @param pixel 当前点的颜色 * @param newColor 填充色 * @param i 横坐标 * @param j 纵坐标 */ private void fillColor(int[] pixels, int w, int h, int pixel, int newColor, int i, int j) { mStacks.push(new Point(i, j)); while (!mStacks.isEmpty()) { Point seed = mStacks.pop(); Log.e("TAG", "seed = " + seed.x + " , seed = " + seed.y); int index = seed.y * w + seed.x; pixels[index] = newColor; if (seed.y > 0) { int top = index - w; if (pixels[top] == pixel) { mStacks.push(new Point(seed.x, seed.y - 1)); } } if (seed.y < h - 1) { int bottom = index + w; if (pixels[bottom] == pixel) { mStacks.push(new Point(seed.x, seed.y + 1)); } } if (seed.x > 0) { int left = index - 1; if (pixels[left] == pixel) { mStacks.push(new Point(seed.x - 1, seed.y)); } } if (seed.x < w - 1) { int right = index + 1; if (pixels[right] == pixel) { mStacks.push(new Point(seed.x + 1, seed.y)); } } } } |
方法的思想也比较简单，将当前像素点入栈，然后出栈着色，接下来分别判断四个方向的，如果符合条件也进行入栈（只要栈不为空持续运行）。ok，这个方法我也尝试跑了下，恩，这次不会报错了，但是速度特别的慢~~~~慢得我是不可接受的。（有兴趣可以尝试，记得如果ANR，点击等待）。
这样来看，第一种算法，我们是不考虑了，没有办法使用，主要原因是假设对于矩形同色区域，都是需要填充的，而算法一依然是各种入栈。于是考虑第二种算法
扫描线填充法
算法思想[4]：
初始化一个空的栈用于存放种子点，将种子点(x, y)入栈；
判断栈是否为空，如果栈为空则结束算法，否则取出栈顶元素作为当前扫描线的种子点(x, y)，y是当前的扫描线；
从种子点(x, y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xLeft和xRight；
分别检查与当前扫描线相邻的y - 1和y + 1两条扫描线在区间[xLeft, xRight]中的像素，从xRight开始向xLeft方向搜索，假设扫描的区间为AAABAAC（A为种子点颜色），那么将B和C前面的A作为种子点压入栈中，然后返回第（2）步；
上述参考自参考文献[4]，做了些修改，文章[4]中描述算法，测试有一点问题，所以做了修改.
可以看到该算法，基本上是一行一行着色的，这样的话在大块需要着色区域的效率比算法一要高很多。
ok，关于算法的步骤大家目前觉得模糊，一会可以参照我们的代码。选定了算法以后，接下来就开始编码了。
三、编码实现
我们代码中引入了一个边界颜色，如果设置的话，着色的边界参考为该边界颜色，否则会只要与种子颜色不一致为边界。
（一）构造方法与测量
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
public class ColourImageView extends ImageView{ private Bitmap mBitmap; /** * 边界的颜色 */ private int mBorderColor = -1; private boolean hasBorderColor = false; private Stack<Point> mStacks = new Stack<Point>(); public ColourImageView(Context context, AttributeSet attrs) { super(context, attrs); TypedArray ta = context.obtainStyledAttributes(attrs, R.styleable.ColourImageView); mBorderColor = ta.getColor(R.styleable.ColourImageView_border_color, -1); hasBorderColor = (mBorderColor != -1); L.e("hasBorderColor = " + hasBorderColor + " , mBorderColor = " + mBorderColor); ta.recycle(); } @Override protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) { super.onMeasure(widthMeasureSpec, heightMeasureSpec); int viewWidth = getMeasuredWidth(); int viewHeight = getMeasuredHeight(); //以宽度为标准，等比例缩放view的高度 setMeasuredDimension(viewWidth, getDrawable().getIntrinsicHeight() * viewWidth / getDrawable().getIntrinsicWidth()); L.e("view's width = " + getMeasuredWidth() + " , view's height = " + getMeasuredHeight()); //根据drawable，去得到一个和view一样大小的bitmap BitmapDrawable drawable = (BitmapDrawable) getDrawable(); Bitmap bm = drawable.getBitmap(); mBitmap = Bitmap.createScaledBitmap(bm, getMeasuredWidth(), getMeasuredHeight(), false); } |
可以看到我们选择的是继承ImageView，这样只需要将图片设为src即可。
构造方法中获取我们的自定义边界颜色，当然可以不设置~~
重写测量的目的是为了获取一个和View一样大小的Bitmap便于我们操作。
接下来就是点击啦~
（二）onTouchEvent
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
@Override public boolean onTouchEvent(MotionEvent event) { final int x = (int) event.getX(); final int y = (int) event.getY(); if (event.getAction() == MotionEvent.ACTION_DOWN) { //填色 fillColorToSameArea(x, y); } return super.onTouchEvent(event); } /** * 根据x,y获得改点颜色，进行填充 * * @param x * @param y */ private void fillColorToSameArea(int x, int y) { Bitmap bm = mBitmap; int pixel = bm.getPixel(x, y); if (pixel == Color.TRANSPARENT || (hasBorderColor && mBorderColor == pixel)) { return; } int newColor = randomColor(); int w = bm.getWidth(); int h = bm.getHeight(); //拿到该bitmap的颜色数组 int[] pixels = new int[w * h]; bm.getPixels(pixels, 0, w, 0, 0, w, h); //填色 fillColor(pixels, w, h, pixel, newColor, x, y); //重新设置bitmap bm.setPixels(pixels, 0, w, 0, 0, w, h); setImageDrawable(new BitmapDrawable(bm)); } |
可以看到，我们在onTouchEvent中获取(x,y)，然后拿到改点坐标：
获得点击点颜色，获得整个bitmap的像素数组
改变这个数组中的颜色
然后重新设置给bitmap，重新设置给ImageView
重点就是通过fillColor去改变数组中的颜色
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
/** * @param pixels 像素数组 * @param w 宽度 * @param h 高度 * @param pixel 当前点的颜色 * @param newColor 填充色 * @param i 横坐标 * @param j 纵坐标 */ private void fillColor(int[] pixels, int w, int h, int pixel, int newColor, int i, int j) { //步骤1：将种子点(x, y)入栈； mStacks.push(new Point(i, j)); //步骤2：判断栈是否为空， // 如果栈为空则结束算法，否则取出栈顶元素作为当前扫描线的种子点(x, y)， // y是当前的扫描线； while (!mStacks.isEmpty()) { /** * 步骤3：从种子点(x, y)出发，沿当前扫描线向左、右两个方向填充， * 直到边界。分别标记区段的左、右端点坐标为xLeft和xRight； */ Point seed = mStacks.pop(); //L.e("seed = " + seed.x + " , seed = " + seed.y); int count = fillLineLeft(pixels, pixel, w, h, newColor, seed.x, seed.y); int left = seed.x - count + 1; count = fillLineRight(pixels, pixel, w, h, newColor, seed.x + 1, seed.y); int right = seed.x + count; /** * 步骤4： * 分别检查与当前扫描线相邻的y - 1和y + 1两条扫描线在区间[xLeft, xRight]中的像素， * 从xRight开始向xLeft方向搜索，假设扫描的区间为AAABAAC（A为种子点颜色）， * 那么将B和C前面的A作为种子点压入栈中，然后返回第（2）步； */ //从y-1找种子 if (seed.y - 1 >= 0) findSeedInNewLine(pixels, pixel, w, h, seed.y - 1, left, right); //从y+1找种子 if (seed.y + 1 < h) findSeedInNewLine(pixels, pixel, w, h, seed.y + 1, left, right); } } |
可以看到我已经很清楚的将该算法的四个步骤标识到该方法中。好了，最后就是一些依赖的细节上的方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
/*** 在新行找种子节点** @param pixels* @param pixel* @param w* @param h* @param i* @param left* @param right*/private void findSeedInNewLine(int[] pixels, int pixel, int w, int h, int i, int left, int right){/*** 获得该行的开始索引*/int begin = i * w + left;/*** 获得该行的结束索引*/int end = i * w + right;boolean hasSeed = false;int rx = -1, ry = -1;ry = i;/*** 从end到begin，找到种子节点入栈（AAABAAAB，则B前的A为种子节点）*/while (end >= begin){if (pixels[end] == pixel){if (!hasSeed){rx = end % w;mStacks.push(new Point(rx, ry));hasSeed = true;}} else{hasSeed = false;}end--;}}/*** 往右填色，返回填充的个数** @return*/private int fillLineRight(int[] pixels, int pixel, int w, int h, int newColor, int x, int y){int count = 0;while (x < w){//拿到索引int index = y * w + x;if (needFillPixel(pixels, pixel, index)){pixels[index] = newColor;count++;x++;} else{break;}}return count;}/*** 往左填色，返回填色的数量值** @return*/private int fillLineLeft(int[] pixels, int pixel, int w, int h, int newColor, int x, int y){int count = 0;while (x >= 0){//计算出索引int index = y * w + x;if (needFillPixel(pixels, pixel, index)){pixels[index] = newColor;count++;x--;} else{break;}}return count;}private boolean needFillPixel(int[] pixels, int pixel, int index){if (hasBorderColor){return pixels[index] != mBorderColor;} else{return pixels[index] == pixel;}}/*** 返回一个随机颜色** @return*/private int randomColor(){Random random = new Random();int color = Color.argb(255, random.nextInt(256), random.nextInt(256), random.nextInt(256));return color;} |
ok，到此，代码就介绍完毕了~~~
最后贴下布局文件~~
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android" xmlns:tools="http://schemas.android.com/tools" xmlns:zhy="http://schemas.android.com/apk/res-auto" android:layout_width="match_parent" android:layout_height="match_parent" android:paddingLeft="@dimen/activity_horizontal_margin" android:paddingRight="@dimen/activity_horizontal_margin" android:paddingTop="@dimen/activity_vertical_margin" android:paddingBottom="@dimen/activity_vertical_margin" tools:context=".MainActivity"> <com.zhy.colour_app_01.ColourImageView zhy:border_color="#FF000000" android:src="@drawable/image_007" android:background="#33ff0000" android:layout_width="match_parent" android:layout_centerInParent="true" android:layout_height="match_parent"/></RelativeLayout><?xml version="1.0" encoding="utf-8"?><resources> <declare-styleable name="ColourImageView"> <attr name="border_color" format="color|reference"></attr> </declare-styleable></resources> |
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对服务器之家的支持。
原文链接：https://blog.csdn.net/lmj623565791/article/details/45954255
