Efficient polygon-filling algorithms for raster displays
Michael R. Dunlavey · ACM Transactions on Graphics · 1983
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.