多边形图形的环状扫描线种子填充算法

邱国清

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

多边形图形的环状扫描线种子填充算法

邱国清

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

递归种子填充算法在对多边形区域填充时存在一个点多次进出堆栈且占用大量存储空间，只适合于细小区域填充.为此，基于Morton码原理提出一种改进算法.首先，将填充胚的行列值转换成十进制Morton码，其次将每个填充胚的值与堆栈中的种子点Morton码一一匹配，避免堆栈中出现重复点，最后采用环状扫描线方式按顺时针或逆时针方向对多边形区域进行扫描填充.经过实验数据验证，改进算法能节省较多的存储空间，避免一个点反复多次进出堆栈.

Morton码；环状扫描线；递归种子算法；堆栈；填充胚

0 引言

区域填充算法是指给出一个区域的边界，在边界范围内对所有像素单元赋予指定的颜色代码［1］，传统的种子填充算法，无论是简单种子填充算法还是扫描线种子填充算法，总免不了要将已经填充过的像素点进行再次或多次重复判断［2］，这会占用非常大的存储空间和堆栈的溢出.种子填充算法是利用栈结构的搜索算法［3］，改进后的递归种子填充算法对原算法中的堆栈结构进行合理的修改，在保存种子点的行列值的同时也保留行列值所对应的十进制Morton编码［4］，对于每一个种子点只有唯一的编码，当新的种子点进入堆栈，先将行列值转换成相应的编码，再搜索堆栈，检索是否存在相同的编码，避免一个点多次反复进入.改进后的算法采用环状扫描线的方式依顺时针或逆时针进行扫描填充，如图1所示，优点在于能完整地搜索到区域内每个内点，算法容易实现，同时十进制Morton编码可以确保每个内点都有唯一的编码值，有利于比较，避免出现同一个点多次进出堆栈.

1 递归种子填充改进算法

1.1 基本思路

每次找到一个新的填充胚时，将填充胚放入堆栈，同时记录该填充胚的行列值并一起压入堆栈，当再次找到新的填充胚时，进入堆栈前先搜索匹配是否存在与该填充胚具有相同行列值的填充胚，如存在则该填充胚不再重复进入堆栈，否则压入堆栈，这样避免一个点重复进入堆栈，避免堆栈溢出.同时为了节省存储空间，在连续经过两次填充胚填充后，堆栈中仅需保留连续两次循环产生的填充胚和对应的行列值，之前循环产生的填充胚可以删除，例如，当填充胚完成第3次扩散与填充后，只保留第2次和第3次循环产生的填充胚，第1次循环产生的填充胚对应的行列值可以全部删除，以此类推，堆栈中始终保留最近连续两次循环产生的填充胚及对应行列值，这样就可以极大节省存储空间.

图1 环状扫描线示意图

1.2 递归种子填充改进算法的具体步骤

从当前点检测相邻像素有4连同和8连同两种方法【5】.改进的递归种子填充算法以4连同为例.

第1步，从给定的种子填充胚出发，向上、下、左、右4个方向中任意选定一个且按顺时针或逆时针环状扫描进行扩散与填充，当4个方向都被填充一次则表明第一次填充胚扩散填充完成，然后将种子点及行列值和新得到的填充胚及行列值转换成十进制的Morton编码放入堆栈中，同时将边界点的行列值也转换成十进制的Morton编码放入堆栈但边界点不能作为填充胚.

第2步，将新得到的填充胚依次出栈，按第1步的方法进行环状扫描扩散与填充，得到新的填充胚在入栈前，先搜索堆栈中已经存在的填充胚行列值进行匹配，如果匹配成功，说明该填充胚已存在，不要再重复进入，否则放入堆栈，同时还要和边界点行列值匹配，防止边界溢出.所谓区域的边界点，就是无论将它的邻域取得多小，它都包含有集合的内点和外点［6］.

第3步，将每次环状扫描循环产生新的填充胚行列值放入栈中，只保留最近连续两次循环产生的填充胚，删除之前所有的填充胚，不包含边界点，以节省存储空间.

第4步，当栈非空时，转到第一步，否则算法结束.

1.3 改进算法的流程图

改进算法流程图如图2所示.

图2 改进算法流程图

2 栅格的行列值与十进制Morton编码的转换

先将行与列的值转换为二进制数据，再将二进制的行与列的每一位依次交叉排列，从而产生新的二进制数据，最后将二进制数据转换成十进制数值，即得到Morton编码，例如，第5行第3列的栅格单元，行与列转换为二进制后分别为：101和011，交叉排列生成新的二进制为100111，转换成十进制为39，即Morton编码，如图3所示.

图3 行列值与Morton编码的转换

图4 边界点与填充胚

3 数据验证

3.1 多边形区域填充

图4表示一个多边形区域，属性等于1的点为区域范围线上的像元，属性为2的是填充胚.

填充前，首先把边界点对应的行列值转换成相应的Morton码保存在堆栈中，用来检测填充胚是否溢出.图1中的种子填充胚的行列值为7行6列，对应的二进制分别为0111，0110，按位交叉排列后得到新的二进制数为00111110，转换成十进制Morton码为62，以种子填充胚为中心，采用四邻法从种子填充胚顶部开始按顺时针方向进行搜索与填充，得到4个新的填充胚，它们对应的行列值分别是8行6列、7行7列、6行6列和7行5列，转换成相应的十进制Morton码分别是148、63、60、59，在进入堆栈前先搜索堆栈中的边界点和填充胚的编码值，检查是否存在边界溢出和重复的点，将4个新的填充胚放入堆栈，这样第1次循环填充结束，开始第2次循环填充，编码为148的点开始以同样的方法填充，得到新的填充胚行列值分别是9行6列、8行7列、7行6列、8行5列，转换成十进制Morton码分别是150、149、62、145，在进入堆栈前先和边界点堆栈中第1次循环产生的填充胚进行匹配，其中7行6列的编码为62的点已经存在于堆栈中，所以不能再重复进入，其他3个新的填充胚进入堆栈.其次以编码为63的点开始搜索填充，得到的填充胚对应的十进制Morton码是149、106、61、62，和堆栈中的边界点和其他填充胚进行一一匹配后得出，编码62、149已经存在不能再重复进入.再次以编码为60的点为中心开始填充，得到的十进制Morton码分别为62、61、64、57，进行匹配后可以看到编码61和编码62已经存在不能重复进入.最后以编码59为中心进行填充，得到十进制Morton码为145、62、57、58，进行匹配后看到编码62、57、145已经存在不能再进入，第2次循环填充结束，堆栈中的填充胚为编码62、148、63、60、59、150、147、145、106、61、54、57、58在内的12个点，其中种子填充胚在进行2次循环填充后已经不可能需要再次出栈填充，所以可以从堆栈中删除，以节省存储空间.同样的方法，开始第3次循环填充，得到新的填充胚在经过与堆栈中的边界点和其他已经存在的点匹配后可以进入堆栈，当第3次循环填充结束后，应当及时删除第1次循环产生的填充胚，始终只保留连续两轮循环填充产生的填充胚，及时释放出堆栈空间.在循环填充时，要防止堆栈溢出.

3.2 算法评价

由表1可知：1）将多边形图形中的栅格点所对应的行列值转换成十进制Morton编码，可以保证唯一性，避免同一个点多次反复进出堆栈.2）对于复杂大型的多边形图形，需要填充的点繁多且存在许多狭窄区域，改进后的算法以环状扫描方式进行填充，能很轻松填充满整个多边形，这些是种子填充算法无法实现的.3）环状扫描线遇到边界点的时候，不会再将该点作为种子点存入堆栈.4）随着环状扫描循环次数的增大，每次扫描得到的点成倍增加，填充效率非常好.

4 总结

基于递归种子填充算法采用十进制Morton编码和环状扫描线方法提出一种新的改进算法，从数据验证的结果可以看出，改进后的算法占用极少的堆栈空间，避免一个点多次反复进入堆栈，做到一个填充胚只检索一次，即节约时间也节省存储空间，该算法适合填充比较大的多边形图形.

［1］闫浩文，杨树文，孙建国，等.计算机地图制图原理与算法基础［M］.北京：科学出版社，2007：216-217.

［2］张正峰，马少飞，李玮.新的种子点区域填充算法［J］.计算机工程与应用，2009，45（6）：201.

［3］马治平.一种区域填充算法［J］.计算机应用与软件，2004，21（4）：84-85.

［4］聂庆华.地理信息系统及其在环境科学中的应用［M］.北京：高等教育出版社，2006：171-175.

［5］秦晓嶶.区域填充算法的研究［J］.赤峰学院学报（自然科学版），2011，27（6）：47-49.

［6］邓国强，孙景鳌，蔡安妮，等.一种基于曲线积分的区域填充算法［J］.北京邮电大学学报，2001，24（2）：87-91.

The Seed Filling Algorithm for Circular Scan Lines of Polygon

QIU Guoqing
（College of Computer,Minnan Normal University，363000，Fujian，Zhangzhou，China）

Recursive seed filling algorithm on ploygon filling when there is a multiple import and stack occupies a lot of storage space，only suitable for small area filling.Therefore，based on the Morton code principle and proposes an improved algorithm.First，the filling embryo value into the rank of hexadecimal Morton code.Second，fill each embryo one by one in orde to avoid duplication of point stack.Last，use the circular scan line in clockwise or counterclockwise direction of polygon scan fill.A lot of experiment date show，the new algorithm can save more storage space than old way and avoid one point repeated import stack.

Morton code；circular scan line;recursive seed algorithm;stack；filling embryo

TP 399

A

2095-0691（2017）01-0064-04

表1 根据图1计算出的数据

循环次数1 2 3 4 5存储空间4个字节8个字节11个字节15个字节20个字节新得到点的坐标(x,y) (8,6)(7,7)(6,6)(7,5) (9,6)(8,7)(8,5)(7,8)(6,7)(5,6)(6,5)(7,4) (10,6)(9,7)(9,5)(8,8)(8,4)(7,9)(6,8)(5,7) (4,5)(6,4)(7,3) (11,6)(10,7)(10,5)(9,8)(9,4)(8,9)(8,3) (7,10)(6,9)(5,8)(4,7)(5,4)(6,3)(7,2) (12,6)(11,7)(11,5)(10,4)(10,8)(9,9)(9,3) (10,9)(9,10)(7,11)(6,10)(5,9)(4,8)(3,7) (4,6)(6,4)(5,5)(4,4)(5,3)(7,1)十进制Morton值148、63、60、59 150、147、145、106、61、54、57、58 140、151、147、192 144、117、104、55 49、56、47 158、157、153、194 134、193、133、110 105、98、53、50、45、46 180、159、155、152 199、195、135、201 198、111、108、99 96、31、52、56、51、48、39、43

2016-11-25

福建省教育厅科研项目（JAT160290）

邱国清（1975- ），男，江西临川人，讲师，硕士，研究方向：图形编码处理.