一种Delaunay三角网的改进生成算法

An Improved Generation Algorithm of Delaunay Triangulation

Delaunay三角网在地理信息系统等领域有着广泛的应用,通常被用于生成不规则三角网(Triangular Irregular Network,TIN)模型,并被用于描述地表的形态.基于传统的逐点插入法,提出一种改进的Delaunay三角网生成算法,通过合理的数据结构与拓扑关系,建立新生成的三角形之间以及点插入前后三角形之间的联系,优化三角形定位过程.首先通过点集凸包生成若干个初始三角形,然后依次插入各点,新点的三角形定位从前一插入点所在的三角形开始,可大幅缩短三角形定位过程的搜索路径,快速定位到新点所在的三角形,当所有点均插入后,最后对整个三角网进行局部优化.实践表明了该算法的高效性和稳定性.

With its wide use in the field of geographic information systems and other fields,Delaunay triangulation is often adopted to generate the triangular irregular network（ TIN） model and describe the surface patterns.Based on the traditional incremental insertion method,an improved generation algorithm of delaunay triangulation is proposed in this paper. Through reasonable data structure and topological relations,the relationship is established between the newly generated triangles and also between the new and the old triangles,which optimizes the process of triangle localization. Firstly,several initial triangles are generated by the convex hull of point set.Secondly,each point is inserted in turn. The triangle localization of the new point starts from the triangle that contains the last point,which can greatly shorten the search path of the process of triangle localization and quickly locate the triangle of the new point. Finally,after all points are inserted,local optimization of the whole triangulation network is carried out. The efficiency and stability of the algorithm are proved through practice.