一种改进的多边形区域填充算法

卫洪春

摘要：多边形区域填充是图形学和数字图像处理等领域的基本问题。种子填充算法虽然简单，但需要大量栈空间来存储相邻点，容易发生工作栈溢出的情况，在实际填充过程中很难真正发挥作用。该文提出了一种改进的种子填充算法，在堆中实现栈操作，突破了工作栈大小的限制，可处理任意大的填充区域。实验表明，该算法具有较高的运算效率及实用价值，对实际应用有较好的参考作用。

关键词：递归；多边形；种子填充；工作栈

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2016）02-0210-03

1 概述

多边形区域填充是图形学和数字图像处理等领域中计算机应用的一个重要方面。填充算法的优劣直接影响图形显示的速度和精确性。多边形填充一直是计算机图形学研究的热点，常用于CAD/CAM、界面设计、地理信息系统、广告设计、机械制造、阴影、图像处理等领域。

多边形填充算法较多，主要有种子填充法和扫描线填充法。种子填充是从多边形区域的一个内点开始，由内向外用给定颜色画点直到边界为止。若边界指定了某种颜色，则种子填充算法可逐像素处理直到边界色为止。该算法需给出图像数据的区域及区域内的一个点，该算法较适合以人机交互方式进行的图像填充操作。种子填充算法的优点是非常简单，缺点是需要大量栈空间来存储相邻点，且当待填充区域较大时，容易造成栈溢出，从而中止区域填充。本文提出了一种改进的种子填充算法，可以处理任意大的区域填充。

2 简单种子填充算法

简单种子填充算法的核心是递归算法。该方法理论上非常简单、准确，但重复计算较多。种子填充算法有“4连通算法”和“8连通算法”，如图1所示。

以四连通域的填充为例，四连通域从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。四向连通填充算法如下：

a） 种子像素压入栈；

b） 若栈为空，则转e）；否则转c）；

c） 弹出一个像素，并将该像素置成填充色；判断该像素相邻的四连通像素是否为边界色或已经置成多边形的填充色，若不是，则将该像素压入栈；

d） 转b）；

e） 结束。

3 改进的种子填充算法

由于简单种子填充算法存在上述缺点，在实际填充过程中很难真正发挥作用。因为在函数调用过程中，调用函数和被调用函数之间的链接和信息交换需要通过工作栈来完成，而栈是一种容纳数据的容器，数据只能从栈的一端存入（压入栈），同时只能从栈的同一端取出（弹出栈）。运行栈是一段区域的内存空间，运行栈由很多栈帧构成，每个栈帧对应一次函数调用。栈帧的内容包括：本次函数调用的形参值、控制信息、局部变量值及临时数据。函数调用时，将栈帧压入运行栈；返回时则弹出栈帧。由此可见，当函数进行递归调用时，随着递归深度的增加，被压入的栈帧将越来越多，工作栈的可用空间越来越少，直至消耗殆尽。如图3（a）及图3（b）所示。

虽然开发平台可调整运行工作栈的大小，例如，在VC环境下，可通过打开工程，依次操作命令Project->Setting->Link，在Link选项卡的Category 项选择Output，然后在Reserve中设定栈的值。reserve默认值为1MB，最小值为4Byte若将栈空间设为4MB，则将reserve改为0x400000。通过以上操作即可完成工作栈大小的调整。但是调整了工作栈大小后会引来一些其他的问题，如响应时间等。因此这不能解决根本问题。基于上述原因，本文提出了一种将简单种子填充递归算法改进为通过堆栈操作的非递归算法。通过在堆中动态开辟一段空间作为栈空间，则这样的栈空间可以相当大，从而突破了运行工作栈大小的限制，满足了种子填充算法正确运行的要求。在MFC中的测试代码如下：

4 结语

简单种子填充算法需要大量栈空间来存储相邻点，容易造成工作栈的溢出，其实用价值不高。由于堆是很大的自由空间，从而可在堆中动态分配所需空间来实现栈的操作，本文提出的改进的种子填充算法，突破了工作栈大小的限制，可处理任意大的填充区域。实验表明，该算法具有较好的实用价值及较高的运算效率，对实际应用有较好的参考作用。

参考文献：

[1] 王汝传，黄海平，林巧民.计算机图形学教程[M]. 2版.北京：人民邮电出版社，2009.

[2] 和青芳. 计算机图形学原理及算法教程[M].北京：清华大学出版社，2008.

[3] 孙剑，王玉亭. C++中一种高性能动态数组的实现方法[J].现代计算机，2007，（4）：102-104，112.

[4] 苏小红，李东，唐好选，等.计算机图形学实用教程（第3版）[M]. 北京：人民邮电出版社，2014.

[5] 严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社，2015.

[6]张雪彬，刘培国，曹兵.基于C++语言的多维动态数组的实现[J]. 现代电子技术，2006，29（24）：68-69.