Java Floodfill очень медленно

Я делаю приложение для рисования, и инструмент заливки работает, но для заполнения 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 миллисекунд. Есть ли способ для меня, чтобы ускорить этот процесс вообще? Любая помощь приветствуется.

Источник

2 ответа

Решение

Вот ваша проблема:

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

Вы добавляете каждый пиксель несколько раз (один раз здесь и один раз для каждого блока вокруг этого конкретного пикселя) и перепроверяете его каждый раз, когда он добавляется снова. Если бы у вас был блок 4х4 или что-то подобное, вы действительно не заметили бы замедления, но когда мы говорим о добавлении и проверке 400х180 (72000) пикселей 3 или 4 раза на пиксель, оно становится огромным.

Мое предложение очень простое: проверьте, прежде чем добавить. Или, что еще лучше, создайте небольшой маленький класс "MyPixel", который имеет логическое значение, которое переключается в true после того, как вы уже проверили его. Таким образом, вы можете пропустить любую математику и просто сделать что-то вроде этого:

if(my_pixel.has_been_checked == false)
   queue.add(my_pixel);
Источник

Вы преобразуете пиксельные координаты в строку, а затем анализируете их обратно. По своему опыту я обнаружил, что объединение строк является дорогостоящим действием. Вместо этого просто сохраняйте пиксели как java.awt.Point объекты и читать координаты из тех.

Источник
Другие вопросы по тегам