摘要：

提出一种基于离散点Delaunay三角网快速构建的网格生长算法，采用分治算法将离散点表达为唯一网格，利用稀疏矩阵完成网格数据的压缩存储，通过标识码实现有值单元格与离散点之间的高效检索，从而提高网格构建的效率。依据有值单元格的密度获取预设正方形搜索空间，并在三角网扩展时根据需要动态建立正方形搜索空间，从而保证网格生长的准确性。实验结果表明，该算法的时间复杂度为O(nlogn)，对于少量或海量离散点均具有较好的适应性。

关键词: Delaunay三角网, 不规则三角网, 离散点, 正方形搜素空间, 网格生长算法

Abstract:

This paper presents a grid growing algorithm for fast construction of Delaunay irregular network based on discrete point. In this algorithm, a grid is achieved to express discrete point uniquely based on the divide-and-conquer method, which is compressed storage in a sparse matrix, and an efficient retrieval method is established between value cell and discrete point by identification code, which is effectively to improve the efficiency of the construction of Triangular Irregular Network(TIN). According to the density of value cells, a default square search space is acquired, and it is allowed to create the square search space dynamically in the expansion process of TIN, which ensures the accuracy of the grid growing. Experimental results show that the time complexity of the proposed algorithm is O(nlogn), and the algorithm is available to both small and massive amount of discrete points.

Key words: Delaunay triangular network, Triangular Irregular Network(TIN), discrete point, square search space, grid growing algorithm

中图分类号: 

• P209