How does the fill operation work in paint applications?

Question

All paint programs, independent of how simple or complex they are, come with a fill tool. This basically replaces the color of a closed region with another color. I know that there are different APIs to do this, but I am interested in the algorithm. What would be an efficient algorithm to implement this tool?

A couple of things I can think of quickly are:

1. Convert image into a binary map, where pixels in the color to be replaced are 1 and all other colors are 0.
2. Find a closed region around the point you want to change such that all the pixels inside are 1 and all the neighbouring pixels are 0.

Sample Image

Answer 1

Many implementations are done as a recursive conquer and divide algorithm. If you do a quick google for "flood fill algorithm" you will find plenty of resources including the excellent wikipedia page on the topic.

Answer 2

The Flood Fill algorithm is what's most commonly used. The following is a naive version of it straight out of my old university textbook, "Computer Graphics with OpenGL" by Hearn Baker, 3rd ed:

void floodFill4 (int x, int y, int fillColor, int interiorColor)
{
  int color;

  /* Set current color to fillColor, then perform the following operations */
  getPixel(x, y, color);
  if (color == interiorColor) 
  {
    setPixel(x,y);  // Set color of pixel to fillColor.
    floodFill4(x + 1, y, fillColor, interiorColor);
    floodFill4(x - 1, y, fillColor, interiorColor);
    floodFill4(x, y + 1, fillColor, interiorColor);
    floodFill4(x, y - 1, fillColor, interiorColor);
  }
}

For large images, however, the above will probably give you a stack-overflow error due to recursing for every pixel. Often, this algorithm is modified so that it uses iteration when filling a row of pixels, then recursively fills the rows above and below. As @kasperjj stated, wikipedia has a good article about this.