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

Research Progress on Delaunay Triangulation Dynamic Updating Algorithm

通过对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.