测绘通报 ›› 2014, Vol. 0 ›› Issue (6): 51-54.doi: 10.13474/j.cnki.11-2246.2014.0190

• 学术研究 • 上一篇    下一篇

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

余代俊1,蒲朝旭1,朱逍贤2   

  1. 1. 成都理工大学 现代工程测量技术及应用研究所;2. 四川科技职业学院 土木与建筑工程学院
  • 收稿日期:2014-01-23 出版日期:2014-06-25 发布日期:2014-06-25
  • 通讯作者: 蒲朝旭 E-mail:pcx@foxmail.com

An Improvement Algorithm for Delaunay Triangulation

  • Received:2014-01-23 Online:2014-06-25 Published:2014-06-25

摘要:

Delaunay三角网的构建算法和设计在GIS分析管理以及可视化等方面有着重要的作用。本文将逐点插入法和凸包法进行融合,利用Akl-Toussaint启发式函数来剔除原始数据点集中的多余点以便快速高效的实现凸包的构建,利用角度判别对角线法来对生成的初始三角网进行优化,在此基础之上提出了生成Delaunay三角网的改进算法。实践表明,该算法对于小量或大量数据集均有较好的适应性,不仅具有与分治算法一致的高效性,还具有易于理解和实现的算法思路。

关键词: 凸包, Delaunay, 逐点插入法, TIN, LOP