徐胜攀，刘正军，左志权，程耀东

1.兰州交通大学测绘与地理信息学院，兰州 730071

2.中国测绘科学研究院，北京 100830

一种改进的活性边表区域填充算法

徐胜攀1，2，刘正军2，左志权2，程耀东1

1.兰州交通大学测绘与地理信息学院，兰州 730071

2.中国测绘科学研究院，北京 100830

为提高区域填充效率，对三种常见的区域填充算法进行了介绍和分析，并对其中优势较为明显的活性边表区域填充算法进行了进一步改进。改进算法针对原始算法的不足，充分利用多边形顶点信息，建立了活性边动态发现机制，使得算法时间效率和空间效率都得到提高；同时，为填充自相交多边形，又提出一种简单有效的基于扫描线的多边形自相交点探测方法，使得算法的适用性得到进一步增强。实验结果表明，算法的改进取得了很好的效果。

区域填充；活性边表；动态发现机制；自相交

1 引言

区域填充是指用一种颜色或图案来填充一个二维区域[1]，它是计算机图形学和数字图像处理领域的一个基本操作[2-3]，也是计算机应用的一个重要方面，在计算机辅助设计、真实感图形显示、动画、图像处理等实际领域中有着广泛的应用[4-5]。填充算法的优劣直接影响着图形显示的速度和精确性。

常见的区域填充算法主要有边标识算法、种子填充算法和活性边表算法[6-7]。边标识算法[1，6]是基于像素的填充算法，填充过程中需要不断地读取像素，以确定是否到达边界，效率较低，目前应用并不多。种子填充是研究较为活跃的算法，分为经典的种子填充算法和基于扫描线的种子填充算法[7-8]，目前后者已出现了许多改进算法[3，9-10]。……