Flood Fill Very Slow

Processing Coding Questions
1

I have created the flood fill program shown below. When you click in an area then that shape will fill with black. I am pleased with the result except that it is incredibly slow. I believe this is because every surrounding pixel that qualifies for change needs to be checked to make sure that it is not already on the arraylist. Is there a way to speed up this process (the paint bucket tool on Microsoft Paint is almost instantaneous!)?

Thank you.

//select target colour
int targetRed = 0;
int targetGreen = 0;
int targetBlue = 0;

//set global variables
color c;
int currentpixel;
int pixeltocheck;
ArrayList<Integer> pixelstochange= new ArrayList();

//set arraylist counter to 0
int arraylistindex = 0;

void setup() {
  size(600, 600);
  noFill();
  stroke(0);
  background(255);
  strokeWeight(2.5);

  //create random shapes
  for (int i=0; i<35; i++) {
    rect(random(600), random(600), 50, 50);
    ellipse(random(600), random(600), 200, 100);
  }
  loadPixels();
}

void draw() {

  //go to next pixel on arraylist, repeat check 4 surrounding pixels
  if (arraylistindex<pixelstochange.size()&&pixelstochange.size()>0) {
    checkSurrounding();
  }
}

//click on area, get pixel number and colour
void mouseClicked() {

  currentpixel=mouseY*width+mouseX;
  c =pixels[currentpixel];
  pixels[currentpixel]=color(targetRed, targetGreen, targetBlue);
  testColour();
}

//check not target colour
void testColour() {

  if (red(c)!=targetRed||green(c)!=targetGreen||blue(c)!=targetBlue) { 
    addToArrayList();
  }
}

//if different add pixel to arraylist
void addToArrayList() {

  pixelstochange.add(currentpixel);
  checkSurrounding();
}

//check 4 surrounding pixels
void checkSurrounding() {

  int checkingpixel = pixelstochange.get(arraylistindex);

  pixeltocheck = checkingpixel-width;
  if (pixeltocheck>0) {
    color top =pixels[pixeltocheck];
    if (red(top)!=targetRed||green(top)!=targetGreen||blue(top)!=targetBlue) {    
      checkOnArrayList();
    }
  }


  pixeltocheck =checkingpixel+width; 
  if (pixeltocheck<width*height) {
    color bottom =pixels[pixeltocheck];
    if (red(bottom)!=targetRed||green(bottom)!=targetGreen||blue(bottom)!=targetBlue&&pixeltocheck<width*height) {     
      checkOnArrayList();
    }
  }

  pixeltocheck =checkingpixel-1;
  if (pixeltocheck>0&&pixeltocheck%width!=0) {
    color left =pixels[pixeltocheck];
    if (red(left)!=targetRed||green(left)!=targetGreen||blue(left)!=targetBlue) {     
      checkOnArrayList();
    }
  }

  pixeltocheck =checkingpixel+1;
  if (pixeltocheck<width*height&&pixeltocheck%width!=width-1) {
    color right =pixels[pixeltocheck];
    if (red(right)!=targetRed||green(right)!=targetGreen||blue(right)!=targetBlue) {    
      checkOnArrayList();
    }
  }

  //increment arraylist counter
  arraylistindex++;
}

//for each, if different check not on arraylist
//if not on arraylist, add to array list
void checkOnArrayList() {

  if (pixelstochange.contains(pixeltocheck)) {
    return;
  } else {
    pixelstochange.add(pixeltocheck);
    pixels[pixeltocheck]=color(targetRed, targetGreen, targetBlue);
    updatePixels();
    println(pixelstochange.size());
  }
}
1 Like
2

You’re creating an animation that gradually fills the shape with the color. If you want it to be instantaneous, change this line:

if (arraylistindex<pixelstochange.size()&&pixelstochange.size()>0) {

To this:

while (arraylistindex<pixelstochange.size()&&pixelstochange.size()>0) {

This will cause your algorithm to continue running until the shape is filled with the color, instead of splitting the work up between frames.

If that’s still not what you want, I’d recommend you do some profiling: what part of this program is taking up the most time? Which line of code is most expensive? The only way to answer that is to measure the performance.

You might also want to consider: are you only checking the pixels you need to? Your algorithm appears to get slower over time, which is suspicious to me. Are you sure you aren’t checking extra pixels?

Sounds like some debugging is in your future. Good luck!

3 Likes