概述
在图像着色游戏中，基于边界的图像填充是常见需求。本文详细介绍 Android 中不规则封闭区域填充色彩的两种经典算法：种子填充法和扫描线填充法，并提供完整的代码实现。
图像的填充主要有两种经典算法：
- 种子填充法：理论上能够填充任意区域和图形，但存在大量的反复入栈和大规模递归，降低了填充效率，容易导致栈溢出。
- 扫描线填充法：通过一行一行着色的方式，在大块需要着色区域的效率比种子填充法更高。
原理分析
算法 1：种子填充法（四联通/八联通）
假设要将某个区域填充成红色，从用户点击点的像素开始，上下左右（八联通还有左上、左下、右上、右下）去判断颜色。如果四个方向上的颜色与当前点击点的像素一致，则改变颜色至目标色，然后继续上述过程。
这是一个递归的过程。虽然代码简单，但在移动设备上使用该方法容易引发 StackOverflowException 异常。
尝试使用 Stack 存储像素点以减少递归深度后，速度依然过慢，无法满足性能要求。
算法 2：扫描线填充法
算法思想如下：
- 初始化一个空的栈用于存放种子点，将种子点 (x, y) 入栈。
- 判断栈是否为空，如果栈为空则结束算法，否则取出栈顶元素作为当前扫描线的种子点 (x, y)，y 是当前的扫描线。
- 从种子点 (x, y) 出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为 xLeft 和 xRight。
- 分别检查与当前扫描线相邻的 y – 1 和 y + 1 两条扫描线在区间 [xLeft, xRight] 中的像素，从 xRight 开始向 xLeft 方向搜索，将符合条件的 A 作为种子点压入栈中，然后返回第（2）步。
该算法基本上是一行一行着色的，效率较高。
编码实现
我们代码中引入了一个边界颜色，如果设置的话，着色的边界参考为该边界颜色，否则会只要与种子颜色不一致为边界。
（一）构造方法与测量
public class ColourImageView extends ImageView {
private Bitmap mBitmap;
/**
* 边界的颜色
*/
private int mBorderColor = -1;
private boolean hasBorderColor = false;
private Stack<Point> mStacks = new Stack<>();
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);
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());
// 根据 drawable，去得到一个和 view 一样大小的 bitmap
BitmapDrawable drawable = (BitmapDrawable) getDrawable();
Bitmap bm = drawable.getBitmap();
mBitmap = Bitmap.createScaledBitmap(bm, getMeasuredWidth(), getMeasuredHeight(), false);
}
}
继承 ImageView，只需将图片设为 src 即可。重写测量的目的是为了获取一个和 View 一样大小的 Bitmap 便于操作。
（二）onTouchEvent
@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);
}
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, , w, , , w, h);
setImageDrawable( (bm));
}
重点就是通过 fillColor 去改变数组中的颜色。
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)
while (!mStacks.isEmpty()) {
Point seed = mStacks.pop();
// 步骤 3：从种子点 (x, 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] 中的像素
if (seed.y - 1 >= 0)
findSeedInNewLine(pixels, pixel, w, h, seed.y - 1, left, right);
if (seed.y + 1 < h)
findSeedInNewLine(pixels, pixel, w, h, seed.y + 1, left, 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，找到种子节点入栈
while (end >= begin) {
if (pixels[end] == pixel) {
if (!hasSeed) {
rx = end % w;
mStacks.push(new Point(rx, ry));
hasSeed = true;
}
} else {
hasSeed = false;
}
end--;
}
}
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;
(needFillPixel(pixels, pixel, index)) {
pixels[index] = newColor;
count++;
x++;
} {
;
}
}
count;
}
{
;
(x >= ) {
y * w + x;
(needFillPixel(pixels, pixel, index)) {
pixels[index] = newColor;
count++;
x--;
} {
;
}
}
count;
}
{
(hasBorderColor) {
pixels[index] != mBorderColor;
} {
pixels[index] == pixel;
}
}
{
();
Color.argb(, random.nextInt(), random.nextInt(), random.nextInt());
color;
}
布局文件
<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
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">
<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" />
</declare-styleable>
</resources>
