Implementation of an Efficient Scan-Line Polygon Fill Algorithm

Abstract

Area filling or polygon filling is a fundamental operation in computer graphics. There are many methods used to fill a closed shape, but the most common one uses the property of raster scan display to perform the filling. These types of algorithms simply depend on finding the intersection points for each scan-line with polygon edges and fill between alternate pairs of intersection points. The implementation of these operations is a straight forward for simple polygons, like convex and concave, and can be more complicated for complex polygon where regions may overlap. This paper present implementation for an efficient algorithm that manages to fill all kinds of polygons depends on using very simple arrays data structure that can be easily programmed by C or Java language. The implementation in Java verified that the algorithm is theoretically and experimentally superior to many other conventional algorithms implementation.

Keywords: Polygon filling, Scan-line filling, Edge-Table, Active-Table, Odd–Even Parity.