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

Improved active-edge-table area filling algorithm

作　　者：徐胜攀[1,2] 刘正军[2] 左志权[2] 程耀东[1] 

机构地区：[1]兰州交通大学测绘与地理信息学院,兰州730071 [2]中国测绘科学研究院,北京100830

出　　处：《计算机工程与应用》2014年第17期178-181,共4页Computer Engineering and Applications

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]