摘要
讨论了建立约束Delaunay三角网算法的研究现状,采用“逐点插入法”和“多对角线交换算法”构成“两步法”,在此基础上,从建立高精度三角网模型的需求出发,研究以大数据量等高线为约束边进行Delaunay三角剖分的改进算法。针对“逐点插入法”,采用网格分块的方法对构网点集和已生成的三角网建立索引,提高了点的查询速度和点在三角网中的定位速度,提高了三角网的生成效率;针对“多对角线交换算法”,增加了一些特殊情况的处理,提高了算法的健壮性和交换速度。
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.
出处
《测绘工程》
CSCD
2007年第3期6-10,共5页
Engineering of Surveying and Mapping
基金
国家自然科学基金资助项目(40401052)
关键词
约束Delaunay三角网
逐点插入法
约束边嵌入
对角线交换
等高线
constraint delaunay triangulation
incremental insertion algorithm
inserting constrained boundary
diagonal exchanging
contour line
