Delaunay三角网高效构建及地形仿真应用  

Efficient Construction of Delaunay Triangulation Network and Terrain Simulation Application

作　　者：谭云兰[1,2] 李光耀[2] 夏洁武[1] 李超[2] 徐祥龙[2] 

机构地区：[1]井冈山大学电子与信息工程学院,江西吉安343009 [2]同济大学电子与信息工程学院,上海201804

出　　处：《计算机工程》2012年第22期287-290,共4页Computer Engineering

基　　金：国家"863"计划基金资助项目(2010AA122200);国家科技支撑计划基金资助项目(2012CBA001);上海市科委国际合作基金资助项目(10510712500)

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

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

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]