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.
DownLoad: