首页 | 本学科首页   官方微博 | 高级检索  
     

一种改进的Voronoi图增量构造算法
引用本文:孟 雷,张俊伟,王筱婷,杨承磊.一种改进的Voronoi图增量构造算法[J].中国图象图形学报,2010,15(6):978-984.
作者姓名:孟 雷  张俊伟  王筱婷  杨承磊
作者单位:(山东大学计算机科学与技术学院, 济南 250101)
基金项目:国家自然科学基金项目(60703028,60573181)
摘    要:Voronoi图是计算几何中的一种重要几何结构,也是计算几何的重要研究内容之一,如今已经在图形学、地理信息系统、机械工程、机器人等领域得到广泛应用。增量法是最常用的构造Voronoi图的方法,但一般实现方法中点的定位时间比较长。扫描线算法可以视为一种特殊的增量法,时间复杂度为O(nlog n),但需要构造比较复杂的数据结构。为了更有效地构建Voronoi图,提出了一种改进的Voronoi图增量构造算法,该算法是通过对已有的生成Voronoi图的增量法进行分析,并结合它们的优点,采用扫描线的方式,通过右凸链的结构来定位新插入的点,实现了Voronoi图的逐步构造。和扫描线算法类似,其时间复杂度为O(nlog n),但算法更简洁,且便于理解和编程实现。

关 键 词:Voronoi图  Delaunay三角化  增量法  扫描线法  右凸链
收稿时间:7/1/2009 12:00:00 AM
修稿时间:2009/10/30 0:00:00

An Improved Incremental Algorithm for Voronoi Diagram
MENG Lei,ZHANG Junwei,WANG Xiaoting and YANG Chenglei.An Improved Incremental Algorithm for Voronoi Diagram[J].Journal of Image and Graphics,2010,15(6):978-984.
Authors:MENG Lei  ZHANG Junwei  WANG Xiaoting and YANG Chenglei
Abstract:
Keywords:
本文献已被 万方数据 等数据库收录!
点击此处可从《中国图象图形学报》浏览原始摘要信息
点击此处可从《中国图象图形学报》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号