Home > Research > Short Notes
Site map

Two Filling Algorithms
W. Randolph Franklin (WRF)

Here are two filling algorithms, since each handles things the other doesn't.

Polygon Fill

The input is a polygon defined by a list of vertices and edges.

If a scan line goes exactly thru a vertex, then pretend that it really goes slightly below. The effect is that the code to test whether a scan line crosses an edge is thus:

if yscan<= yhi and ylo < yscan then We have an intersection

Seed (Boundary) Fill

The input is a region defined by setting the pixels around the border. You mark one inside pixel, then the color spreads like a fire. More general regions can be filled. Hearn & Baker mention this on page 127.

The inside must be connected, else only one component is filled. This is harder than you'd think. If the polygon is thin, then the inside may not be connected, so the color stops too soon. This figure shows a long thin triangle, zoomed, and filled with green by touching a point in the center and flooding. Note that two red regions are missed.

Polygon Not Properly Filled