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

您要多次添加每个像素（此处一次，该特定像素周围的每个块一次）并在每次再次添加时重新检查它。如果你有一个 4x4 的块，或者类似的东西，你真的不会注意到速度变慢，但是当我们谈论添加 400x180 (72,000) 像素并每个像素检查 3 或 4 次时，它会变得很大。

我的建议很简单：先检查再添加。或者甚至更好，制作一个小的 "MyPixel" class ，它有一个布尔值，在你已经检查它之后翻转为 true 。这样，您就可以跳过对其进行任何数学运算，而只需执行以下操作即可：

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

Answer 2

您正在将像素坐标转换为字符串，然后再将它们解析出来。根据我的经验，我发现字符串连接是一项昂贵的操作。相反，只需将像素存储为 java.awt.Point 对象并从中读取坐标。

Java Floodfill 真的很慢

Java Floodfill really slow

java

flood-fill