一种快速二维Delaunay三角网点定位算法  

A rapid algorithm for point positioning in 2D delaunay triangulation

作　　者：王雯[1] 吴蔚[1] 苏天赟[2] 

机构地区：[1]中国海洋大学信息科学与工程学院,山东青岛266100 [2]国家海洋局第一海洋研究所,山东青岛266061

出　　处：《测绘工程》2016年第3期25-29,共5页Engineering of Surveying and Mapping

基　　金：国家科技重大专项资助项目(2011ZX05056-001-01);海洋公益性行业科研专项资助项目(201205001)

摘　　要：在构建二维Delaunay三角网的逐点插入法中,定位待插点所在三角形的快慢是影响整个算法构网速度的关键因素。针对目前已有算法存在的搜索路径长、搜索路径求解计算量大等问题,结合三角形重心的几何性质,对点定位算法进行改进,避免求三角形重心和相交边的过程。实验结果表明,文中算法较目前其他点定位算法能够有效地缩短搜索路径,减少点定位的计算时间,提高Delaunay三角网构网过程中点定位的效率。In incremental insertion algorithms of 2D Delaunay triangulation,seeking out the triangle which the inserting point locates in is the key factor influencing the efficiency.In this paper,point positioning algorithm is improved by avoiding the calculation of gravity center and intersecting edge,which makes the use of geometric properties for triangle barycenter to solve the problem that searching path is too long and complicated to calculate in present algorithms.The experimental results show the algorithm in this paper can shorten the searching path and reduce the time of point positioning process,ultimately improve the efficiency of delaunay triangulation compared with other present point positioning algorithms.

关 键 词：DELAUNAY三角网 逐点插入法 点定位算法 三角形重心 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]