以优先点为中心的Delaunay三角网生长算法

目的 Delaunay三角网具备的优良性质使其得到广泛的应用,构建Delaunay三角网是计算几何的基础问题之一,为了高效、准确地构建大规模点集的Delaunay三角网,提出一种基于优先点的改进三角网生长算法.方法 算法以逆时针次序的一条凸包边为初始基边,使用基边对角最大化并按照逆时针次序选定第3点构建一个Delaunay三角形,通过待扩展边列表中的数据判断新生成的两条边是否需要扩展,采用先进先出的方式从待扩展边列表中取边作为基边,以优先点为中心构建局部Delaunay三角网使优先点尽快成为封闭点,再从点集中删除此封闭点.结果 对于同一测试点集,改进算法运行时间与经典算法运行时间的比率不超过1/3,且此比率随点集规模增长逐步下降.相比经典算法,改进算法在时间效率上有较大提升.结论 本文改进算法对点集规模具有较好的自适应性与较高的构网效率,可用于大规模场景下Delaunay三角网的构建.

Growth algorithm centered on priority point for constructing the Delaunay triangulation

Objective The Delaunay triangulation is a fundamental problem in the field of computational geometry. It is widely used because of its excellent characteristics. To construct a Delaunay triangulation network efficiently and accurately on a large-scale point set, an improved Delaunay triangulation algorithm based on priority point is presented in this paper. Method An initial base edge is selected from the convex hull edges in anticlockwise order. A Delaunay triangle is constructed by base edge and the third point in the anticlockwise order, which maximizes the angle opposite the base edge. Whether the generated two edges need to be expanded is determined by the array of the needed expanded edges. The first-in-first-out strategy is used to extract the base edge from the array of the needed expanded edges. The local Delaunay triangulation is constructed around the priority point and accelerates the priority point to become a closed-point. Then, the closed-point is removed. Result The running time ratio of improved algorithm to classical algorithm is less than a third when using the same point set, and the ratio gradually decreases with increasing point set scale. Compared with the classical algorithm, the improved algorithm has significant enhancement in time efficiency. Conclusion The improved algorithm has better adaptability for point set scale and high efficiency for constructing Delaunay triangulation. It can also be used for large-scale point set Delaunay triangulation.