Delaunay三角网动态更新算法的研究进展  

Research Progress on Delaunay Triangulation Dynamic Updating Algorithm

作　　者：李娜[1] 

机构地区：[1]福州大学福建省空间信息工程研究中心,福州350002

出　　处：《计算机系统应用》2015年第2期14-21,共8页Computer Systems & Applications

基　　金：福建省科技计划重点项目(2014Y0032)

摘　　要：通过对Delaunay三角网动态更新算法进行研究,综述了Delaunay三角网中插入和删除点、约束线算法以往研究.详细介绍点定位、LOP优化、对角线交换等关键技术的研究进展,并对比各种方法的优缺点,分析已解决的问题和仍存在的问题.最后对更新算法研究不足之处进行总结,并提出若干可能的研究方向.Based on the study of delaunay triangulation dynamic updating algorithm, this paper reviews the earlier researches about inserting points and constrained edges into an existed Delaunay Triangulation, or deleting points and constrained edges from the Delaunay Triangulation. This paper describes a series of key techniques in detail, such as point location, LOP principle, diagonal exchanging etc., and also compares the advantages and disadvantages of these algorithms, furthermore analyses the solved problems and existing problems. Finally the problems existing in the delaunay triangulation dynamic updating algorithms are summarized, and some suggestions about future work are orooosed in the end.

关 键 词：DELAUNAY三角网 动态更新 点插入 约束线插入 点删除 约束线删除 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]