%0 Journal Article
%T 基于delaunay三角剖分生成voronoi图算法
%A 孙继忠
%A 胡艳
%A 马永强
%J 计算机应用
%D 2010
%X ？针对delaunay三角网生长算法和间接生成voronoi图算法构网效率不高的问题，提出了一种delaunay三角网生长法间接生成voronoi图的改进算法。该算法以点集凸壳上一边快速生成种子三角形，定义了半封闭边界点的概念，在三角形扩展过程中动态删除封闭点及半封闭边界点，加快delaunay三角网生成速度。然后又定义了有序目标三角形的概念，该算法能迅速查找点的有序目标三角形，生成无射线的voronoi图；考虑凸壳上点的特性，借助三个无穷点生成带射线的voronoi图。通过实验结果分析表明，改进的算法执行效率有了很大提高。
%K delaunay三角剖分
%K voronoi图
%K 计算几何
%K 凸壳
%U http://www.joca.cn/CN/abstract/abstract12538.shtml