Scan Line Seed Fill Algorithm in Computer Graphics

Scan Line Seed Fill Algorithm:

Scan-Line Seed Fill Algorithm makes the stack becomes quite large because in every loop the algorithm pushes almost 4 to 8 pixels into the stack. The stack frequently contains duplicate pixels.

Scan-Line Seed Fill Algorithm minimizes stack size by posting to the stack only one pixel in any uninterrupted unfilled span of pixels in a single scan line, or row of pixels in a boundary-defined region. Instead of proceeding along a 4-connected or 8-connected chain this algorithm processes pixels in a raster pattern from left to right along each scanline in the region.

Algorithm:

1. A seed pixel on a scan line within the area is popped from a stack containing the seed pixel.

2. The line or span containing the seed pixel is filled to the right & left of the seed pixel including the seed pixel itself until a boundary is found.

3. The extreme left and extreme right unprocessed pixel in the span are saved as x_left and x_right respectively.

4. The scan line above and below the current scan lines are examined in the range x_left to x_right for any contiguous span of either boundary pixels or previously filled pixels. If any such span is found it is simply crossed over. The extreme right pixel in all the unfilled spans on these scan lines within the same range is marked as a seed pixel and pushed onto the stack.