基于栅格的环形多边形区域填充算法

An new algorithm for filling circular polygon based on grid

环形多边形是指在一个多边形里除去嵌套的一个或多个其他多边形的剩余部分,根据环形多边形的形状特征,在栅格原理的基础上采用等间距平行线原理提出了一种环形多边形区域填充新算法。首先,依据等间距平行线原理在填充区域绘制若干条任意角度的等间距的平行线,依次计算每条线与多边形轮廓的交点并排序配对输出;其次,把多边形区域栅格化,根据交点坐标计算每条线经过的栅格个数及行列值;最后,对所有栅格单元进行填充,从而实现指定区域的填充。通过实验数据表明,等间距平行线算法能适用于任意角度的区域填充,效果良好。

An annular polygon is the remaining part of a polygon in which one or more other polygons are nested,based on the principle of grid and equidistant parallel lines,a new algorithm for filling circular polygon is proposed by using the principle of equidistant parallel lines.First,several equal-spaced parallel lines at any angle are drawn in the filled area according to the principle of equidistant parallel lines and the intersection points of each line.Secondly,the polygon contour are calculated in turn and the corresponding output pairs are sorted,the row and column values of raster cells are calculated.Las,populates all grid elements,so as to fill the specified area.The experiment data show that the algorithm can be applied to any angle of the region filling and effect is good.