| Delaunay三角网建立的改进算法 |
| |
| 引用本文： | 徐道柱,刘海砚.Delaunay三角网建立的改进算法[J].测绘与空间地理信息,2007,30(1):38-41. |
| |
| 作者姓名： | 徐道柱 刘海砚 |
| |
| 作者单位： | 信息工程大学,测绘学院,河南,郑州,450052 |
| |
| 摘 要： | 本文深入研究了Delaunay三角网建立算法中的逐点插入法,详细介绍了算法的实现步骤,分析了其中影响算法效率的关键环节,并采用数据点集分块管理、三角形快速定位、改变点插入顺序等方法进行了算法优化,对三角形快速定位方法进行了改进。测试实验的结果说明,算法改进后Delaunay三角网建立的效率提高了4~6倍。
|
| 关 键 词： | Delaunay三角网 逐点插入法 三角形快速定位 |
| 文章编号： | 1672-5867(2007)01-0038-04 |
| 修稿时间： | 2006年7月11日 |
An Improved Algorithm for Creation of Delaunay Triangulation |
| |
| XU Dao-zhu,LIU Hai-yan.An Improved Algorithm for Creation of Delaunay Triangulation[J].Geomatics & Spatial Information Technology,2007,30(1):38-41. |
| |
| Authors: | XU Dao-zhu LIU Hai-yan |
| |
| Abstract: | This paper studied incremental insertion algorithm,which is one of the methods of Delaunay triangulation,analyzed the key steps which affect the efficiency of algorithm mostly of all the steps of the algorithm.The point set is organized by constructing grid index,together with recompose the insertion order of the points and the algorithm for fast location of the triangle that contain the given point,the efficiency of algorithm is greatly improved.Tested by actual map data,it shows that the improved algorithm could improve the efficiency so much as four to six times. |
| |
| Keywords: | Delaunay triangulation incremental insertion algorithm fast location of the triangle |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
