Android 不规则封闭区域颜色填充算法实现与示例

缺点：虽然逻辑简单，但在大区域填充时，Java 虚拟机栈深度有限，容易抛出异常。此外，大量重复入栈出栈操作会降低性能。

迭代优化（使用 Stack）

为了避免递归深度问题，可以使用显式栈来模拟递归过程。

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));
        }
    }
}

缺点：虽然解决了栈溢出问题，但每个像素点仍需单独处理，对于大块同色区域，效率依然较低，因为需要逐个像素入栈出栈。

2. 扫描线填充法

为了提升效率，扫描线填充法利用了水平方向的连通性。它不需要逐像素判断，而是整行整段地处理。

算法思想：

1. 初始化一个空的栈用于存放种子点，将种子点 (x, y) 入栈。
2. 判断栈是否为空，如果为空则结束；否则取出栈顶元素作为当前扫描线的种子点 (x, y)。
3. 从种子点出发，沿当前扫描线向左、右两个方向填充，直到遇到边界。分别标记区段的左端点 xLeft 和右端点 xRight。
4. 检查与当前扫描线相邻的 y-1 和 y+1 两条扫描线在区间 [xLeft, xRight] 中的像素。如果在这些区间内发现了与种子颜色相同的像素段，则将这些段作为新的种子点压入栈中。
5. 返回步骤 2。

优势：该算法基本上是一行一行着色的，减少了大量的重复判断和栈操作，在大块需要着色区域的效率比单纯的种子填充法高很多。

三、编码实现

我们将通过自定义 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 像素数组可能会带来性能开销，特别是在高分辨率屏幕上。

1. 内存管理：getPixels 和 setPixels 会涉及内存拷贝。对于频繁操作的场景，建议考虑使用 RenderScript 或 OpenGL ES 进行 GPU 加速处理。
2. ANR 风险：填充算法运行在主线程。如果区域过大，可能导致界面卡顿。务必确保在子线程中执行填充逻辑，或使用 Handler 将结果回主线程更新 UI。
3. 透明度处理：注意 Color.TRANSPARENT 的处理逻辑，避免误触透明区域触发填充。
4. 边界条件：确保坐标检查逻辑严密，防止数组越界异常。

五、总结

本文详细介绍了 Android 平台上实现不规则封闭区域颜色填充的两种主要算法。通过对比发现，扫描线填充法在处理大面积同色区域时具有显著的性能优势。提供的完整代码示例展示了如何自定义 View、处理触摸事件以及操作像素数组。开发者可根据实际业务场景选择合适的算法，并注意主线程性能优化，以确保用户体验流畅。