What is Boundary fill algorithm?
The boundary fill algorithm is a recursive process that starts with a seed pixel inside the region. The program determines if this pixel is a boundary pixel or if it has previously been filled. If the answer is no, it fills the pixel and calls itself recursively, utilizing every nearby pixel as a new seed. If the response is affirmative, the algorithm returns to the caller.
This method works smoothly on an arbitrarily shaped region by tracking and filling all non-boundary pixels which are either directly or indirectly connected to the seed via a chain of nearby relations. However, due to the possibly huge number of recursive calls, a simple implementation can require time and memory to run, particularly when the region is relatively wide.
Reducing recursive calls in the boundary fill algorithm
In a region filling algorithm, we can fill up the N scan line. Variations can be made to limit the number of recursive calls for this N scan line by rearranging the order in which neighboring pixels are processed in each line. Assume that, one can first fill pixels to the left and right of the seed on the same scan line until boundary pixels are hit to be filled. Ok, then check each pixel up and down the line just drawn to see if it can be used as a new seed (a key pixel line) for the next horizontal line to fill (corresponding to the immediate up or down line). This way the number of recursive calls can be reduced to optimize the boundary fill algorithm for the N number of scan lines.
Boundary fill algorithm
Step 1: Start the algorithm.
step 2: Set four integer variables of a point to fill the boundary of a region in a four connected way.
step 3: Initialize the variables ( point position of x, point position of y, fill color, and boundary color)
step 4: Get pixel of x and y position with variable 'color' in the frame.
step 5:
START of if loop.
check two conditions
colors do not equal to boundary color and fill color
If yes, go to step 6
step 6: Recall the same function and start to set pixel in frame with x and y position in a four connected way.
END of the if loop.
step 7: End of the algorithm
Pseudo-code for Boundary fill algorithm in C language
BoundaryFillRecursive (int a, b, fill_color, boundary_color)
{
int color;
getPixel(a, b, color);
if (color != boundary_color && color != fill_color)
{
setPixel(a, b, fill_color);
BoundaryFillRecursive(a+1, b, fill_color, boundary_color);
BoundaryFillRecursive(a, b+1, fill_color, boundary_color);
BoundaryFillRecursive(a-1, b, fill_color, boundary_color);
BoundaryFillRecursive(a, b-1, fill_color, boundary_color);
}
}
NoteBook : getPixel() and setPixel() is the function of graphics.h header file.
 |
| 4-connected method to fill-up pixels |