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

邱国清

(闽南师范大学 计算机学院， 福建 漳州 363000)

环形多边形区域填充是指在一个给定的区域内对所有像素单元赋予指定的像素值，由于环形多边形的区域形状不同，有些包含非常狭窄区域，有些相互嵌套。在填充时，采用传统的算法如递归种子算法、种子填充算法或扫描线算法难以实现填满整个区域[1-3]。等间距平行线填充算法是通过在指定区域内绘制一组等间距平行线，计算每条平行线与多边形边界的交点并配对成组，根据每组交点坐标值来计算该条平行线所穿越的栅格单元个数及每个栅格单元的坐标，计算出整个区域栅格单元数，依次对每个单元进行填充，从而实现对整个区域填充。该算法不需要设置种子点，特别适用于相互嵌套且狭窄区域的填充。

1 等间距平行线算法

1.1 等间距平行线基本原理

绘制等间距平行线是指在多边形区域内绘制一组平行线并计算其与边界的交点，算法步骤[4]如下：

(1)旋转多边形顶点坐标。由于平行线的倾斜为任意角度，为了计算方便，首先旋转顶点坐标值，目的是使绘制出的等间距平行线相互平行且呈现水平状，设等间距平行线与原坐标系的y轴之间夹角为θ(-180°≤θ≤180°)，新坐标系下轮廓点的转换计算公式为

(1)

(2)

(2)在新的曲面轮廓点中求横坐标的最小值和最大值。取轮廓点中横坐标最小值，d为等间距平行线的间距，首先选定一条平行线开始推算，该平行线与新坐标系Y轴之间的距离称为a值，也……