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

摘要

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