| 大量约束边条件下Delaunay三角网的快速生成 |
| |
| 引用本文： | 徐道柱,刘海砚.大量约束边条件下Delaunay三角网的快速生成[J].测绘工程,2007,16(3):6-10. |
| |
| 作者姓名： | 徐道柱 刘海砚 |
| |
| 作者单位： | 信息工程大学,测绘学院,河南,郑州,450052;信息工程大学,测绘学院,河南,郑州,450052 |
| |
| 摘 要： | 讨论了建立约束Delaunay三角网算法的研究现状,采用“逐点插入法”和“多对角线交换算法”构成“两步法”,在此基础上,从建立高精度三角网模型的需求出发,研究以大数据量等高线为约束边进行Delaunay三角剖分的改进算法。针对“逐点插入法”,采用网格分块的方法对构网点集和已生成的三角网建立索引,提高了点的查询速度和点在三角网中的定位速度,提高了三角网的生成效率;针对“多对角线交换算法”,增加了一些特殊情况的处理,提高了算法的健壮性和交换速度。
|
| 关 键 词： | 约束Delaunay三角网 逐点插入法 约束边嵌入 对角线交换 等高线 |
| 文章编号： | 1006-7949（2007）03-0006-05 |
| 收稿时间： | 2006-12-06 |
| 修稿时间： | 2006-12-06 |
The of fast generation constraint delaunay triangulation with constraint lines |
| |
| XU Dao-zhu,LIU Hai-yan.The of fast generation constraint delaunay triangulation with constraint lines[J].Engineering of Surveying and Mapping,2007,16(3):6-10. |
| |
| Authors: | XU Dao-zhu LIU Hai-yan |
| |
| Institution: | Institute of Surveying and Mapping, Information Engineering University, Zhengzhou 450052, China |
| |
| Abstract: | It presents the status of Delaunay triangulation methods,which consists of two steps,firstly,constructing Delaunay triangulation by incremental insertion algorithm,and them inserting constrained boundary by multiple diagonal exchanging algorithm to form constraint Delaunay Triangulation.In order to construct high resolution Triangulation,the algorithm uses contour line as constraint line.The two steps algorithm,will improve the algorithm for fast inserting constrained line.In incremental insertion algorithm,it organizes the point set and triangle by constructing grid index to enhance the query speed of point and the speed of searching for the triangle that contains the given point.With the improving measures,the efficiency of algorithm is greatly improved. |
| |
| Keywords: | constraint delaunay triangulation incremental insertion algorithm inserting constrained boundary diagonal exchanging contour line |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
