1.3.3. Filling Areas

Similarly to the line rasterisation, solid figures such as filled polygons or circles are created by intensifying the pixels in their interiors and on their boundaries.
We present you an algorithm that operates by computing spans that lie between left and right edges of the polygon. The span extrema are calculated by computing a scan line intersection from the intersection with the previous scan line. Have a look at the next image, which shows a polygon and one scan line passing through it. The intersections of scan 4 with edges AF and CD lie on integer coordinates, whereas those for AB and BC do not; the intersections are marked in the figure by vertical red marks. (FOLEY et al. 1996, p. 92)

We must determine which pixels on each scan line are within the polygon, and we must set the corresponding pixels to their appropriate values. By repeating this process for each scan line that intersects the polygon, we scan convert the entire polygon. (FOLEY et al. 1996, p. 92-93)

The described algorithm handles both convex and concave polygons, even those that are self-intersecting or have interior holes. (FOLEY et al. 1996, p. 92)

Algorithm "Filling Polygon" in few words

When filling a polygon, the intersections that lie between left and right edges of the polygon have to be computed. Afterwards, the resulting spans can be filled. (FOLEY et al. 1996, p. 92) According to this, the algorithm for filling polygons features two steps:

• Computing the intersections for each scan line.
• Filling the polygon alternately between the intersections.