一种改进的快速Delaunay三角剖分算法

作者：何俊; 戴浩; 谢永强; 刘宝生

来源：系统仿真学报, 2006, (11): 3055-3057.

• 数字高程模型
• Delaunay三角剖分
• 数据分块
• 三角网生长算法 DEM
• Delaunay triangulation
• data set partition
• triangulation growth algorithm

Delaunay三角剖分算法是构建数字高程模型(DEM)的主要算法。分析了几种已有Delaunay三角剖分算法后,对前沿边推进算法进行了两点改进。一是直接以边为基础向一侧推进,而不是以凸包为基础向内推进;二是利用分块技术来改进搜索方法,使搜索范围限制在搜索边的周围区域,从而极大地提高了Delaunay三角网的推进速度。仿真实验表明,改进后算法效率有了显著提高。

• 单位
  中国人民解放军陆军工程大学; 中国人民解放军国防科学技术大学