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

计算机工程与应用 ›› 2014, Vol. 50 ›› Issue (17): 178-181.

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

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

1.兰州交通大学测绘与地理信息学院，兰州 730071
2.中国测绘科学研究院，北京 100830

出版日期:2014-09-01 发布日期:2014-09-12

Improved active-edge-table area filling algorithm

XU Shengpan1，2, LIU Zhengjun2, ZUO Zhiquan2, CHENG Yaodong1

1.Faculty of Geomatics, Lanzhou Jiaotong University, Lanzhou 730071, China
2.Chinese Academy of Surveying & Mapping, Beijing 100830, China

Online:2014-09-01 Published:2014-09-12

摘要/Abstract

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

关键词: 区域填充, 性边表, 动态发现机制, 自相交

Abstract: To improve the efficiency of area filling, the paper makes an introduction and analysis for the three common area filling algorithms and further improves the active-edge-table algorithm which has more obvious advantages compared with the others. For the deficiency of traditional algorithm, the improved algorithm makes full use of vertex information and establishes the dynamic discovery mechanism of active edges, making the time efficiency and space efficiency both improved; meanwhile, in order to fill the self-intersected polygons, an easy and effective method to detect self-intersected vertices based on scan line is proposed, making the adaptability of the algorithm enhanced. Experimental results demonstrate that the improved algorithm achieves very good results.

Key words: area-filling, active-edge-table, dynamic discovery mechanism, self-intersection

徐胜攀1，2，刘正军2，左志权2，程耀东1. 一种改进的活性边表区域填充算法[J]. 计算机工程与应用, 2014, 50(17): 178-181.

XU Shengpan1，2, LIU Zhengjun2, ZUO Zhiquan2, CHENG Yaodong1. Improved active-edge-table area filling algorithm[J]. Computer Engineering and Applications, 2014, 50(17): 178-181.

[1]	王杰雄，陈国栋，陈怡. 改进的B-Snake模型肝脏CT图像分割算法[J]. 计算机工程与应用, 2015, 51(9): 152-157.
[2]	徐旭1，2，刘伟1. 线目标缓冲区生成的矢栅混合算法研究[J]. 计算机工程与应用, 2014, 50(4): 152-156.
[3]	张申华，祝轩，雷文娟，王蕾. 一种改进的基于样例的目标物体移除方法[J]. 计算机工程与应用, 2011, 47(7): 180-182.
[4]	张正峰,马少飞,李玮. 新的种子点区域填充算法[J]. 计算机工程与应用, 2009, 45(6): 201-202.
[5]	陈玉国¹,李治隆²,刘秀平²,王丰敏². 复杂矢量图中矩形域填充的快速定位方法[J]. 计算机工程与应用, 2009, 45(12): 229-232.
[6]	胡炜炜李树广吴舟舟. 序列图像的自适应背景提取及车型分类[J]. 计算机工程与应用, 2007, 43(12): 239-242.