由三维离散数据生成四面体格网算法研究

在资源、环境、工程勘探等领域中, 由三维离散数据生成四面体格网, 对三维空间的判断分析, 并得出一些未知的三维空间体的分布信息具有重要意义.在分析三角网生成算法的基础上, 给出了3个建立四面体格网的算法思想及步骤: (1) 四面体格网生成算法.在数据场中先构成第1个四面体, 然后以四面体的某个面向外扩展生成新的四面体, 直至全部离散点均已连成网为止. (2) 逐次插入算法.将未处理的点加入到已经存在的四面体格网中, 每次插入一个点, 然后将四面体格网进行优化. (3) 分治算法.首先将数据排序, 然后递归地分割数据点集, 直至子集中只包含4个点而形成四面体, 然后自下而上地逐级合并生成最终的四面体格网. 

Algorithms of Producing Tetrahedral Network from Three Dimensional Dispersed Data

In the fields of resources, environment and engineering exploration, tetrahedral network created up from the three dimensional dispersed data is of great significance for making three dimension spatial analysis to obtain the distribution of unknown three dimensional spatial objects. Based on the analysis of the triangulation irregular network algorithms, the authors put forward three ideas and steps of building tetrahedral network. (1) Triangulation growth: The first tetrahedron is first generated in a data field. Then a new tetrahedron is spread out from one surface of the tetrahedron. This continues until all discrete points are connected to a network. (2) Incremental insertion: The un processed data are inserted in the existing tetrahedral network, once a point. Then the local optimization procedure of the network is realized. (3) Divided conquer: First, the data are ordered. Then the collections of data points are recursively divided until each collection only includes four points to form a tetrahedron. Finally, every tetrahedral network is merged from lower level to upper level until the last tetrahedral network is produced.