计算机工程 ›› 2012, Vol. 38 ›› Issue (22): 287-290.doi: 10.3969/j.issn.1000-3428.2012.22.072

• 开发研究与设计技术 • 上一篇    下一篇

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

谭云兰 1,2,李光耀2,夏洁武1,李 超2,徐祥龙2   

  1. (1. 井冈山大学电子与信息工程学院,江西 吉安 343009;2. 同济大学电子与信息工程学院,上海 201804)
  • 收稿日期:2012-01-10 修回日期:2012-03-31 出版日期:2012-11-20 发布日期:2012-11-17
  • 作者简介:谭云兰(1972-),女,副教授、博士研究生,主研方向:虚拟现实,科学计算可视化;李光耀,教授、博士生导师;夏洁武,教授;李 超,博士研究生;徐祥龙,硕士研究生
  • 基金项目:
    国家“863”计划基金资助项目(2010AA122200);国家科技支撑计划基金资助项目(2012CBA001);上海市科委国际合作基金资助项目(10510712500)

Efficient Construction of Delaunay Triangulation Network and Terrain Simulation Application

TAN Yun-lan 1,2, LI Guang-yao 2, XIA Jie-wu 1, LI Chao 2, XU Xiang-long 2   

  1. (1. School of Electronics and Information Engineering, Jinggangshan University, Ji’an 343009, China; 2. School of Electronics and Information Engineering, Tongji University, Shanghai 201804, China)
  • Received:2012-01-10 Revised:2012-03-31 Online:2012-11-20 Published:2012-11-17

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

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

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

中图分类号: