| 一种快速二维 Delaunay 三角网点定位算法 |
| |
| 引用本文： | 王雯,吴蔚,苏天赟.一种快速二维 Delaunay 三角网点定位算法[J].测绘工程,2016,25(3):25-29. |
| |
| 作者姓名： | 王雯 吴蔚 苏天赟 |
| |
| 作者单位： | 中国海洋大学 信息科学与工程学院,山东 青岛,266100;国家海洋局第一海洋研究所,山东 青岛,266061 |
| |
| 基金项目： | 国家科技重大专项资助项目(2011ZX05056-001-01)；海洋公益性行业科研专项资助项目(201205001) |
| |
| 摘 要： | 在构建二维Delaunay三角网的逐点插入法中,定位待插点所在三角形的快慢是影响整个算法构网速度的关键因素。针对目前已有算法存在的搜索路径长、搜索路径求解计算量大等问题,结合三角形重心的几何性质,对点定位算法进行改进,避免求三角形重心和相交边的过程。实验结果表明,文中算法较目前其他点定位算法能够有效地缩短搜索路径,减少点定位的计算时间,提高Delaunay三角网构网过程中点定位的效率。
|
| 关 键 词： | Delaunay三角网 逐点插入法 点定位算法 三角形重心 |
A rapid algorithm for point positioning in 2D delaunay triangulation |
| |
| WANG Wen,WU Wei,SU Tianyun.A rapid algorithm for point positioning in 2D delaunay triangulation[J].Engineering of Surveying and Mapping,2016,25(3):25-29. |
| |
| Authors: | WANG Wen WU Wei SU Tianyun |
| |
| Abstract: | 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 . |
| |
| Keywords: | delaunay triangulation incremental insertion algorithm point positioning algorithm triangle barycenter |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
