标题:一种改进的Voronoi图增量构造算法
作者:孟雷;张俊伟;王筱婷;杨承磊;
作者机构:[孟雷;张俊伟;王筱婷;杨承磊]山东大学计算机科学与技术学院
来源:中国图象图形学报
出版年:2010
期:06
页码:978-984
关键词:Voronoi图;Delaunay三角化;增量法;扫描线法;右凸链
摘要:Voronoi图是计算几何中的一种重要几何结构,也是计算几何的重要研究内容之一,如今已经在图形学、地理信息系统、机械工程、机器人等领域得到广泛应用。增量法是最常用的构造Voronoi图的方法,但一般实现方法中点的定位时间比较长。扫描线算法可以视为一种特殊的增量法,时间复杂度为O(nlogn),但需要构造比较复杂的数据结构。为了更有效地构建Voronoi图,提出了一种改进的Voronoi图增量构造算法,该算法是通过对已有的生成Voronoi图的增量法进行分析,并结合它们的优点,采用扫描线的方式,通过右凸链的结构来定位新插入的点,实现了Voronoi图的逐步构造。和扫描线算法类似,其时间复杂度为O...
资源类型:期刊论文
原文链接:http://kns.cnki.net/kns/detail/detail.aspx?FileName=ZGTB201006021&DbName=CJFQ2010
TOP