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

摘要：

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

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

所属期刊栏目：38

分类号：TP391.41(计算技术、计算机技术)

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

在线出版日期：2013-01-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：287-290