Irregular Polygon Fill Using Contour Encoding

Abstract

A filling algorithm for irregular polygons is described. This algorithm is oriented towards raster graphics and uses image memories as job areas. The algorithm is based on the encoding of polygon boundaries by contour following so that all topologies are successfully processed. Thus, concave or convex polygons, holed or not, including possibly duplicate points can be filled. It is quite robust and easy to implement. It uses systematic encoding without special cases. Only two bits for encoding are needed and, thereby, it is suitable for hardware implementation.This algorithm can be used in many fields such as image synthesis, 3D objects or mathematical surface displays with hidden parts.