快速构建Delaunay三角网算法研究

Study on an algorithm for fast constructing Delaunay triangulation

研究一种快速构建 Delaunay三角网的算法 ,该算法结合逐点插入算法和分治算法 ,具有建网速度快、耗费空间小的优点。采用多级自适应网格划分点集 ,对叶子网格内的点采用改进了的逐点插入算法生成子三角网 ,子三角网间利用分治算法的思想进行合并。经实践验证 ,算法复杂度与点数几乎成线性关系。

In this paper , an algorithm for fast constructing Delaunay triangulation is presented. This algorithm takes the advantages of incremental insertion algorithm and divide conquer, and has the advantages of high efficiency and small space. It divides the points set by adaptive grid and constructs the sub triangulation by improved incremental insertion algorithm for the points in leaf grids. After that, it merges sub triangulations by the thought of divide conquer. The time complexity of the algorithm is about linear to the number of points set which has been verified by its successful experiment.