Seed Fill Algorithms
Presentation by ….
Yagnik Parmar(299) &
Jayveer Parmar(314)
Polygon Filling Algorithms
For highlighting all the pixels inside the polygon, 2 approaches can be
used-
1. Scan Fill
2. Seed Fill (Boundary Fill, Flood Fill )
SEED FILL ALGORITHMS
A different approach is used in this algorithm, it assume that at least one pixel interior
to a polygon or region is known. The algorithm then attempts to find and colour or fill
all other pixels interior to the region.
Region may be either interior or boundary defined.
Fig.. Interior defined region Fig.. Boundary defined region
SEED FILL ALGORITHMS
Sometimes we come across an object where we want to fill the area and its
boundary with different colors. We can paint such objects with a specified
interior color instead of searching for particular boundary color as in boundary
filling algorithm.
Instead of relying on the boundary of the object, it relies on the fill color. In
other words, it replaces the interior color of the object with the fill color.
When no more pixels of the original interior color exist, the algorithm is
completed.
Once again, this algorithm relies on the Four-connect or Eight-connect method
of filling in the pixels. But instead of looking for the boundary color, it is
looking for all adjacent pixels that are a part of the interior.
A SIMPLE SEED FILL ALGORITHM
A simple seed fill algorithm for a boundary-defined region can be developed using a stack. A
stack is simply an array, or other storage space, into which values are sequentially placed, or
from which they are sequentially removed. As new values are added to or pushed onto the
stack, all previously stored values are pushed down one level. As values are removed or popped
from the stack, previously stored values float or pop up one level. Such a stack is referred to as a
first in, last out (FILO), or push-down, stack. A simple seed fill algorithm is then:
Simple seed fill algorithm using a stack:
Push the seed pixel onto the stack
while the stack is not empty
Pop a pixel from the stack
Set the pixel to the required value
SCAN LINE SEED FILL ALGORITHM
The stack can become quite large. The stack frequently contains duplicate or
unnecessary in formation. An algorithm which minimizes stack size attempts to
seed only one pixel in any uninterrupted scan line span. This is called a scan line
seed fill algorithm.
The scan line seed fill algorithm is applicable to boundary defined regions.
The 4-connected boundary-defined region may be either convex or concave, and it
may contain one or more holes. The region exterior to and adjacent to the
boundary-defined region may not contain pixels with a value or color
corresponding to the one used to fill the region or polygon Conceptually, the
algorithm works in four steps.
Scan line seed fill algorithm:
1. A seed pixel on a span is popped from a stack containing the seed pixel.
2. The span containing the seed pixel is filled to the right and left of the seed pixel
along a scan line, until a boundary is found.
3. The algorithm remembers the extreme left and the extreme right pixels in the
span as XLef and XRight.
4. In the range of Xlef <= x <= Xright, the scan line immediately above and
immediately below the current scan line are examined to see if they completely
contain either boundary pixels or previously filled pixels. If these scan lines do not
contain either boundary or previously filled pixels, then in the range Xlef <= x <=
Xright the extreme right pixel in each span is marked as a seed pixel and pushed
onto the stack.
REFERENCES
Procedural elements for computer graphics by David F. Rogers
