基于Delaunay三角剖分生成Voronoi图算法

作     者：孙继忠 胡艳 马永强 SUN Ji-zhong;HU Yan;MA Yong-qiang

作者机构：西南交通大学信息科学与技术学院成都610031 西南交通大学理学院成都610031 

出 版 物：《计算机应用》 (journal of Computer Applications)

年 卷 期：2010年第30卷第1期

页      面：75-77,97页

核心收录：

学科分类：08[工学] 080203[工学-机械设计及理论] 0802[工学-机械工程] 

主　　题：Delaunay三角剖分 Voronoi图 凸壳 计算几何 

摘      要：针对Delaunay三角网生长算法和间接生成Voronoi图算法构网效率不高的问题,提出了一种Delaunay三角网生长法间接生成Voronoi图的改进算法。该算法以点集凸壳上一边快速生成种子三角形,定义了半封闭边界点的概念,在三角形扩展过程中动态删除封闭点及半封闭边界点,加快Delaunay三角网生成速度。然后又定义了有序目标三角形的概念,该算法能迅速查找点的有序目标三角形,生成无射线的Voronoi图;考虑凸壳上点的特性,借助三个无穷点生成带射线的Voronoi图。通过实验结果分析表明,改进的算法执行效率有了很大提高。