Abstract: An efficient algorithm of constructing Delaunay triangulation network based on discrete point set is presented. A large scale data points are pre-processed by sorting with blocks, which makes the next inserting point closely neighboring the newly inserting one, so the algorithm is in accord with the space related theory. When it comes to predicate the location of the next inserting point in which triangles is very time-consuming, it adopts an efficient and robust blending algorithm of the shortest path location including locating the between the point and the triangle by calculating the acreage of triangle and combining the center of gravity of triangle with the relationship between the directed line segment and the point. Consequently, the search numbers of the triangles are decreased and the location of triangles is low time-consuming. While optimizing the local Delaunay triangulation network, it stores all the adjusted edges and vertices by Delaunay Quadtree, which can search effectively. Experimental result proves that applying the algorithm into the 3D terrain simulation makes good natural looking, and the time complexity of whole algorithm is low.

Key words: Delaunay triangle network, Digital Elevation Model(DEM), Local Optimization Procedure(LOP), 3D terrain simulation, Flip operation, incremental generation algorithm

摘要： 针对基于离散点的Delaunay三角网构建过程中待插入点的定位耗时问题，提出Delaunay三角网高效构建算法，并将其用于三维地形仿真应用中。对大量数据点进行分块排序预处理后，运用空间自相关理论使下一个待插入点总是紧邻新近插入点，融合最短路径定位算法和三角形面积法，结合三角形重心与点、有向线段的关系遍历三角形，减少遍历时间。在对三角网进行LOP局部优化时，采用Delaunay四叉树保存待调整的所有边的节点信息，提高遍历效率。实验结果证明，该算法构建的三维地表真实感较强，并且具有较低的时间复杂度。

关键词: Delaunay三角网, 数字高程模型, 局部优化过程, 3D地形仿真, Flip操作, 增量生成算法

CLC Number: 

• TP391.41