java - 算法，洪水填充(深度优先搜索)

Question

我正在使用 Java。
我正在开发一个绘画程序，“Paint Can”工具使用的是Flood Fill算法，但它太昂贵了。

这是代码:

private int[] dx = { -1, 0, 1, 0 };
private int[] dy = { 0, 1, 0, -1 };

public void floodFill(int x, int y, Color target_color, Color replacement_color) {
    Stack<Integer[]> stack = new Stack<Integer[]>();
    if (imageBuffer.getRGB(x, y) == replacement_color.getRGB())
         return;
    stack.push(new Integer[] { x, y });
    while (!stack.isEmpty()) {
        Integer[] aux = stack.peek();
        imageBuffer.setRGB(aux[0], aux[1], replacement_color.getRGB());
        stack.pop();
        for (int i = 0; i < 4; i++) {
            if (imageBuffer.getRGB(aux[0] + dx[i], aux[1] + dy[i]) == target_color.getRGB())
                stack.push(new Integer[] { aux[0] + dx[i], aux[1] + dy[i] });
        }

    }
}

有人可以帮助我提高效率吗？

(对于 1020x700 像素图像)执行大约需要 1200 毫秒。

Answer 1

使用队列算法的基本思想，可以阅读here (+示例)。

您可能可以找到其他优化和实现，但我找到了这个 Queue-Linear Flood Fill 。不过你应该自己做这项工作。