A New Polygon Filling Algorithm Based on Pertinence Between Point and Its Abutting Sides
基于顶点与邻边相关性的多边形填充算法

Present polygon filling algorithms including scanline algorithm, seed filling algorithm and the algorithms based on the two classical filling theories, are analyzed and compared in this paper. A new filling algorithm is put forward, which is based on thorough analysis of the relations between point and its abutting sides. This new filling algorithm divides all points of a polygon into five types at firstly, and transforms the polygon into unit areas which are simple triangles and trapeziums by the line passing the points. Using the characteristics of bevel edges, the unit areas filling can replace the multiplication-division with the addition-subtraction. It decreases the time and complexity of filling the whole polygon. This paper explains the design of the algorithm and how it is going on, and also presents the data structures storing the information of points and unit areas. In the end, some experimental results show that the new algorithm has a high efficiency and a good stability.