概述
在图像着色游戏中，基于边界的图像填充是常见需求。本文详细介绍 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);
context.obtainStyledAttributes(attrs, R.styleable.ColourImageView);
mBorderColor = ta.getColor(R.styleable.ColourImageView_border_color, -);
hasBorderColor = (mBorderColor != -);
ta.recycle();
}
{
.onMeasure(widthMeasureSpec, heightMeasureSpec);
getMeasuredWidth();
getMeasuredHeight();
setMeasuredDimension(viewWidth,
getDrawable().getIntrinsicHeight() * viewWidth / getDrawable().getIntrinsicWidth());
(BitmapDrawable) getDrawable();
drawable.getBitmap();
mBitmap = Bitmap.createScaledBitmap(bm, getMeasuredWidth(), getMeasuredHeight(), );
}
}
