A Hilbert-Octree Neighbor Grid Element Calculation Algorithm

WU Yuhao; CAO Xuefeng

doi:10.13203/j.whugis20200099

Volume 47 Issue 4

Apr. 2022

Turn off MathJax

Article Contents

Abstract

References

Geomatics and Information Science of Wuhan University > 2022 > 47(4): 613-622. > DOI: 10.13203/j.whugis20200099

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. DOI: 10.13203/j.whugis20200099

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. DOI: 10.13203/j.whugis20200099

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. DOI: 10.13203/j.whugis20200099

PDF (6072 KB)

A Hilbert-Octree Neighbor Grid Element Calculation Algorithm

WU Yuhao^1,,
CAO Xuefeng^1,

1.
Institute of Geographical Spatial, Information Engineering University, Zhengzhou 450001, China

Funds:

The National Natural Science Foundation of China 41401465

The National Natural Science Foundation of China 41371384

More Information

Author Bio:
WU Yuhao, postgraduate, specializes in the discrete global grid system. E-mail: 514536575@qq.com
Corresponding author:
CAO Xuefeng, PhD, associate professor. E‐mail: CAO_Xue_Feng@163.com
Received Date: March 16, 2020
Published Date: April 04, 2022

Graphical Abstract

Abstract

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.
- Hilbert code,
- linear octree,
- neighbor lattice element,
- state vector

FullText(HTML)

References (24)

References

[1]	周果, 朱登明, 王兆其. 面向大规模场景的多片元效果高效绘制[J]. 计算机学报, 2017, 40(11): 2606-2618 doi: 10.11897/SP.J.1016.2017.02606 Zhou Guo, Zhu Dengming, Wang Zhaoqi. Efficient Rendering of Multi-fragment Effects for Massive Scene[J]. Chinese Journal of Computers, 2017, 40 (11): 2606-2618 doi: 10.11897/SP.J.1016.2017.02606
[2]	Dutré J. Out-of-Core Construction of Sparse Voxel Octrees[J]. Computer Graphics Forum: Journal of the European Association for Computer Graphics, 2014, DOI: 10.1145/2492045.2492048
[3]	吕梦雅, 刘丁, 唐勇, 等. 真实感海下光照效果实时绘制[J]. 小型微型计算机系统, 2018, 39(10): 2326-2329 doi: 10.3969/j.issn.1000-1220.2018.10.034 Lü Mengya, Liu Ding, Tang Yong, et al. Improved Fast Rendering Algorithm for Large-Scale Underwater Illumination Effect[J]. Journal of Chinese Computer Systems, 2018, 39(10): 2326-2329 doi: 10.3969/j.issn.1000-1220.2018.10.034
[4]	Bi L, Zhao H, Jia M T. Database-Oriented Storage Based on LMDB and Linear Octree for Massive Block Model[J]. Transactions of Nonferrous Metals Society of China, 2016, 26(9): 2462-2468 doi: 10.1016/S1003-6326(16)64377-7
[5]	Moon B, Jagadish H V, Faloutsos C, et al. Analysis of the Clustering Properties of the Hilbert SpaceFilling Curve[J]. IEEE Trans Knowl Data Eng, 2001, 13(1): 124-141 doi: 10.1109/69.908985
[6]	万刚, 曹雪峰. 地理空间信息网格的历史演变与思考[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
[7]	Guan X F, van Oosterom P, Cheng B. 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 doi: 10.3390/ijgi7080327
[8]	曹布阳, 冯华森, 梁峻浩, 等. 利用Hilbert曲线与Cassandra技术实现时空大数据存储与索引[J]. 武汉大学学报·信息科学版, 2021, 46(5): 620-629 doi: 10.13203/j.whugis20200367 Cao Buyang, Feng Huasen, Liang Junhao, et al. Hilbert Curve and Cassandra Based Indexing and Storing Approach for Large-Scale Spatiotemporal Data[J]. Geomatics and Information Science of Wuhan University, 2021, 46(5): 620-629 doi: 10.13203/j.whugis20200367
[9]	Mekuria R, Blom K, Cesar P. Design, Implementation, and Evaluation of a Point Cloud Codec for Tele-Immersive Video[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2017, 27(4): 828-842 doi: 10.1109/TCSVT.2016.2543039
[10]	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 doi: 10.1111/j.1467-8659.2009.01554.x
[11]	Meijers M, van Oosterom P. Clustering and Indexing Historic Vessel Movement Data with Space Filling Curves[J]. The International Archives of the Photogrammetry, Remote Sensing and Spatial Infor⁃ mation Sciences, 2018, XLII-4: 417-424
[12]	van Oosterom P, Martinez-Rubi O, Ivanova M, et al. Massive Point Cloud Data Management: Design, Implementation and Execution of a Point Cloud Benchmark [J]. Computers & Graphics, 2015, 49: 92-125 doi: 10.1016/j.cag.2015.01.007
[13]	Chen H L, Chang Y I. Neighbor-Finding Based on Space-Filling Curves [J]. Information Systems, 2005, 30(3): 205-226 doi: 10.1016/j.is.2003.12.002
[14]	徐红波, 郝忠孝. 基于空间填充曲线网格划分的最近邻查询算法[J]. 计算机科学, 2010, 37 (1): 184-188 doi: 10.3969/j.issn.1002-137X.2010.01.043 Xu Hongbo, Hao Zhongxiao. Nearest-Neighbor Query Algorithm Based on Grid Partition of SpaceFilling Curve[J]. Computer Science, 2010, 37(1): 184-188 doi: 10.3969/j.issn.1002-137X.2010.01.043
[15]	Sadeghi F, Kermani F, Rafsanjani M. Optimizing Image Steganography by Combining the GA and ICA [J]. ISC Int J Inf Secur, 2015, 7: 47-58 doi: 10.1158/1078-0432.CCR-04-2378
[16]	Huang W, Zhang W, Zhang D Y, et al. Elastic Spatial Query Processing in OpenStack Cloud Computing Environment for Time-Constraint Data Analysis [J]. ISPRS International Journal of Geo-Information, 2017, 6(3): 84 doi: 10.3390/ijgi6030084
[17]	刘辉, 冷伟, 崔涛. 高维Hilbert曲线的编码与解码算法设计[J]. 数值计算与计算机应用, 2015, 36(1): 42-58 https://www.cnki.com.cn/Article/CJFDTOTAL-SZJS201501005.htm Liu Hui, Leng Wei, Cui Tao. Development of Encoding and Decoding Algorithms for High Dimensional Hilbert Curves[J]. Journal on Numerical Methods and Computer Applications, 2015, 36(1): 42-58 https://www.cnki.com.cn/Article/CJFDTOTAL-SZJS201501005.htm
[18]	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 doi: 10.1016/j.eswa.2010.12.077
[19]	戴晶, 吴明光, 郑培蓓, 等. 基于Hilbert曲线的STR索引改进算法[J]. 武汉大学学报·信息科学版, 2014, 39(7): 777-781 http://ch.whu.edu.cn/article/id/3019 Dai Jing, Wu Mingguang, Zheng Peibei, et al. An Improved STR-Tree Spatial Index Algorithm Based on Hilbert-Curve[J]. Geomatics and Information Science of Wuhan University, 2014, 39(7): 777-781 http://ch.whu.edu.cn/article/id/3019
[20]	Shen J H, Lu C T, Jian M S. Neighbor-Index Method for Continuous Window Queries over Wireless Data Broadcast[J]. Applied Mechanics and Materials, 2013, 284: 3295-3299 doi: 10.4028/www.scientific.net/AMM.284-287.3295
[21]	Stommel M, Edelkamp S, Wiedemeyer T, et al. Fractal Approximate Nearest Neighbour Search in Log-Log Time[C]//The British Machine Vision Conference 2013, Bristol, UK, 2013
[22]	Liu X, Schrack G F. An Algorithm for Encoding and Decoding the 3-D Hilbert Order[J]. IEEE Transactions on Image Processing, 1997, 6(9): 1333-1337 doi: 10.1109/83.623197
[23]	Campbell P M, Flaherty J E, Gervasio L G. Dynamic Octree Load Balancing Using Space-Filling Curves[J]. Theory of Computing Systems, 2010, DOI: 10.1007/s00224-010-9306-3
[24]	Butz A R. Alternative Algorithm for Hilbert's Space-Filling Curve[J]. IEEE Transactions on Computers, 1971, C-20(4): 424-426 doi: 10.1109/T-C.1971.223258

Cited By

Cited by

Periodical cited type(4)

1.	邓凯锋，陶黎明，蒲阳，程鹏飞. 三维点云重建下电力作业安全距离测量系统. 计算机仿真. 2025(01): 62-66+105 .
2.	李颖颖，黄文培. 基于优化八叉树的场景视锥体裁剪算法. 计算机与现代化. 2024(01): 103-108 .
3.	张译，魏永瑜，马燕，冶秀兰，马元明. 基于最邻近算法的数据中台内生性数据安全交互系统. 电子设计工程. 2024(08): 121-124+129 .
4.	李泽宇，赵志刚，万远，陈俊杰，徐海. 面向BIM构件实例模型的层次聚类方法研究. 测绘科学. 2023(03): 146-154 .

Other cited types(6)

Get Citation

PDF

XML

Article views (773) PDF downloads (54) Cited by(10)

A Hilbert-Octree Neighbor Grid Element Calculation Algorithm

Abstract

References

Cited by

Periodical cited type(4)

Other cited types(6)

Catalog

Related

A Hilbert-Octree Neighbor Grid Element Calculation Algorithm

Abstract

References

Cited by

Periodical cited type(4)

Other cited types(6)

Catalog

Related

Export File

Citation

Format

Content