快速构建三角网数字地形模型方法的研究

On the Method for Fast Constructing Delaunay Triangulation DTM

改进和优化了逐点插入算法 ,通过建立网格索引 ,实现了DTM数据的高效组织和管理 ,再结合有向查找技术 ,研究出了三角形的快速定位算法。采用Watson的空外接圆法优化构网 ,为减少优化时间 ,提出了按网格轮流取点的策略。在地性线的处理上 ,采用了先构建初级Delaunay三角网 ,再将地性线做为约束边嵌入初级网中的二级建网方案。经实践验证 ,该算法具有速度快、网形优、精度高。

In this paper, some methods for optimizing and improving the incremental insertion algorithm for construction of DTM are presented.The data of DTM are organized and controlled efficiently by constructing the grid index system, together with the technology of orient searching, the algorithm for fast searching for the triangle that contain the given point is worked out.The empty circumcircle test algorithm put forward by Watson is applied to searching for and reconstituting the impacted area.To accelerating that course,the strategy of extracting points from alternated grids in turn is implemented. Furthermore,two steps method is presented to dealing with terrain feature, that is constructing initial Delaunay triangulation net without considering terrain feature firstly, then implanting the terrain feature edges in the initial net. The whole algorithm has such characteristics as high speed, smart shape,high precision and wide use,which has been verified by its successful application.