基于四叉树结构索引的约束TIN的构建

Building of Constrained TIN Based on Quad-tree Structured Index

提出了一个用四叉树索引对平面区域进行划分并在此基础上用前沿推进法实现平面点集TIN构建的算法。对于实际应用中所遇到的数据，四叉树索引能够在有限层次内对平面区域进行有效划分，从而保证了TIN构建程序的运行效率。该算法能适用于任意的初始边界约束条件，并对边界和点集的分布特征具有良好的适应能力，因此该算法适用于复杂地形的DTM建模。

This paper presents an algorithm for the triangulation of points in a Euclidean plane. The algorithm, based on a quad-tree structured index, is a modification of the frontier-advancement algorithm. When dealing with practical data, the quad-tree will divide the plane efficiently within limited levels, which enables the algorithm run with good time performance. The algorithm is suitable for any given boundary, and able to treat data of various distributions. Thus it can be used for DTM.