Efficient polygon-filling algorithms for raster displays

Abstract

Parity-based algorithms are described for coloring the interior of a polygon drawn on a raster display. The polygon is input as a chain of incremental moves. These algorithms are automatic in the sense that they require no manually specified interior point. First a distinction is made between two possible coordinate systems for a raster display, the region-oriented and vector-oriented coordinate systems. The Edge Fill algorithm of Ackland and Weste is given for the region-oriented coordinate system, and then is adapted for the vector-oriented coordinate system. Next the algorithm is enhanced in two ways, denoted Fence Fill and Pairwise Fill, which trade storage for speed. Finally, in the Appendix, a correctness property of the vector-oriented version of Edge Fill is proved.