面向二维Delaunay构网的点定位算法优化  

Point Positioning Algorithm Optimization for Construction of 2D Delaunay Triangle Meshwork

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

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

出　　处：《计算机仿真》2015年第8期306-310,共5页Computer Simulation

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

摘　　要：逐点插入法是构建Delaunay三角网的主要方法之一,而在众多三角形中能否快速找到插入点所在三角形是影响整个逐点插入法构网速度的重要因素。在分析现有点定位算法的基础上,结合三角形重心的几何性质,提出了一种新的点定位算法,简化了待插点位于三角形两条边外侧时的寻找下一三角形的计算步骤,避免了求三角形重心坐标和相交边的过程,并将新算法应用到点云数据地形建模中。实验结果表明,上述算法较目前其它点定位算法能够有效的缩短搜索路径,避免了目前已有算法存在的搜索路径长、搜索路径求解计算量大等问题,较其它算法能提高Delaunay三角网构网过程中点定位的效率,并减少点云数据地形建模时间。As the main way of Delaunay triangulation, the incremental insertion algorithm is seriously influenced by the speed of seeking out the triangle in which the inserting point locates. Based on the analysis of existing point positioning algorithms, a new one with a simplification for the calculation steps when the inserted point located out- ward two edges of current triangle was presented by using geometric properties for triangle barycenter. Using this algo- rithm, the calculation of triangle baryeenter and intersecting edge can be avoided. In addition, the improved algo- rithm was applied to model large scale terrain. The experimental results show that the improved algorithm can shorten the searching path and avoid the problem that searching path is too long and too complicated to calculate in present algorithms, which improve the efficiency of point positioning process, and then reduce the time of Delaunay triangula- tion in terrain modeling.

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

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