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

论文摘要

不规则三角网(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 increme...

下载地址

http://www.gissky.net- GIS空间站