Scan Line Seed Fill Algorithm

A seed pixel on a span is popped from a stack containing the seed pixel.

The span containing the seed pixel is filled to the right and left of seed pixel along a scan line until a boundary is found.

The algorithm remembers the extreme left and the extreme right pixel in the span as xleft and xright.

In the range of xleft ≤ x ≤ xright the scan lines immediately above & immediately below the current scan line are examined to see if they completely contain either boundary pixels or previously filled points. If these scan lines do not contain either boundary or previously filled pixels, then in the range Xleft ≥ x ≥ Xright the extreme right pixel in 0each span is marked as a seed pixel and pushed onto the stack.

The Seed Fill Algorithms assume that at least one pixel is interior to a polygon or region is known. The algorithm then attempts to find and color or fill all other pixels interior to the region.

The method of the seed fill is to start with a seed and recursively check neighboring points to fill in the polygon.

1).Start with a point known to be contained within the polygon. This is the seed.

2).Set the buffer for this seed and draw it.

3).Check each neighbor point. A neighbor point is a point for which the x and/or y values are exactly one greater or less than the current point's values. For each neighbor that is not a boundary point and is not already set, recursively call this function.

The following will demonstrate this method. The polygon below is outlined by black pixels. Start with the point (23, 11), as the seed. This is filled in blue. The buffer would be set so as not to draw this pixel again.

Then each neighbor would be checked. For example, let's check point (24, 10). This point is in the polygon, so we would recursively call the seed fill algorithm on it. At that point, the pixel would be drawn.

Then the neighbors of point (24, 10) would be checked. If we checked pointer (25, 9), we would see that it is a border point and not draw it or recursively call the seed fill algorithm. You can see that this method would lead to a slightly different polygon than one filled with the scan-line method. The top and left edges would not be drawn in the seed fill since no edges are drawn.