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(17)

1.	彭继达，张春桂. 基于PCA-RF组合模型的福建省空气负氧离子浓度预测研究. 能源与环保. 2024(01): 17-24 .
2.	张成才，王蕊，侯佳彤，姜明梁，祝星星. 基于特征变量筛选的无人机多光谱遥感土壤含水量反演. 中国农村水利水电. 2024(05): 147-154 .
3.	王宇，杨丽萍，任杰，张静，孔金玲，侯成磊. 联合ALOS-2和Landsat 8的绿洲土壤水分反演模型研究. 武汉大学学报(信息科学版). 2024(09): 1630-1638 .
4.	薛智暄，张丽，王新军，李永康，张冠宏，李沛尧. 古尔班通古特沙漠SMAP土壤水分产品降尺度分析. 干旱区研究. 2023(04): 583-593 .
5.	艾小童. 基于ELM模型的极化SAR土壤水分降尺度研究. 地理空间信息. 2023(07): 11-15 .
6.	杨丽萍，王彤，苏志强，侯成磊，冯瑞. 随机森林反演绿洲土壤水分的特征参数优化降维方法. 西北大学学报(自然科学版). 2022(02): 181-191 .
7.	王思楠，李瑞平，吴英杰，赵水霞，王秀青. 基于环境变量和机器学习的土壤水分反演模型研究. 农业机械学报. 2022(05): 332-341 .
8.	杨丽萍，苏志强，侯成磊，白宇兴，王彤，孔金玲. 基于随机森林的干旱区全极化SAR土壤含水量反演. 吉林大学学报(地球科学版). 2022(04): 1255-1264 .
9.	王斌，何丙辉，林娜，王伟，李天阳. 基于随机森林特征选择的茶园遥感提取. 吉林大学学报(工学版). 2022(07): 1719-1732 .
10.	张双成，鲍琳，马中民，陈雪蓉，马红利，周昕. 多源哨兵数据解译农田区土壤湿度算法研究. 测绘科学. 2022(08): 94-104 .
11.	杨丽萍，侯成磊，苏志强，白宇兴，王彤，冯瑞. 基于机器学习和全极化雷达数据的干旱区土壤湿度反演. 农业工程学报. 2021(13): 74-82 .
12.	李向龙，赵洪丽，赵红莉，王镕，郝震. 极限学习机模型的土壤含水量反演研究. 测绘科学. 2021(12): 91-97 .
13.	张王菲，文哲，张亚红，张庭苇，李云. Stokes参数在油菜长势监测中的可行性分析. 武汉大学学报(信息科学版). 2020(02): 242-249 .
14.	黄赫，周勇，刘宇杰，肖梁，李可，段建设，魏洪亮. 基于多源环境变量和随机森林的农用地土壤重金属源解析——以襄阳市襄州区为例. 环境科学学报. 2020(12): 4548-4558 .
15.	魏琪，林增刚，郭阳明，孔德岐，张双. 面向移动智能终端的人体心率监护系统设计与实现. 计算机测量与控制. 2019(11): 30-33+38 .
16.	黄华国. 林业定量遥感研究进展和展望. 北京林业大学学报. 2019(12): 1-14 .
17.	李文吉，姜德才，郑向向，宋艳茹，杨昭颖. 云贵高原典型地物L波段SAR散射特性分析——以昆明为例. 上海国土资源. 2019(04): 77-81 .

Other cited types(31)

Get Citation

PDF

XML

Article views (774) PDF downloads (54) Cited by(48)

A Hilbert-Octree Neighbor Grid Element Calculation Algorithm

Abstract

References

Cited by

Periodical cited type(17)

Other cited types(31)

Catalog

Related

A Hilbert-Octree Neighbor Grid Element Calculation Algorithm

Abstract

References

Cited by

Periodical cited type(17)

Other cited types(31)

Catalog

Related

Export File

Citation

Format

Content