三维Hilbert曲线层级演进模型与编码计算

doi:10.11947/j.AGCS.2022.20200241

摘要/Abstract

摘要： 格网单元的编码计算是全球离散网格系统的核心，支撑着网格快速索引及应用分析的高效计算。Hilbert曲线具有聚簇性高、连续性强的特点，是研究设计全球离散网格编码的重要工具。利用Hilbert曲线进行格元编码实现了坐标等效降维表达，但是对Hilbert曲线不同层级之间的变换关系、一维Hilbert码如何刻画格元多维空间结构与关系等网格编码基础理论问题的研究尚不完备。本文以八叉树立体网格中三维Hilbert曲线层级演进关系为突破口，使用状态矩阵与演进矩阵构建层级演进模型，进而分别设计笛卡儿坐标至Hilbert码计算以及邻近格元Hilbert码计算方法。与现有算法对比，本文算法以层级演进模型为理论基础，避免了烦琐迭代步骤以及转换步骤，算法流程简明直接。试验结果表明，本文笛卡儿坐标至Hilbert码计算效率较迭代算法提高为7%~23%，邻近格元Hilbert码计算效率较转换算法提高4.0~4.5倍。

关键词: 全球离散网格, Hilbert曲线, 编码计算, 邻近

Abstract: The coding calculation of grid cells is the core of the discrete global grid system, which supports efficient calculation of indexing and analysis. Hilbert curve has the characteristics of high clustering and strong continuity, and is an important tool for global discrete grid coding. The lattice element coding using Hilbert curve realizes the coordinate equivalent dimensionality reduction expression, but the research on the basic theoretical problems of grid coding still not complete. In this paper, the hierarchical evolution relationship of the three-dimensional Hilbert curve in the octree three-dimensional grid is used as a breakthrough. The state matrix and the evolution matrix are used to construct a hierarchical evolution model, and then the calculation methods of Cartesian coordinates to Hilbert codes and adjacent grid Hilbert codes are designed respectively. Compared with the existing algorithms, the algorithm in this paper is based on a hierarchical evolution model, which avoids cumbersome iteration steps and conversion steps, and the algorithm flow is simple and straightforward. The experimental results show that the calculation efficiency of Cartesian coordinates to Hilbert codes in this paper is "7%~23%" higher than that of the iterative algorithm, and the calculation efficiency of neighbor grid elements Hilbert codes is 4.0~4.5 times higher than that of the conversion algorithm.

Key words: discrete global grid, Hilbert curve, coding calculation, neighbor

中图分类号:

P208

吴宇豪, 曹雪峰, 余岸竹, 孙万忠. 三维Hilbert曲线层级演进模型与编码计算[J]. 测绘学报, 2022, 51(1): 104-114.

WU Yuhao, CAO Xuefeng, YU Anzhu, SUN Wanzhong. Hierarchical evolution model and coding calculation of three-dimensional Hilbert curve[J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(1): 104-114.

参考文献

[1] SAHR K, WHITE D, KIMERLING A J. Geodesic discrete global grid systems[J]. Cartography and Geographic Information Science, 2003, 30(2):121-134.
[2] DUTTON G. Part 4:Mathematical, algorithmic and data structure issues:geodesic modelling of planetary relief[J]. Cartographica:The International Journal for Geographic Information & Geovisualization, 1984, 21(2-3):188-207.
[3] 万刚, 曹雪峰. 地理空间信息网格的历史演变与思考[J]. 测绘学报, 2016, 45(S1):15-22. DOI:10.11947/j.AGCS.2016.F002. WAN Gang, CAO Xuefeng. The historical evolution and reflection of geospatial information grid[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(S1):15-22. DOI:10.11947/j.AGCS.2016.F002.
[4] GOODCHILD M F, SHIREN Y. A hierarchical spatial data structure for global geographic information systems[R]. Santa Barbara:University of California, 1989.
[5] SAGAN H. Space-filling curves[M]. New York:Springer-Verlag, 1994.
[6] KUMAR A. Mean-variance analysis of the performance of spatial ordering methods[J]. International Journal of Geographical Information Science, 1998, 12(3):269-289.
[7] RONG Y, FALOUTSOS C. Analysis of the clustering property of Peano curves[M]. City of College Park:University of Maryland Press, 1991.
[8] MOON B, JAGADISH H V, FALOUTSOS C, et al. Analysis of the clustering properties of the Hilbert space-filling curve[J]. IEEE Transactions on Knowledge and Data Engineering, 2001, 13(1):124-141.
[9] SAMET H. Foundations of multidimensional and metric data structures[M]. Boston:Elsevier, 2006.
[10] 赵学胜, 贲进, 孙文彬, 等. 地球剖分格网研究进展综述[J]. 测绘学报, 2016, 45(S1):1-14. DOI:10.11947/j.AGCS.2016.F001. ZHAO Xuesheng, BEN Jin, SUN Wenbin, et al. Overview of the research progress in the earth tessellation grid[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(S1):1-14. DOI:10.11947/j.AGCS.2016.F001.
[11] 程承旗, 张恩东, 万元嵬, 等. 遥感影像剖分金字塔研究[J]. 地理与地理信息科学, 2010, 26(1):19-23. CHENG Chengqi, ZHANG Endong, WAN Yuanwei, et al. Research on remote sensing image subdivision pyramid[J]. Geography and Geo-Information Science, 2010, 26(1):19-23.
[12] 林冰仙, 许德朋, 盛业华, 等. 正二十面体球面菱形离散格网的编码模型及其映射方法[J]. 测绘学报, 2016, 45(S1):23-31. DOI:10.11947/j.AGCS.2016.F003. LIN Bingxian, XU Depeng, SHENG Yehua, et al. Coding model and mapping method of spherical diamond discrete grids based on icosahedron[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(S1):23-31. DOI:10.11947/j.AGCS.2016.F003.
[13] 曹雪峰. 地球圈层空间网格理论与算法研究[D]. 郑州:信息工程大学, 2012. CAO Xuefeng. Research on earth sphere shell space grid theory and algorithms[D]. Zhengzhou:Information Engineering University, 2012.
[14] 曹雪峰, 万刚, 张宗佩. 紧致的Hilbert曲线Gray码索引算法[J]. 测绘学报, 2016, 45(S1):90-98. DOI:10.11947/j.AGCS.2016.F010. CAO Xuefeng, WAN Gang, ZHANG Zongpei. Compact Hilbert curve index algorithm based on Gray code[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(S1):90-98. DOI:10.11947/j.AGCS.2016.F010.
[15] 张宗佩. 地月圈层立体网格理论与应用研究[D]. 郑州:信息工程大学, 2015. ZHANG Zongpei. Research on earth-lunar sphere shell space grid theory and application[D]. Zhengzhou:Information Engineering University, 2015.
[16] 张宗佩, 万刚, 曹雪峰, 等. 地月圈层空间立体网格技术及其编码转换方法[J]. 测绘通报, 2015(6):20-23, 27. DOI:10.13474/j.cnki.11-2246.2015.0169. ZHANG Zongpei, WAN Gang, CAO Xuefeng, et al. Earth-lunar shell space solid grid technology and coding-conversion[J]. Bulletin of Surveying and Mapping, 2015(6):20-23, 27. DOI:10.13474/j.cnki.11-2246.2015.0169.
[17] 张宗佩, 万刚, 曹雪峰, 等. 月球圈层空间立体网格技术研究[J]. 测绘科学技术学报, 2015(1):101-105, 110. ZHANG Zongpei, WAN Gang, CAO Xuefeng, et al. Lunar shell space solid grid technology[J]. Journal of Geomatics Science and Technology, 2015(1):101-105, 110.
[18] 吴宇豪, 曹雪峰. 虚拟战场环境时空数据的Hilbert码索引方法[J]. 武汉大学学报(信息科学版), 2020, 45(9):1403-1411. WU Yuhao, CAO Xuefeng. Hilbert code index method for spatiotemporal data of virtual battlefield environment[J]. Geomatics and Information Science of Wuhan University, 2020, 45(9):1403-1411.
[19] GUAN Xuefeng, VAN OOSTEROM P, CHENG Bo. A parallel N-dimensional space-filling curve library and its application in massive point cloud management[J]. ISPRS International Journal of Geo-Information, 2018, 7(8):327.
[20] WU Yuhao, CAO Xuefeng, AN Zipeng. A spatiotemporal trajectory data index based on the Hilbert curve code[C]//Proceedings of the First China Digital Earth Conference 18-20 November 2019, Beijing, China:IOP Conference Series:Earth and Environmental Science, 2020.
[21] LIU Xian, SCHRACK G. Encoding and decoding the Hilbert order[J]. Software:Practice and Experience, 1996, 26(12):1335-1346.
[22] LI Chenyang, FENG Yucai. Algorithm for analyzing N-dimensional Hilbert curve[C]//Proceedings of International Conference on Web-Age Information Management. Hangzhou, China:Springer, 2005:657-662.
[23] 李绍俊, 钟耳顺, 王少华, 等. 基于状态转移矩阵的Hilbert码快速生成算法[J]. 地球信息科学学报, 2014, 16(6):846-851. LI Shaojun, ZHONG Ershun, WANG Shaohua, et al. An algorithm for Hilbert ordering code based on state-transition matrix[J]. Journal of Geo-Information Science, 2014, 16(6):846-851.
[24] 曹雪峰, 万刚, 张宗佩. Hilbert曲线层级演进关系[J]. 测绘学报, 2016, 45(S1):77-84. DOI:10.11947/j.AGCS.2016.F009. CAO Xuefeng, WAN Gang, ZHANG Zongpei. Hilbert curve hierarchical evolution relationship[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(S1):77-84. DOI:10.11947/j.AGCS.2016.F009.
[25] CHOI M G, JU E, CHANG J W, et al. Linkless Octree using multi-level perfect hashing[J]. Computer Graphics Forum, 2009, 28(7):1773-1780.
[26] CHEN H L, CHANG Y I. Neighbor-finding based on space-filling curves[J]. Information Systems, 2005, 30(3):205-226.
[27] 徐红波, 郝忠孝. 基于空间填充曲线网格划分的最近邻查询算法[J]. 计算机科学, 2010, 37(1):184-188. XU Hongbo, HAO Zhongxiao. Nearest-neighbor query algorithm based on grid partition of space-filling curve[J]. Computer Science, 2010, 37(1):184-188.
[28] CHEN H L, CHANG Y I. All-nearest-neighbors finding based on the Hilbert curve[J]. Expert Systems with Applications, 2011, 38(6):7462-7475.
[29] WU Yuhao, CAO Xuefeng, SUN Wanzhong. MI-HCS:monotonically increasing Hilbert code segments for 3D geospatial query window[J]. IEEE Access, 2020, 8:47580-47595.
[30] 李晨阳, 段雄文, 冯玉才. N维Hilbert曲线生成算法[J]. 中国图象图形学报, 2006, 11(8):1068-1075. LI Chenyang, DUAN Xiongwen, FENG Yucai. Algorithm for generating N-dimensional Hilbert curve[J]. Journal of Image and Graphics, 2006, 11(8):1068-1075.
[31] 巴恩斯利M F. 分形图形学[M]. 和风, 译. 北京:海洋出版社, 1995. BARNSLEY M F. The science of fractal images[M]. HE Feng, trans. Beijing:China Ocean Press, 1995.