Javajava算法
Android 不规则封闭区域颜色填充算法实现与示例
Android 不规则封闭区域颜色填充主要涉及种子填充法和扫描线填充法。种子填充法通过递归或栈遍历像素，易导致栈溢出；扫描线填充法按行扫描效率更高。对比两种算法原理，提供基于 Java 的完整实现代码，包括自定义 View 构建、触摸事件处理及像素数组操作，帮助开发者理解图像着色算法在移动端的应用。同时补充了性能优化建议和布局配置细节，确保代码可直接集成使用。
Android 不规则封闭区域颜色填充主要涉及种子填充法和扫描线填充法。种子填充法通过递归或栈遍历像素，易导致栈溢出；扫描线填充法按行扫描效率更高。对比两种算法原理，提供基于 Java 的完整实现代码，包括自定义 View 构建、触摸事件处理及像素数组操作，帮助开发者理解图像着色算法在移动端的应用。同时补充了性能优化建议和布局配置细节，确保代码可直接集成使用。
在移动应用开发中，图像着色（Flood Fill）是常见的交互需求，例如填色游戏或图片编辑工具。图像填充的核心在于如何高效地识别并修改特定区域内的像素颜色。
图像填充主要有两种经典算法：
虽然存在多种变体算法，但在移动端资源受限的环境下，选择效率更高的算法至关重要。本文将详细对比这两种算法的原理，并提供基于 Java 的完整 Android 实现代码。
算法简介：假设要将某个区域填充成红色。从用户点击点的像素开始，检查上下左右（八联通还包括对角线）四个方向的像素。如果相邻像素的颜色与当前点击点的像素一致，则将其改变为目标色，并继续对该新点进行同样的判断。
这是一个典型的递归过程。一个点扩展到四个点，这四个点再各自扩展，形成树状结构。如果区域较大，递归深度会迅速增加，极易导致栈溢出（StackOverflowException）。
/**
* @param pixels 像素数组
* @param w 宽度
* @param h 高度
* @param pixel 当前点的颜色
* @param newColor 填充色
* @param i 横坐标
* @param j 纵坐标
*/
private void fillColorRecursive(int[] pixels, int w, int h, int pixel, int newColor, int i, int j) {
int index = j * w + i;
// 边界检查及颜色匹配检查
if (index < 0 || index >= pixels.length ||
i < 0 || i >= w || j < 0 || j >= h ||
pixels[index] != pixel) {
return;
}
pixels[index] = newColor;
// 上
fillColorRecursive(pixels, w, h, pixel, newColor, i, j - 1);
// 右
fillColorRecursive(pixels, w, h, pixel, newColor, i + 1, j);
// 下
fillColorRecursive(pixels, w, h, pixel, newColor, i, j + 1);
// 左
fillColorRecursive(pixels, w, h, pixel, newColor, i - 1, j);
}
缺点：虽然逻辑简单，但在大区域填充时，Java 虚拟机栈深度有限，容易抛出异常。此外，大量重复入栈出栈操作会降低性能。
为了避免递归深度问题，可以使用显式栈来模拟递归过程。
private void fillColorIterative(int[] pixels, int w, int h, int pixel, int newColor, int i, int j) {
Stack<Point> mStacks = new Stack<>();
mStacks.push(new Point(i, j));
while (!mStacks.isEmpty()) {
Point seed = mStacks.pop();
int index = seed.y * w + seed.x;
pixels[index] = newColor;
// 检查四个方向并压栈
if (seed.y > 0 && pixels[index - w] == pixel) {
mStacks.push(new Point(seed.x, seed.y - 1));
}
if (seed.y < h - 1 && pixels[index + w] == pixel) {
mStacks.push(new Point(seed.x, seed.y + 1));
}
if (seed.x > 0 && pixels[index - 1] == pixel) {
mStacks.push(new Point(seed.x - 1, seed.y));
}
if (seed.x < w - 1 && pixels[index + 1] == pixel) {
mStacks.push(new Point(seed.x + 1, seed.y));
}
}
}
缺点：虽然解决了栈溢出问题，但每个像素点仍需单独处理，对于大块同色区域，效率依然较低，因为需要逐个像素入栈出栈。
为了提升效率，扫描线填充法利用了水平方向的连通性。它不需要逐像素判断，而是整行整段地处理。
算法思想：
xLeft 和右端点 xRight。y-1 和 y+1 两条扫描线在区间 [xLeft, xRight] 中的像素。如果在这些区间内发现了与种子颜色相同的像素段，则将这些段作为新的种子点压入栈中。优势：该算法基本上是一行一行着色的，减少了大量的重复判断和栈操作，在大块需要着色区域的效率比单纯的种子填充法高很多。
我们将通过自定义 ImageView 来实现这一功能。代码中引入了一个可选的边界颜色参数，如果设置的话，着色的边界参考为该边界颜色，否则只要与种子颜色不一致即为边界。
继承 ImageView 可以方便地设置图片源。重写 onMeasure 方法是为了获取一个与 View 尺寸一致的 Bitmap，便于后续操作。
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();
if (drawable != null) {
Bitmap bm = drawable.getBitmap();
mBitmap = Bitmap.createScaledBitmap(bm, getMeasuredWidth(), getMeasuredHeight(), false);
}
}
}
在 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) {
if (mBitmap == null) return;
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));
}
这是扫描线填充法的具体实现，包含寻找种子点和水平填充的逻辑。
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));
while (!mStacks.isEmpty()) {
Point seed = mStacks.pop();
// 步骤 3：从种子点出发，沿当前扫描线向左、右两个方向填充
int countLeft = fillLineLeft(pixels, pixel, w, h, newColor, seed.x, seed.y);
int left = seed.x - countLeft + 1;
int countRight = fillLineRight(pixels, pixel, w, h, newColor, seed.x + 1, seed.y);
int right = seed.x + countRight;
// 步骤 4：检查相邻行的种子点
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;
int 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;
if (needFillPixel(pixels, pixel, index)) {
pixels[index] = newColor;
count++;
x++;
} else {
break;
}
}
return count;
}
/**
* 往左填色，返回填色的数量值
*/
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;
}
}
private int randomColor() {
Random random = new Random();
return Color.argb(255, random.nextInt(256), random.nextInt(256), random.nextInt(256));
}
在布局中使用自定义 View 并设置边界颜色属性。
<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.example.colour_app_01.ColourImageView
android:id="@+id/imageView"
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>
对应的 attrs.xml 定义：
<?xml version="1.0" encoding="utf-8"?>
<resources>
<declare-styleable name="ColourImageView">
<attr name="border_color" format="color|reference" />
</declare-styleable>
</resources>
在实际项目中，直接操作 Bitmap 像素数组可能会带来性能开销，特别是在高分辨率屏幕上。
getPixels 和 setPixels 会涉及内存拷贝。对于频繁操作的场景，建议考虑使用 RenderScript 或 OpenGL ES 进行 GPU 加速处理。Color.TRANSPARENT 的处理逻辑，避免误触透明区域触发填充。本文详细介绍了 Android 平台上实现不规则封闭区域颜色填充的两种主要算法。通过对比发现，扫描线填充法在处理大面积同色区域时具有显著的性能优势。提供的完整代码示例展示了如何自定义 View、处理触摸事件以及操作像素数组。开发者可根据实际业务场景选择合适的算法，并注意主线程性能优化，以确保用户体验流畅。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online