邱国清

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

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

1 等间距平行线算法

1.1 等间距平行线基本原理

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

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

(1)

(2)

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

(3)

(3)根据斜率公式计算交点坐标值，即

(4)

(4)根据交点坐标计算该条平行线穿过的栅格单元的行列序号，即

(5)

(6)

1.2 算法描述

(1)建立多边形顶点集合，输入每个顶点的坐标值，判断横坐标值，找出最大值和最小值。设置等间距平行线的间距值，根据公式(3)计算出第一条平行线的横坐标值。

(2)根据公式(4)判断当前平行线与多边形轮廓是否相交，如果没有交点则执行第(3)步，否则执行第(4)步。

(3)计算下一条平行线的横坐标，返回第(2)步。

(4)根据公式(4)计算平行线与轮廓边界的交点并保存。

(5)判断a的值是否大于多边形顶点横坐标最大值，如果小于则返回第(3)步，否则退出。

等间距平行算法流程如图1所示。

图1 等间距平行线算法流程图

1.3 区域栅格化

区域栅格化是指把整个环形多边形所在区域划分成大小一致且紧密相连的网格阵列，每个网格相当于一个像元，每个像元由行列号确定其位置。网格大小可以根据精度要求进行设置，所有网格面积等于环形多边形区域的大小，对所有单元赋予指定像素值，实现了多边形的区域填充。

1.4 裁剪算法

线段裁剪是计算机图形学研究的一个基本内容[6]，在图形处理系统中，裁剪是指在指定区域内识别图形内、外部分的过程[7]。多边形裁剪算法是指被裁剪的多边形与裁剪区域均为多边形的情形，该算法的原理是：由入点开始，沿被裁剪多边形追踪，当遇到出点时跳转到裁剪区域继续追踪；如果再次遇到入点，则跳转回被裁剪多边形继续追踪。重复以上过程，直到回到起始入点，算法步骤如下：

(1)计算多边形a、c的交点，把交点分别加入到两个多边形的顶点数组中，构成新的集合a′、c′；

(2)建立交点I集合，记录交点类型及其在两个多边形顶点集合中的位置；

(3)在交点集合I中取出一个入点，在a′中查找该入点的位置并沿顺时针方向追踪a′的顶点集合，直到遇到下一个交点；

(4)根据第(3)步搜索到的交点在c′表中的位置，沿顺时针追踪c′的顶点表，直至遇到下一个交点。

(5)跳转到a′，重复第三、四步，直至回到起始交点。

2 数据验证

2.1 狭窄区域填充

首先根据多边形区域所有顶点坐标值绘制环形多边形，如图2(a)所示，该环形区域有多个凹进和凸起部分，由于其中一些狭小的区域间距过小，很难实现填充。为此根据等间距平行线绘制算法，在多边形区域内绘制一组平行线，依次循环判断每一条平行线与边界是否相交并计算交点，记录并保存每个交点的坐标值，排序配对输出。根据每一对坐标值依次判断该条平行线经过的栅格单元个数，最终的效果如图2(b)、(c)所示，多边形区域内有52个坐标对，每一个坐标对表示一条直线。以图2(d)为例，计算出22个坐标值，如表1所示。

图2 不规则多边形区域填充

表1 平行线与多边形轮廓的交点

根据表1中坐标值，可以计算出每条平行线经过的栅格单元个数及行列值，如表2所示。

表2 栅格单元的坐标值

2.2 多边形嵌套区域填充

环形多边形是指在一个多边形里面除去嵌套一个或多个其他多边形的剩余部分。此时必须计算每条平行线与有关多边形轮廓的所有交点，然后排序，配对输出，如图3(a)所示。

在图3(a)中可以看到，多边形acdefghija中嵌套了另一个多边形ACDEFGHA，两个多边形各自有若干个狭长的区域且相互嵌套，彼此之间间距非常小，如夹角efg和DEF、夹角ghi和FGH之间缝隙过于狭窄，填充比较困难。通过计算平行线与两个多边形轮廓的交点，可以快速实现填充效果，但此时在交点配对时要注意区分，因为当平行线还未与内部多边形相交时，只需要对平行线与外部多边形交点配对输出，当平行线同时与两个多边形轮廓都有交点时，此时交点配对难度比较大，填充效果如图图3(b)所示。

(a) 嵌套多边形 (b) 内部多边形绘制平行线 (c) 嵌套多边形绘制平行线 图3 间距值为9，倾斜角为22.5°

(a) 多边形相交 (b) 嵌套多边形绘制平行线图4 间距值为5，倾斜角为-22.5°

图3(b)表示的是在内部多边形ACDEFGHA绘制等间距平行线的效果，从图中可以看到，有12条平行线，包含了24对坐标值。在同样的间距值条件下，外部多边形acdefghija有30条平行线，包含了60对坐标值。与内部多边形相比，外部多边形多了36对坐标值，根据该数值绘制出嵌套区域平行线如图3(c)所示。

绘制嵌套多边形平行线时，要考虑到平行线同时经过内、外多边形轮廓，在图3(c)中可以看到，平行线与外部多边形有60个交点，与内部多边形有24个交点，从第18条平行线开始同时和两个多边形都有交点，第27条平行线离开内部多边形只和外部多边形相交，即第18条到26条平行线在交点配对时，必须是外部多边形轮廓交点与内部多边形轮廓交点配对，其余都是外部多边形轮廓交点配对输出。

2.3 多边形相交区域填充

在区域填充中，当两个任意形状多边形相互相交时，一个多边形为裁剪对象，另一个则是被裁剪对象，此时，被裁剪的多边形分为内侧和外侧两部分。为了实现内侧或外侧区域填充，需要运用1.4节多边形裁剪算法来实现，如图4所示。在图中可以看出，多边形acdefghija和ACDEFA相交，交点集合为{a1，a2，a3，a4，a5，a6，a7，a8}，其中多边形acdefghija是被裁剪对象，根据1.4节裁剪算法得出该多边形被裁剪后得到的内侧多边形为{a1，a2，a3，e，a4，D，a5，a6，a7，a8，A，a1}，利用等间距平行线填充算法对内侧多边形填充，如图4(b)所示。

3 数据分析

3.1 算法复杂度分析

算法的复杂度是衡量该算法优劣的标准，包括空间复杂性和时间复杂性[8]。等间距平行线填充算法的计算量取决于平行线的数目，间距越小，填充效果越好，但交点越多，包含的栅格单元越多，计算量增大。对于普通的制图，算法在时间上差别不明显，以图3(a)为例，算法的复杂度见表3。

表3 嵌套多边形复杂度分析

3.2 算法通用性分析

等间距平行线区域填充算法取多边形顶点中横坐标中的最小值作为平行线的初始值开始循环绘制，每循环一次绘制一条平行线，间隔等于设定的精度值，直到最后一条平行线的横坐标大于多边形中横坐标最大值时停止循环，每一次循环判断该条平行线与多边形的所有边是否存在交点，如果有则计算并保存交点坐标，否则接着循环，直到该条平行线与每条边都计算过，这就是等间距平行法的两重循环原理，算法简单，有较好的适用性。

3.3 技术难点分析

(1)裁剪算法中如何把交点分别插入两个相交多边形顶点集合。

在裁剪算法中，裁剪对象与被裁剪对象轮廓的交点值，需要分别存入到两个多边形顶点集合中，同时要保证插入到准确的位置，如图4(a)所示，被裁剪多边形acdefghija轮廓有9条边，从第一条边ac开始判断，是否与裁剪对象ACDEFGA相交，判断依据如下：

max(xa1，xa2)

min(xa1，xa2)>max(xc1，xc2)或

max(ya1，ya2)

min(ya1，ya2)>max(yc1，yc2),

如果上述条件成立，则说明无交点。根据以上判断依据，线段ac两个端点横坐标最大值小于裁剪对象直线AC两个端点最小值，说明无交点，线段cd两个端点横坐标最大值大于线段AC两个端点的最小值，说明有交点，则计算两条线段的交点坐标，分别插入到线段cd和AC两个端点所在顶点集合中间的位置。

(2)如何实现平行线与多边形轮廓配对输出。

在一些比较复杂的多边形区域中，包含多个凹进或凸起部分，当平行线同时经过多个这些部分时，与之同时都有交点，此时需要对交点配对输出。以图3(b)为例，当平行线同时与外多边形acdefghija和内多边形ACDEFGHA轮廓相交时，此时每条平行线会计算出4个交点，此时第1、4交点为外部多边形轮廓交点，第2、3为内部多边形轮廓交点，所以交点要分别配对。核心代码如下：

for(int i=0；i

g.drawLine(tx[i]，ty[i]，tx[i+1]，ty[i+1])； //平行线还未与被嵌套的多边形有交点

}

for(int i=z；i

g.drawLine(tx[i]，ty[i]，kkx[i-z]，kky[i-z])； //平行线与被嵌套的多边形有交点

i++；

g.drawLine(kkx[i-z]，kky[i-z]，tx[i]，ty[i])； } //取内部交点与外部交点配对输出绘制直线

for(int i=zz+z；i<100；i=i+2){

g.drawLine(tx[i]，ty[i]，tx[i+1]，ty[i+1])；}//平行线离开被嵌套的多边形没有交点

(3)裁剪算法中如何创建内侧多边形顶点集合。

在两个相交多边形内侧或外侧区域填充，首先需要创建内侧或外侧多边形顶点集合，以图4(a)为例，交点为a1、a2、a3、a4、a5、a6、a7、a8。按裁剪算法原理，先从被裁剪多边形顶点集合开始搜索，当遇到a1时，跳到裁剪对象顶点集合继续搜索，当遇到a2时再次跳到被裁剪对象继续搜索下一个交点，直到所有8个交点被搜索一遍。关键代码如下：

t=1； // 计数器，记录交点个数

while (true){

if (t%2==1) // 在被裁剪多边形中搜索

for(int j=0；j

If (ax[j]!=ex[t]&&ay[j]!=ey[t]){ //被裁剪对象顶点与交点集合顶点不一致

dx[k++]=ax[j]；

dy[k++]=ay[j]；} //把被裁剪对象顶点坐标存入dx、dy数组

else {

dx[k++]=ex[t]；

dy[k++]=ey[t]； } //否则把交点集合顶点存入dx、dy数组

break；}

if (t%2==1) // 在裁剪多边形中搜索

for(int jj=0；jj

If (cx[jj]!=ex[t]&&cy[jj]!=ey[t]){ //裁剪对象顶点与交点集合顶点不一致

dx[k++]=cx[jj]；

dy[k++]=cy[jj]；} //把裁剪对象顶点坐标存入dx、dy数组

else {

dx[k++]=ex[t]；

dy[k++]=ey[t]； } //把交点集合顶点坐标存入dx、dy数组

break；}

t++；

if (t>=8) // 交点搜索结束

break；

} } // dx[]、dy[]是保存内侧多边形坐标值

(4)如何实现栅格单元的快速填充。

基于栅格的填充是通过计算每条平行线经过栅格单元的行列值，对每个栅格单元填充，此时要准确计算每个单元的坐标值，如图5所示，表示的是第8条平行线经过的栅格单元填充，因为每个单元大小一致，根据交点坐标可以得出该条平行线穿越单元的个数，同时根据交点的横坐标或纵坐标值，依据设定好的像元宽度值，以此推算每个像素单元的中心坐标值，最后对所有单元赋予指定像素值。

图5 栅格填充效果

4 小结

本文基于等间距平行线原理提出了一种区域填充算法，计算每条平行线与多边形轮廓的交点，测算出每条平行线经过的栅格单元行列值及坐标，通过对所有的栅格单元进行填充，从而实现了整个区域的快速填充。对于狭小区域或凹进与凸出部位以及多个多边形相互嵌套、裁剪等，都有较好的填充效果，具有良好的通用性。