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», который имеет логическое значение, которое перевернуто на true после того, как вы уже проверили его. Таким образом, вы можете пропустить делать любую математику на него, и вы можете просто сделать что-то вроде этого:

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

Answer 2

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