A New Method for Filling a 2D-Polygon

Abstract

Polygon filling process often involves with lot of procedures which are repeatedly called by one another and making lot of calculations and data reordering works to fill a polygon. One way for improving the efficiency of a polygon filling algorithm is to save the unnecessary calculations and reordering works demanded by traditional algorithms either for rejecting some reordering works or for avoiding some sorting and calculations works. An adaptive filling algorithm is presented here to achieve this goal. The filling process of our new algorithm, NH algorithm, consists of five steps. Firstly, we read the value of edges of a polygon and avoiding the sorting of the sides which are normally required in a traditional algorithm. Secondly, we calculated all boundary points for each sides of a polygon between its maximum and minimum y value. Thirdly, we find all boundary points for each scan level. Fourthly, we sort all boundary points in the order of their minimum x values. And finally, even number of boundary points are selected and filled. Here, the data reordering analysis and experimental statistics between these two algorithms demonstrate the high efficiency of our new algorithm.