算法，洪水填充（深度优先搜索） [英] Algorithm, Flood Fill ( Depth First Search )

问题描述

我正在使用Java。

我正在开发一个绘图程序，Paint Can工具正在使用Flood Fill算法，但它太贵了。

I'm working with Java.
I'm developing a paint program, the "Paint Can" tool is using a Flood Fill algorithm, but it is too expensive.

以下是代码：

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

    }
}

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

Can someone help me make this more efficient?

执行时需要（对于1020x700像素图像）约1200ms。

It takes (for 1020x700 pixel image) about 1200ms to execute.

推荐答案

一个简单（可能很小）的改进就是用ArrayDeque替换Stack。

One quick easy (and probably small) improvement would be to replace the Stack with an ArrayDeque.

这将允许你指定初始容量并使您的代码更新。当floodFill区域包含许多像素时，需要扩展多次向下扩展的Vector。这很浪费 - 但并不是那么昂贵

This will allow you to specify a initial capacity AND bring your code more up-to-date. The Vector underlpinning a Stack will need to be expanded many times when the floodFill area contains many pixels. This is wasteful -- but not all that costly

这篇关于算法，洪水填充（深度优先搜索）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！