Java Floodfill 真的很慢

Question

我正在制作一个绘画应用程序，并且洪水填充工具可以工作，但它需要大约两分钟才能填充 400x180。我可以做什么来加快这个过程？这是我目前使用的代码。

public void gradientSize(int x, int y, int origRGB, int index){
    queue = new ArrayList<String>(); //queue is an ArrayList<String> that holds the points
    time = System.currentTimeMillis(); // time is a long so I can calculate the time it takes to finish a flood fill
    if(new Color(origRGB).equals(foreground)){ //foreground is the color the flood fill is using to fill in. origRGB is the RGB of the color I clicked
        return;
    }
    if(!testFill(x, y, origRGB)){
        return;
    }
    queue.add(pixel(x,y));
    while(!queue.isEmpty()){
        String pixel = queue.get(0);
        int x2 = Integer.parseInt(pixel.substring(0, pixel.indexOf(","))); 
        int y2 = Integer.parseInt(pixel.substring(pixel.indexOf(",")+1,pixel.length()));
        queue.remove(0);
        if(testFill(x2, y2, origRGB)){
            queue.add(pixel(x2+1, y2));
            queue.add(pixel(x2-1,y2));
            queue.add(pixel(x2,y2+1));
            queue.add(pixel(x2,y2-1));
            gradientPoints.add(pixel(x2, y2)); //gradientPoints is an ArrayList<String> that contains all the points for the fill
            processed[y*image.getWidth()+x] = true; //processed[] is a boolean array that has a true or false value for each pixel to determine if it has been looked at yet.
        }
    }
}

public boolean testFill(int x, int y,int origRGB){ //testFill tests if the current pixel is okay to be filled or not
    if(x>=0&&x<image.getWidth()&&y>=0&&y<image.getHeight()){
        int testRGB = image.getRGB(x, y);
        Color orig = new Color(origRGB,true);
        Color test = new Color(testRGB,true);
        if ((Math.abs(orig.getRed() - test.getRed()) <= difference) && (Math.abs(orig.getGreen() - test.getGreen()) <= difference)&& (Math.abs(orig.getBlue() - test.getBlue()) <= difference)&&(Math.abs(orig.getAlpha() - test.getAlpha()) <= difference)) {
            if (!gradientPoints.contains(pixel(x,y))) {
                if (!queue.contains(pixel(x,y))) {
                    if (processed[y*image.getWidth()+x]==false) {
                        return true;
                    }
                }
            }
        }
    }
    return false;

}

public String pixel(int x, int y){//this returns the String value of a pixel's x and y coordinates.
    return String.valueOf(x)+","+String.valueOf(y);
}
public void gradientFillSolid(){ //This gets all the points from gradientPoints and fills each pixel from there.
    for(String s:gradientPoints){
        int x = Integer.parseInt(s.substring(0, s.indexOf(',')));
        int y = Integer.parseInt(s.substring(s.indexOf(',')+1,s.length()));
        image.setRGB(x, y, foreground.getRGB());
    }
    System.out.println(System.currentTimeMillis()-time);
    repaint();
}

400x180 矩形的输出为 148566 毫秒。有没有办法让我加快这个过程？如有任何帮助，我们将不胜感激。

Answer 1

这是你的问题:

queue.add(pixel(x2+1, y2));
queue.add(pixel(x2-1,y2));
queue.add(pixel(x2,y2+1));
queue.add(pixel(x2,y2-1));

您将每个像素添加多次(此处一次，该特定像素周围的每个 block 一次)，并在每次再次添加时重新检查它。如果你有一个 4x4 block 或其他东西，你真的不会注意到速度减慢，但当我们谈论添加 400x180 (72,000) 像素并每个像素检查 3 或 4 次时，它会变得巨大。 p>

我的建议很简单:添加之前先检查。或者更好的是，创建一个小的“MyPixel”类，它具有一个 boolean 值，在您检查完它之后该值会翻转为 true。这样，您就可以跳过对其进行任何数学运算，只需执行以下操作即可:

if(my_pixel.has_been_checked == false)
   queue.add(my_pixel);