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

摘要

In incremental insertion algorithms of 2D Delaunay triangulation ,seeking out the triangle w hich 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 ,w hich 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三角网的逐点插入法中，定位待插点所在三角形的快慢是影响整个算法构网速度的关键因素。针对目前已有算法存在的搜索路径长、搜索路径求解计算量大等问题，结合三角形重心的几何性质，对点定位算法进行改进，避免求三角形重心和相交边的过程。实验结果表明，文中算法较目前其他点定位算法能够有效地缩短搜索路径，减少点定位的计算时间，提高Delaunay三角网构网过程中点定位的效率。