引用本文: 吴宇豪, 曹雪峰. 面向Hilbert八叉树的邻近格元计算算法[J]. 武汉大学学报 ( 信息科学版), 2022, 47(4): 613-622.
WU Yuhao, CAO Xuefeng. A Hilbert-Octree Neighbor Grid Element Calculation Algorithm[J]. Geomatics and Information Science of Wuhan University, 2022, 47(4): 613-622.
 Citation: WU Yuhao, CAO Xuefeng. A Hilbert-Octree Neighbor Grid Element Calculation Algorithm[J]. Geomatics and Information Science of Wuhan University, 2022, 47(4): 613-622.

## A Hilbert-Octree Neighbor Grid Element Calculation Algorithm

• 摘要: 为提高线性八叉树邻近格元计算效率，利用Hilbert码标记格元，提出一种邻近格元Hilbert码快速计算方法。以Hilbert基元曲线为基础，引入状态向量的概念以记录Hilbert曲线对同属于一个父格元的所有子格元的填充顺序，从而建立状态向量的层级演进与退化函数，得到状态向量在m阶与m+1阶曲线中的层级映射关系，最终利用状态向量及其层级演进与退化函数实现邻近格元Hilbert码的计算。结果表明，所提算法计算结果正确；状态向量计算速度随层级提高而降低，在第20层级上1 ms内可完成4 201个格元的计算，对后续邻近格元计算影响较小；在指定层级上同等数量的邻近格元计算中，该算法的速度明显优于现有Morton码转换算法，在第15层级上百万级规模的邻近格元计算中，该算法的速度约为现有Morton码转换算法的2.1~2.4倍；在不同层级的百万级规模邻近格元计算中，该算法计算速度相比现有Morton码转换算法的提升倍数随层级提高而增大，在第20层级上该算法的效率提升达到2.6倍。

Abstract:
Objectives  In order to improve the calculation efficiency of linear octree neighbor grid elements, this paper uses Hilbert code to mark the grid elements and proposes a fast calculation algorithm for neighbor grid elements Hilbert code.
Methods  Based on the Hilbert primitive curve, the concept of state vector is introduced to record the filling order of the Hilbert curve to all child elements belonging to the same parent element, thereby establishing the hierarchical evolution and degradation function of the state vector.With the hierarchical mapping relationship in the order curve, the state vector and its hierarchical evolution function are finally used to calculate the neighboring grid element Hilbert code.
Results  The results of comparison experiments on calculation accuracy and efficiency show that the calculation result of the algorithm is correct. The calculation speed of the state vector decreases with the increase of the level. The calculation of 4 201 grid elements can be completed within 1 ms on the 20th level. In the calculation of the same number of neighbor grid elements at the specified level, the speed of this algorithm is significantly better than the existing Morton code conversion algorithm. At the 15th level, the speed of the algorithm in this paper is about 2.1-2.4 times that of the existing Morton code conversion algorithm. In the calculation of millions of adjacent cells at different levels, the calculation speed of the algorithm in this paper is compared with the existing Morton code conversion. The improvement factor of the algorithm increases as the level increases. At level 20, the efficiency of the proposed algorithm increases by 2.6 times.
Conclusions  Experimental results show that this algorithm is superior to the existing Morton code conversion algorithm, and can be used as the basis of spatial operations such as efficient data retrieval, determination of three-dimensional topological relationship and connectivity judgment.

/

• 分享
• 用微信扫码二维码

分享至好友和朋友圈