Seed Fill
Other methods exist for determining how to fill a polygon. References to some of these may be found in the additional resources page. The one to be discussed here is the seed fill algorithm. This algorithm is easy to understand, yet it is difficult to implement and may produce different polygon fills than the scan-line algorithm.
The method of the seed fill is to start with a seed and recursively check neighboring points to fill in the polygon.
-
Start with a point known to be contained within the polygon. This is the seed.
-
Set the buffer for this seed and draw it.
-
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.
| << Previous Page | Next Page >> |