| 点集收集分配的Delaunay三角网快速生成算法及实现 |
| |
| 引用本文： | 袁正午,侯林,彭军还.点集收集分配的Delaunay三角网快速生成算法及实现[J].测绘科学,2011,36(5):223-225. |
| |
| 作者姓名： | 袁正午 侯林 彭军还 |
| |
| 作者单位： | 1. 重庆邮电大学中韩合作GIS研究所,重庆,400065
2. 中国地质大学,北京,100871 |
| |
| 基金项目： | 国家高技术研究发展计划“863计划”(2007AA12Z226) |
| |
| 摘 要： | 针对目前Delaunay三角网生成算法中定位待插点所在三角形效率不高的问题,本文提出一种基于对待插点集反复收集分配来完成待插入点所属三角形快速定位的方法.经过在数据结构和实现方式上的改进,算法总体平均时间复杂度为O(NlogN).实验表明,该方法具有实现简单、内存占用较小、运算效率较高等特点.
|
| 关 键 词： | 数字地形模型 Delaunay三角网 Bowyer-Watson算法 存储结构 |
A fast algorithm of Delaunay triangulation generation based on collecting and distributing points |
| |
| YUAN Zheng-wu,HOU Lin,PENG Jun-huan.A fast algorithm of Delaunay triangulation generation based on collecting and distributing points[J].Science of Surveying and Mapping,2011,36(5):223-225. |
| |
| Authors: | YUAN Zheng-wu HOU Lin PENG Jun-huan |
| |
| Institution: | ②(①Sino-Korea GIS Research Center,Chongqing University of Posts and Telecommunications,Chongqing 400065,China;②China University of Geosciences,Beijing 100871,China) |
| |
| Abstract: | An algorithm for fast Delaunay triangulation generation was proposed in this paper.To solve the problem that the triangle which contains the given point is inefficient in the present Delaunay triangulation algorithm,a method of searching for the triangle which contains the given point by repeated collection and distribution of points was proposed.With the improvements in the data structure and realization,the algorithm took O(NlogN) time,where N is the input size.The whole algorithm had such characteristics... |
| |
| Keywords: | Digital Terrain Model Delaunay triangulation Bowyer-Watson algorithm storage structure |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
