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

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

孙继忠;胡艳;马永强

【期刊名称】《计算机应用》

【年(卷),期】2010(030)001

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

【关键词】Delaunay三角剖分;Voronoi图;凸壳;计算几何

【作者】孙继忠;胡艳;马永强

【作者单位】西南交通大学,信息科学与技术学院,成都,610031;西南交通大学,理学院,成都,610031;西南交通大学,信息科学与技术学院,成都,610031

【正文语种】中文

【中图分类】TP391.41

【相关文献】

1.一种基于Graham三角剖分生成Delaunay三角网的算法[J], 宋晓宇; 李东; 王永会; 王洪信

2.基于Delaunay三角剖分生成Voronoi图算法 [C], 孙继忠; 胡艳; 马永强