Title: A Polygon Seed Fill Algorithm

It was interesting to read in C Vu 15.2 that Francis would be interested to hear from anyone who knows of a good fill algorithm. I recalled having a go at getting a seed fill algorithm to work several years ago. In those days I was writing in Pascal so I thought it would be an interesting exercise to rewrite it in C++.

The first task was to find the source of the algorithm. After a bit of a search I found a description of the algorithm by Rogers [Rogers]. Unfortunately, his description of the algorithm is not all that clear and the pseudo-code provided would never have worked as far as I could see. I had to do a lot of reading between the lines before I thought I understood the algorithm the author was trying to describe. I remembered having this trouble the first time around.

The algorithm fills an area bounded by either the screen limits or by pixels of a specified colour (the bounding pixels). The bounding pixels must form a continuous 'fence' otherwise the fill colour will leak out through any gaps. A border is continuous if it is impossible to move from an interior pixel to an exterior pixel by only horizontal or vertical steps without passing through a border pixel. The diagram below shows a completely continuous border and may help to visualise the situation.

The algorithm attempts to fill the enclosed region by starting from an arbitrarily chosen 'seed' pixel. The seed pixel can be either inside the boundary or it can be outside the boundary. Taking the above diagram as an example, if the seed is inside the boundary, then the central region will be filled. If the seed is outside the boundary, then the area outside the boundary will be filled.

The algorithm works as follows.

The seed pixel location is pushed onto a stack and the algorithm's main loop is entered. The loop will exit at this point only when the stack is empty. The body of the loop immediately pops the pixel location from the stack. The pixel at that location is filled. The algorithm then fills the row of pixels to the left of the seed until either a boundary pixel is found or the limit of the screen is reached. The horizontal position of the last pixel to be filled is stored and represents the extreme left of the fill line. Next, the pixels on the row to the right of the seed are filled until either a boundary pixel or the screen limit is reached. The location of the last pixel to be filled is stored and represents the extreme right of the fill line.

The algorithm now considers the row above the seed pixel (if that row exists). This line is scanned from the previously stored extreme right position to the extreme left position, inclusively. No pixels are filled during this upper scan; instead the first non-border pixel location is pushed onto the stack. If this upper scan line is broken by groups of border pixels, the first non-border pixel between each group (in the direction of the scan) is also pushed onto the stack.

The row below the seed pixel is now scanned in exactly the same way as the row above the seed pixel and pixel locations pushed onto the stack accordingly.

This completes the first iteration through the main loop. The stack is checked to see whether it is empty and, assuming it is not, the last pixel location to be pushed on the stack is popped off (to form the next seed, in effect). The filling and scanning process is repeated. Eventually, the stack is exhausted and the algorithm terminates. All bounded pixels have been filled.

As an example, consider the 10 x 10 display grid below. The border pixels are shown as asterisks and the original seed (at location 6, 5) is marked by an 'S'. The numbers within the area to be filled show the order and location of pixels pushed onto the stack during the fill process. The shaded background indicates the position of the pixels to be filled.

First, the seed pixel is filled. The five pixels to the left of the seed are filled and then the single pixel to the right of the seed is filled. The extreme left and extreme right scan limits are stored as 1 and 7 respectively. The row above the seed pixel is now examined within the scan limits. It can be seen that row 4 is divided into two groups of unfilled pixels. Accordingly, the locations at 7, 4 and 1, 4 are pushed onto the stack. Similarly, the row below the seed pixel is examined within the scan limits. This row is also found to be divided into two groups and the pixels at locations 7, 6 and 2, 6 are pushed onto the stack. This completes one pass of the algorithm. The stack is not empty and so the pixel location 2, 6 (the last one to be pushed) is popped off the stack. The process continues by filling the new seed pixel at location 2, 6. The pixel at 2,7 is now pushed onto the stack and so on. Eventually, all the bounded pixels are filled, there are no more pixels to push onto the stack, the stack becomes empty and the process ends.

The theoretical basis for this algorithm, as Rogers indicates, is described in a paper by Shani [Shani].

My C++ realisation of the seed fill algorithm is as direct as possible. The only C++ feature of note is the use of the standard template library stackclass. The algorithm could just as well be written in any language that supports the concept of a stack. A stack could also be constructed by hand and thus make practically any programming language suitable.

A 20 x 20 display grid is included in the example code for the purposes of testing. An arbitrary border has been defined that includes an inner 'hole'.

#include <stack>
#include <iostream>

const int width = 20;
const int height = 20;

char screen[height][width] =
{" ******** ",
 " *** * * ",
 " * * * ***** ",
 " * *** * ",
 " * * ",
 " * ***** * ",
 " * * * * ",
 " * *** * * ",
 " * * ***** ",
 " * * ",
 " * ** ***** ",
 " * **** * ",
 " * * ",
 " * ******* * ",
 " * * ** * ",
 " * * * **** ",
 " * *** * * ",
 " * ** *** ",
 " ****** * ",
 " ********* "};

struct Location {
int column;
int row;
};

std::stack<Location> seed_stack;

void display() {
  // Display the image.
  for (int row = 0; row < height; ++row) {
    for (int column = 0;
        column < width;
        ++column) {
      std::cout << screen[row][column];
    }
    std::cout<< std::endl;
  }
  std::cout<< std::endl;
}

void pixel(const Location & position,
           char character) {
  // Place the character on the screen
  // at the specified location.
  screen[position.row][position.column]
                               = character;
}

char pixel(const Location & position) {
  // Get the pixel at the specified location.
  return
      screen[position.row][position.column];
}

int main() {
  display();

  Location seed_location = {7, 4};
  seed_stack.push(seed_location);

  while (!seed_stack.empty()) {
    Location location = seed_stack.top();

    // Fill the pixel at the seed location.
    pixel(location, '*');

    // Fill the line to the left of the seed.
    --location.column;
    while (location.column >= 0
           && pixel(location) != '*') {
      pixel(location, '*');
      --location.column;
    }
    int extreme_left = location.column + 1;
    location.column
             = seed_stack.top().column + 1;
    seed_stack.pop();
    // Fill the line to the right of the seed.
    while (location.column < width
           && pixel(location) != '*') {
      pixel(location, '*');
      ++location.column;
    }
    int extreme_right = location.column - 1;
    // Scan above the seed row.
    --location.row;
    if (location.row >= 0) {
      bool previous_pixel_is_border = true;
      for (location.column = extreme_right;
           location.column >= extreme_left;
           --location.column) {
        if (previous_pixel_is_border
            && pixel(location) != '*') {
          seed_stack.push(location);
          previous_pixel_is_border = false;
        }
        else
        if (pixel(location) == '*') {
          previous_pixel_is_border = true;
        }
      }
    }
    // Scan below the seed row.
    if (location.row < height - 2) {
      location.row += 2;
      bool previous_pixel_is_border = true;
      for (location.column = extreme_right;
           location.column >= extreme_left;
           --location.column) {
        if (previous_pixel_is_border
            && pixel(location) != '*') {
          seed_stack.push(location);
          previous_pixel_is_border = false;
        }
        else
        if (pixel(location) == '*') {
           previous_pixel_is_border = true;
        }
      }
    } 
  }
  display();
  return 0;
}