基于顶点与邻边相关性的多边形填充算法

A New Polygon Filling Algorithm Based on Pertinence Between Point and Its Abutting Sides

为了加快多边形填充算法的运算速度 ,在深入挖掘顶点与相邻边关系对填充算法影响的基础上 ,提出了一种基于顶点与邻边相关性的多边形填充算法。该算法首先归纳了多边形顶点与邻边相关性的 5种典型类型 ,然后依据顶点与邻边的相关性 ,对原有多边形进行了分割与重新组合 ,使其完全由简单的三角形和梯形这样的单元区域组成 ,这样就将复杂的多边形填充问题转化为这些单元区域的填充问题 ,并由此将扫描线与多边形边求交的乘除计算转化为加减运算。通过实验分析 ,新算法大大减少了运算的时间和复杂度 。

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.