Algorithms of Producing Tetrahedral Network from Three Dimensional Dispersed Data
-
摘要: 在资源、环境、工程勘探等领域中, 由三维离散数据生成四面体格网, 对三维空间的判断分析, 并得出一些未知的三维空间体的分布信息具有重要意义.在分析三角网生成算法的基础上, 给出了3个建立四面体格网的算法思想及步骤: (1) 四面体格网生成算法.在数据场中先构成第1个四面体, 然后以四面体的某个面向外扩展生成新的四面体, 直至全部离散点均已连成网为止. (2) 逐次插入算法.将未处理的点加入到已经存在的四面体格网中, 每次插入一个点, 然后将四面体格网进行优化. (3) 分治算法.首先将数据排序, 然后递归地分割数据点集, 直至子集中只包含4个点而形成四面体, 然后自下而上地逐级合并生成最终的四面体格网.Abstract: 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.
-
[1] 李德仁, 李清泉. 一种三维GIS混合数据结构研究[J]. 测绘学报, 1997, 26 (2): 128-133. https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB702.005.htmLI D R, LI Q Q. Study on a hybrid data structure in 3D GIS. Acta Geodaetica et Cartographica Sinica, 1997, 26 (2): 128-133. https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB702.005.htm [2] 王建平, 翟裕生. 金成矿系统分析与找矿方法选择[J]. 地球科学———中国地质大学学报, 2000, 25 (4): 384-389. https://www.cnki.com.cn/Article/CJFDTOTAL-DQKX200004010.htmWANG J P, ZHAI Y S. Analysis of gold ore-forming system and selection of mineral prospecting: an evidence of gold ore exploration in concealed area, North Laizhou, Shandong Province[J]. Earth Science— Journal of China University of Geosciences, 2000, 25 (4): 384-389. https://www.cnki.com.cn/Article/CJFDTOTAL-DQKX200004010.htm [3] 黄旭钊, 徐昆, 梁月明. 利用MapInfo综合分析多源地学信息进行矿产预测[J]. 地球科学———中国地质大学学报, 2001, 26 (2): 189-191. https://www.cnki.com.cn/Article/CJFDTOTAL-DQKX200102018.htmHUANG X Z, XU K, LIANG Y M. Development and application of MapInfo: an example of assessing mineral resources by analyzing multiparametergeological information[J]. Earth Science— Journal of China University of Geosciences, 2001, 26 (2): 189-191. https://www.cnki.com.cn/Article/CJFDTOTAL-DQKX200102018.htm [4] 成秋明. 多重分形与地质统计学方法用于勘查地球化学异常空间结构和奇异性分析[J]. 地球科学———中国地质大学学报, 2001, 26 (2): 161-165. https://www.cnki.com.cn/Article/CJFDTOTAL-DQKX200102012.htmCHENG Q M. Multifractal and geostatistic methods for characterizing local structure and singularity properties of exploration geochemical anomalies[J]. Earth Science— Journal of China University of Geosciences, 2001, 26 (2): 161-165. https://www.cnki.com.cn/Article/CJFDTOTAL-DQKX200102012.htm [5] 李清泉, 李德仁. 三维空间数据模型集成的概念框架研究[J]. 测绘学报, 1998, 11: 325-330. doi: 10.3321/j.issn:1001-1595.1998.04.007LI Q Q, LI D R. Reserch on the conceptual frame of the intergration of 3D spatial data model[J]. Acta Geodaetica et Cartographica Sinica, 1998, 11: 325-330. doi: 10.3321/j.issn:1001-1595.1998.04.007 [6] Green P J, Sibson R. Computing dirichlet tesslelations in the plane[J]. The Computer Journal, 1978, 21 (2): 168-173. doi: 10.1093/comjnl/21.2.168 [7] Lewis B A, Robinson J S. Triangulation of planar regions with applications[J]. The Computer Journal, 1978, 21 (4): 324-332. doi: 10.1093/comjnl/21.4.324 [8] Lee D T, Schachter B J. Two algorithms for constructing a delaunay triangulation[J]. Int J of Computer and Information Sciences, 1980, 9 (3): 219-242. doi: 10.1007/BF00977785