点集收集分配的Delaunay三角网快速生成算法及实现

A fast algorithm of Delaunay triangulation generation based on collecting and distributing points

针对目前Delaunay三角网生成算法中定位待插点所在三角形效率不高的问题,本文提出一种基于对待插点集反复收集分配来完成待插入点所属三角形快速定位的方法。经过在数据结构和实现方式上的改进,算法总体平均时间复杂度为O(NlogN)。实验表明,该方法具有实现简单、内存占用较小、运算效率较高等特点。

An algorithm for fast Delaunay triangulation generation was proposed in this paper. To solve the problem that the triangle which contains the given point is inefficient in the present Deiaunay triangulation algorithm, a method of searching for the triangle which contains the given point by repeated collection and distribution of points was proposed. With the improvements in the data structure and realization, the algorithm took O （NlogN） time, where N is the input size. The whole algorithm had such characteristics as simple performance, taking up less memory and efficient operation. The algorithm would have wide applications.