基于四叉树索引构建TIN的高效合成算法  

An Effectively Combined Algorithm of Generating TIN Based on the Quad-Tree Structured Index

作　　者：郑美霞 王彦兵[1] 马翔旭 

机构地区：[1]首都师范大学三维信息获取与应用教育部重点实验室,首都师范大学资源环境与旅游学院,北京100048

出　　处：《地理与地理信息科学》2012年第2期20-23,59,共5页Geography and Geo-Information Science

基　　金：北京市自然科学基金项目(4102015)

摘　　要：不规则三角网(TIN)可以逼真的模拟地形表面,因此被广泛应用于地学领域。Delaunay三角剖分算法是构建TIN网的最优算法,该文对传统Delaunay三角网构建算法进行分析,提出了一种针对大规模离散数据点生成TIN的高效合成算法。该算法首先根据离散点的分布位置和密度对其进行四叉树区域划分;然后以每个叶子节点的边界四边形为凸包,采用逐点插入法构建三角网;最后采用顶点合并法自底向上合并具有相同父节点的4个子节点,生成Delaunay三角网。实验结果表明,该算法时间复杂度较低,有效提高了TIN网的构建效率。Triangulation Irregular Network（TIN） is widely used in Geosciences because it can simulate terrain surface.The Delaunay triangulation algorithm is an optimal algorithm to generate TIN.After analyzing the traditional algorithm of building Delaunay triangulation,a combined algorithm which can quickly generate TIN for large-scale discrete data points is proposed in this paper.Using this algorithm,discrete points are firstly divided by Quad-tree based on their position and density.Then using incremental insertion algorithm,triangulation is built,with quadrilateral boundary of each leaf node as convex hull.Finally,the four sub-nodes with the same parent are bottom-up merged with vertex combined approach to generate Delaunay triangulation.The results of experiment show that the algorithm has a low time complexity and effectively improves the efficiency of generating TIN.

关 键 词：DELAUNAY三角网 四叉树 逐点插入法 顶点合并法 

分 类 号：P208[天文地球—地图制图学与地理信息工程]