区域填充算法在多重嵌套多边形图形中的应用

邱国清



区域填充算法在多重嵌套多边形图形中的应用

邱国清

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

区域填充算法在制图中有着广泛的应用，但目前对任意多个多边形相互嵌套的区域填充算法很难实现，为此提出一种基于等间距平行线的区域填充算法。首先，按一定的间隔绘制一组平行线；其次，计算所有平行线与任意嵌套的多边形的交点；最后，以间隔值作为子块大小的参数，计算每条平行线所包含的子块个数及坐标值并填充，最终完成整个区域填充。在实验的过程中解决了如何准确计算相互嵌套的多边形同时与平行线都有交点的问题。通过自主设计的应用程序验证多组数据，表明该算法能快速准确地完成任意数量的多边形相互嵌套的区域填充并对实验过程中的技术难点和算法复杂度做了分析。

等间距平行线；内点；多重嵌套；区域填充；子块

计算机辅助设计技术是当今计算机辅助领域中的研究热点之一[1]。区域填充算法在计算机辅助设计及其他领域有广泛的应用，是将区域内的一点(常称为种子点)赋予给定颜色，然后将这种颜色扩展到整个区域的过程[2]。常用的算法有递归种子填充算法和扫描线填充算法，由于这些算法在实际应用中存在一个点多次反复进入堆栈占用大量存储空间，当有多个对象需要填充时，种子点的选择非常困难[3]，故在这些算法的基础上产生了一些改进算法，这些经典的填充算法在填充前需要设定种子点，往返进出堆栈，还需要判断多边形边界是否溢出，算法的通用性和填充的自动化效果比较低，而随着计算机图形学技术的发展，区域填充的自动化和适应性算法成为衡量填充算法优劣的关键参数。相对于效率而言，算法的通用性和自动化程度是更关注的问题[4]。基于等间距平行线区域填充算法是一种研究全自动填充任意复杂多边形区域的技术，是在借鉴其他算法的基础上做出改进，该算法以绘制一组等间距平行线为原理，计算每条线所经过的内点，计算简单，对图形的适应性强，不需要设置填充胚和求解边界像素点序列，不存在一个点多次反复进入堆栈的问题。基于AutoCAD的二次开发[5]，可以将区域填充技术作为子模块嵌入到CAD系统中。

1 基于等间距平行线区域填充算法

基于等间距平行线区域填充算法与传统的递归种子填充算法和扫描线填充算法的区别在于，等间距平行线区域填充算法不需要设置填充胚，每个填充点也不需要反复多次进入堆栈，没有堆栈溢出的问题，新算法对于任意大小的多边形区域都可以快速实现填充，特别是对多边形区域狭小的凸起或凹进部分都可以准确的计算并填充。传统的填充算法在存储数据时需要用到堆栈结构，存在一个点反复多次进入堆栈，造成堆栈的溢出，不适合大型的多边形区域填充。

等间距平行线区域填充算法在计算每条平行线内点的同时绘制子块并完成子块的填充，需要准确的计算出内点的坐标值，所以该算法的区域填充处理分两个主要内容：

(1) 对一个多边形区域绘制一组相互垂直的等间距平行线，计算每条平行线与多边形边界的交点坐标值。

(2) 根据相邻两个内点的坐标，按精度值大小绘制子块。

因此，基于等间距平行线区域填充算法核心的问题在于怎样利用每条平行线内点来绘制子块。在每条平行线上取相邻两个点，以这两点为基点，绘制长度等于精度值且垂直于平行线的线段，然后连接两条线段的端点使其成为一个封闭的方形，即子块，在绘制子块的同时完成填充，从而实现整个多边形区域的填充。

1.1 绘制等间距平行线

(2) 为了能让每条平行线穿过区域内点，约定等间距平行线之间的间距等于栅格数据二维网格大小，这样就可以计算出每条平行线经过内点的行列值，为区域填充提供前提条件，求新坐标系中轮廓点横坐标的最小值和最大值，取轮廓点中横坐标最小值，为等间距平行线的间距(等于网格大小)，首先选定一条平行线开始推算，该平行线与新坐标系轴之间的距离称为值，也就是第一条平行线的横坐标，即

其中，[]为取整符号。

计算平行线与轮廓各条边的交点，如果(–X)(–X+1)<0，则表明有交点[6]，计算交点坐标值，即

计算得到的坐标依次保存在数组中。

(3) 成对读取数组里的坐标值，绘制等间距平行线，计算每条平行线经过内点的个数及相应的行列值，计算如下：

内点个数为

内点坐标分别为

1.2 算法描述

(1) 设置间距值，扫描多边形图形每个顶点的横坐标值，找出最大值和最小值，按式(3)计算第一条平行线的横坐标值。

(2) 根据式(4)计算新的平行线与多边形图形是否有交点，如果没有交点则执行第3步，否则执行第4步。

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

(4) 按照式(4)计算每个交点的坐标值并保存。

(5) 判断的值是否大于的最大值，如果小于则返回第3步，否则直接退出。

(6) 根据式(5)和(6)计算每条平行线所经过的内点个数及其相应的坐标值，对所有内点填充。

1.3 区域填充算法流程图

根据1.2 算法描述绘制出等间距平行线区域填充算法的流程图，如图1所示。

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

1.4 区域填充算法与图形学算法的区别

在计算机图形学中，有许多经典的填充算法，如扫描线填充、边缘填充、边标志填充、边界填充等算法，这些经典的算法各有优势，但也有不足之处，如边缘填充算法对于复杂图形每个像素可能要访问多次，占用过多的存储空间。边界填充算法需要用到堆栈结构，太多的像素压入堆栈，空间需求量大。扫描线算法需要防止多边形区域边界溢出，在进行扫描时，需要检查是否到达边界。区域填充算法与其他经典算法的不同在于，该算法在每生成一条平行线时，判断该条线与多边形是否有交点，如果有则保存交点坐标，如果没有则生成新的平行线，计算简单，运算速度块，不需要堆栈结构，也不需要判断边界。

2 数据验证及算法对比

2.1 数据采集及验证

首先读取多边形区域每个顶点的坐标值，然后从坐标原点开始绘制一组平行于轴的等间距平行线，间距大小根据精度值来设定，最后根据1.1的计算方法求解每条平行线与多边形边界的交点并保存交点的坐标值，计算每条平行线的长度，除以间距，即等于该条平行线所经过的内点个数。根据每个内点的坐标，绘制垂直与平行线垂线，垂直线的距离等于平行线的间距，这样就可以形成子块，如图2所示。

图2 多边形区域的等间距平行线

假设图2所表示的等间距平行线与轴夹角为0，=7，多边形顶点的坐标分别为(125,95)、(155,80)、(175,115)，此时轮廓各点在新坐标和原坐标中的行列值一样，按照计算公式得出等间距平行线与多边形轮廓各条边的交点，实验数据见表1。

表1 等间距平行线与轮廓各条边的交点

根据表1的结果可以得出每一条平行线与轮廓各边的交点，按照1.1算法第3步的计算公式可以计算出每条平行线经过内点个数及相应行列值，实验数据见表2。

2.2 多边形多重嵌套的区域填充

区域填充的过程中经常会遇到多边形嵌套的图形，也就是孤岛，在对孤岛进行区域填充时，往往会分多种情况，如图3所示，有5个相互嵌套的多边形，依次分为1、2、3、4、5。在1区域中嵌套2、3、4、5，而孤岛4、5嵌套在孤岛3中，孤岛3嵌套在孤岛4中。例如，只对1和2的区域进行填充，此时可以根据等间距平行线区域填充算法，分别计算每条平行线与1、2两个多边形区域的交点，图3中从第4条平行线开始与1和2同时有交点，从第35条平行线开始与孤岛2没有交点，孤岛5是整个区域填充，填充时，孤岛5的填充线与1、2区域的平行线是同一组。

表2 计算轮廓内点个数及行列值

在图3中，实现的是最外层和次外层两个相互嵌套的多边形和最内层三角形的内部区域填充，其间的相互联系在于从第17条平行线开始到第23条平行线结束，孤岛5与1、2区域同时经过这7条平行线，在填充时，对1和2区域的嵌套部分进行填充，单独对孤岛5的内部区域进行填充。

图3 任意嵌套的区域填充

2.3 算法对比与复杂度分析

2.3.1 算法对比

常用的多边形区域填充算法有递归种子算法、扫描线填充算法以及一些改进的算法。递归种子填充算法能对具有任意复杂多边形区域进行填充，但该算法存在一个点多次进出堆栈，占用很大的存储空间，仅仅只适用比较小的多边形区域。扫描线填充算法在扫描上具有连贯性，但该算法需要重复判断大量像素点的颜色以及存在不必要的回溯。基于等间距平行线区域填充算法以绘制等间距平行线为基础，计算每条平行线经过的内点，不需要判断内点即不存在一个点多次进出堆栈，占用存储空间小而且具有连贯性，计算简单，实验数据见表3。

2.3.2 算法复杂度分析

计算复杂度包括空间复杂性和时间复杂性[7]。等间距平行线区域填充算法的复杂程度取决于等间距值的大小，值越小，划分的越细小，意味循环次数越大，交点越多，数据量也随着增大，需要填充的子块更多，但精度更好。算法在时间并不明显，但随着交点数量的增大，需要保存的交点的坐标数量就大，以图3为例，间距为7，算法的复杂度见表4。

表3 算法对比

表4 算法复杂度分析

2.3.3 区域填充的自动化和算法适应性

等间距平行线区域填充算法取多边形顶点中横坐标中的最小值作为平行线的初始值开始循环绘制，每循环一次绘制一条平行线，间隔等于设定的精度值，直到最后一条平行线的横坐标大于多边形中横坐标最大值时停止循环，在每次循环绘制平行线的同时再次设定循环条件，依次计算该条平行线与多边形的所有边是否存在交点，如果有则计算并保存交点坐标，否则接着循环，直到该条平行线与每条边都计算过，这就是等间距平行线算法的两重循环原理，完全可以实现填充的自动化。该算法在编写程序时，只需要设定两重循环条件即可，算法简单，有较好的适用性。

2.4 算法技术难点的分析

在使用自主设计的应用程序对等间距平行线区域填充算法进行数据验证的过程中，遇到以下两个关键技术难点，分析如下：

(1) 在相互嵌套的多边形图形中，如何准确从数组中找到平行线同时经过两个嵌套多边形的交点，如图4~5所示。

从图4~5中可看到，图4的数据是外层多边形与平行线的交点坐标，图5的数据是被嵌套的多边形与平行线的交点，在图4~5中带下划线的坐标对有46对，填充时必须上下两部分坐标成对出现，否则填充就会出现混乱。图4的数据中从第9个位置开始与图5的第一个数据成对，相差8。例如，图4中的(65, 31)与图5中的(65, 60)成对，图5中的(65, 5)与图4中的(65, 121)成对，依次类推，两部分有46对坐标是成对的，图4中的数据从第55个开始就不再与图5中的数据存在成对坐标，意味此时平行线和外层多边形有交点，后面的填充只需要图4中的数据坐标成对就可以，例如图4中的(226, 39)与(226, 214)成对、(233, 39)与(233, 162)成对。程序的核心代码如下：

图4 外层多边形与等间距平行线的交点

图5 内层多边形与等间距平行线的交点

for(int i=0;i

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

}

for(int i=z;i

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

i++;

g5.drawLine(kkx[i-z],kky[i-z],tx[i],ty[i]);

}

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

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

(2) 如何准确计算等间距平行线同时经过相互嵌套的多边形的条数。只有先计算出同时经过相互嵌套的多边形的条数，才能准确知道两个多边形从第几个循环填充开始外层与被嵌套的多边形交点成对，否则就是外层多边形坐标自行成对。解决方法为找出被嵌套的多边形横坐标的最小和最大值，最小值除以间距就是第一条同时经过相互嵌套的多边形的平行线，最大值除以间距就是最后一条同时经过相互嵌套的多边形的平行线，每条线有4组坐标，两两成对，实现填充。

第一次同时经过相互嵌套的多边形的线=

[最小值/间距]–1 (7)

最后同时经过相互嵌套的多边形的线=

[最大值/间距)] (8)

3 总 结

计算区域内等间距平行线经过内点的个数及对应的行列值，根据每条平行线相邻两个点分别绘制垂直于平行线的线段，构成一个封闭的子区域，可以快速而准确的确定需要填充的网格子块，为每个子块赋予指定的像素值，不需要重复判断内点和使用堆栈结构，避免了一个点多次堆栈造成溢出的缺陷。等间距平行线填充算法采用计算每条平行线与多边形各条边的交点的方法实现了任意多层嵌套多边形的区域全自动填充和任意复杂区域算法的通用性，能够把任意复杂的多边形区域一次完成全部填充。

[1] 熊胜华, 谢正坚, 何涛. 计算机辅助结构设计与分析的集成框架研究[J]. 图学学报, 2012, 33(4): 129-135.

[2] 任继成, 刘慎权. 区域填充扫描线算法的改进[J]. 计算机辅助设计与图形学学报, 1998, 10(6): 481-486.

[3] 陈优广, 顾国庆, 王玲. 一种基于缝隙码的区域填充算法[J]. 中国图象图形学报, 2007, 12(11): 2086-2092.

[4] 柳稼航, 方涛, 杨建峰. 适用于复杂区域的全自动填充方法[J]. 计算机工程, 2008, 34(4): 238-240.

[5] 唐永勇, 冯剑, 陈国民, 等. 机械制图中CAD教学的软件选择与教学设计[J]. 图学学报, 2014, 35(5): 798-803.

[6] 闫浩文, 杨树文, 孙建国, 等. 计算机地图制图原理与算法基础[M]. 北京: 科学出版社, 2007: 132-134.

[7] 于海燕, 蔡鸿明, 何援军. 图学计算基础[J]. 图学学报, 2013, 34(6): 1-5.

Application of Region Filling Algorithm in Multi Nested Polygon Graph

QIU Guoqing

(Computer College, Minnan Normal University, Zhangzhou Fujian 363000, China)

Region filling algorithm is widely used in drawing, but the arbitrary polygon nested region filling algorithm is very difficult to achieve, in order to solve this problem, puts forward new area filling algorithm that based on equidistant parallel lines. Firstly, draw a set of parallel lines use the same intervals. Secondly, calculation the intersection that all parallel lines with arbitrary nesting the polygon. Finally, use the interval value as a parameter sub block of size, each line contains the parallel calculation of the number of blocks and coordinates and filling, completion of the entire region filling at last. In the process of the experiment, solve the problem of computing in intersection of the nested polygons with the parallel lines is solved. Use multi group data through the application of independent design show that the algorithm can quickly and accurately complete any number of nested polygon area filling and explain the technical difficulties and algorithm complexity which arise in the process of experiment.

equal spaced parallel lines; interior point; multiple nesting; area filling; sub block

TP 399

10.11996/JG.j.2095-302X.2018020357

A

2095-302X(2018)02-0357-05

2017-06-22；

2017-08-03

福建省教育厅中青年教师科研项目(JAT160290)

邱国清(1975–)，男，江西临川人，讲师，硕士。主要研究方向为计算机图形编码。E-mail：qiugq02@163.com