三维空间格网的多尺度整数编码与数据索引方法

doi:10.11947/j.AGCS.2018.20170364

测绘学报 ›› 2018, Vol. 47 ›› Issue (7): 1007-1017.doi: 10.11947/j.AGCS.2018.20170364

三维空间格网的多尺度整数编码与数据索引方法

赖广陵¹, 童晓冲¹, 丁璐¹, 秦志远²

1. 信息工程大学地理空间信息学院, 河南郑州 450001;
2. 河南城建学院, 河南平顶山 467036

收稿日期:2017-06-27 修回日期:2018-03-20 出版日期:2018-07-20 发布日期:2018-07-25
通讯作者: 童晓冲 E-mail:txchr@163.com
作者简介:赖广陵(1992-),男,博士生,研究方向为三维数据处理和高分辨率卫星影像处理。E-mail:lgl_fly@126.com
基金资助:
国家自然科学基金（41671409；41201392）

Multiscale Integer Coding and Data Index of 3D Spatial Grid

LAI Guangling¹, TONG Xiaochong¹, DING Lu¹, QIN Zhiyuan²

1. Institute of Geospatial Information, Information Engineering University, Zhengzhou 450001, China;
2. Henan University of Urban Construction, Pingdingshan 467036, China

Received:2017-06-27 Revised:2018-03-20 Online:2018-07-20 Published:2018-07-25
Supported by:
The National Natural Science Foundation of China (Nos. 41671409;41201392)

摘要/Abstract

摘要： 本文针对三维空间索引方法存在的问题，提出了一种适用于三维空间格网化区域的多尺度整数编码与索引方法。该方法利用整数对由规则格网划分的空间区域进行统一编码，形成了一种包含格网大小关系和格网尺度变化的树状结构，体现了不同尺度格网之间的包含/被包含、相邻等空间关系，最终实现了对多种尺度格网的统一整数编码化处理。在此基础上，还研究了层级运算、编码与格网坐标转换运算、父单元查询和子单元查询等基本运算方法，并与Oracle Spatial的三维R树索引进行比较，设计了对比试验。结果表明，三维空间格网的多尺度整数编码在数据导入、索引建立及区域查询三个方面均优于Oracle Spatial的三维R树索引方法，其效率分别提高了约2倍、46倍和4倍。

关键词: 规则格网划分, 三维空间索引, 多尺度整数编码, 编码计算, 区域查询

Abstract: This paper proposed a multiscale integer coding and index method available for 3D spatial grid area based on the exiting problems of 3D spatial grid.This method used integer to unify coding the region divided by regular grid, formed a tree structure showed the size relationship and scale variation of grid which embodied the spatial relationships in different scale grid:include, be included, adjacent and so on, and achieved the unified integer coding of multi-scale grid in the end.On this basis, a serious of basic operation methods were also studied like:level operation, coordinate transformation operation between coding and grid, parent-unit query and sub-unit query.The contrast experiment was designed to compare this method with 3D R-tree index of Oracle Spatial.The result showed that, multiscale integer coding of 3D spatial grid was superior to the 3D R-tree of Oracle Spatial in data importing, index establishing and region querying, and the efficiency were enhanced about two times, forty-six times and four times respectively.

Key words: regular grid division, 3D spatial index, multiscale integer coding, coding operation, region query

中图分类号:

P237

赖广陵, 童晓冲, 丁璐, 秦志远. 三维空间格网的多尺度整数编码与数据索引方法[J]. 测绘学报, 2018, 47(7): 1007-1017.

LAI Guangling, TONG Xiaochong, DING Lu, QIN Zhiyuan. Multiscale Integer Coding and Data Index of 3D Spatial Grid[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(7): 1007-1017.

参考文献

[1] BENTLEY J L. Multidimensional Binary Search Trees Used for Associative Searching[J]. Communications of the ACM, 1975, 18(9):509-517.
[2] GAEDE V, GVNTHER O. Multidimensional Access Methods[J]. ACM Computing Surveys, 1998, 30(2):170-231.
[3] 邵正伟, 席平. 基于八叉树编码的点云数据精简方法[J]. 工程图学学报, 2010, 31(4):73-76. SHAO Zhengwei, XI Ping. Data Reduction for Point Cloud Using Octree Coding[J]. Journal of Engineering Graphics, 2010, 31(4):73-76.
[4] 张会霞. 基于八叉树的点云数据的组织与可视化[J]. 太原师范学院学报(自然科学版), 2011, 10(3):128-132. ZHANG Huixia. The Organization and Visualization of Point Cloud Data Based on the Octree[J]. Journal of Taiyuan Normal University (Natural Science Edition), 2011, 10(3):128-132.
[5] 张传明, 潘懋, 徐绘宏. 基于分块混合八叉树编码的海量体视化研究[J]. 计算机工程, 2007, 33(14):33-35, 78. ZHANG Chuanming, PAN Mao, XU Huihong. Hybrid Blocking Octree-based Mass Volume Rendering[J]. Computer Engineering, 2007, 33(14):33-35, 78.
[6] 綦科, 谢冬青, 刘洁. 基于八叉树空间分割的三维点云模型密写[J]. 计算机工程, 2011, 37(4):7-9. QI Ke, XIE Dongqing, LIU Jie. 3D Point Cloud Model Steganography Based on Octree Space Division[J]. Computer Engineering, 2011, 37(4):7-9.
[7] 宋扬, 潘懋, 朱雷. 三维GIS中的R树索引研究[J]. 计算机工程与应用, 2004(14):9-10, 21. SONG Yang, PAN Mao, ZHU Lei. Study of R-tree Spatial Access Method in Three Dimensional GIS[J]. Computer Engineering and Applications, 2004(14):9-10, 21.
[8] BRAKATSOULAS S, PFOSER D, THEODORIDIS Y. Revisiting R-tree Construction Principles[C]//Proceedings of the 6th East European Conference on Advances in Databases and Information Systems. Bratislava, Slovakia:Springer, 2002:149-162.
[9] 郑坤, 朱良峰, 吴信才, 等. 3D GIS空间索引技术研究[J]. 地理与地理信息科学, 2006, 22(4):35-39. ZHENG Kun, ZHU Liangfeng, WU Xincai, et al. Study on Spatial Indexing Techniques for 3D GIS[J]. Geography and Geo-Information Science, 2006, 22(4):35-39.
[10] GUTTMAN A. R-trees:A Dynamic Index Structure for Spatial Searching[J]. ACM SIGMOD Record, 1984, 14(2):47-57.
[11] BECKMANN N, KRIEGEL H P, SCHNEIDER R, et al. The R-tree:An Efficient And Robust Access Method for Points and Rectangles[J]. ACM SIGMOD Record, 1990, 19(2):322-331.
[12] SELLIS T K, ROUSSOPOULOS N, FALOUTSOS C. The R+-tree:A Dynamic Index for Multi-dimensional Objects[C]//Proceedings of the 13th International Conference on Very Large Data Bases. San Francisco:Morgan Kaufmann Publishers, 1987:507-518.
[13] 邓红艳, 武芳, 翟仁健, 等. 一种用于空间数据多尺度表达的R树索引结构[J]. 计算机学报, 2009, 32(1):177-184. DENG Hongyan, WU Fang, ZHAI Renjian, et al. R-tree Index Structure for Multi-scale Representation of Spatial Data[J]. Chinese Journal of Computers, 2009, 32(1):177-184.
[14] 龚俊, 朱庆, 张叶廷, 等. 顾及多细节层次的三维R树索引扩展方法[J]. 测绘学报, 2011, 40(2):249-255. GONG Jun, ZHU Qing, ZHANG Yeting, et al. An Efficient 3D R-tree Extension Method Concerned With Levels of Detail[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(2):249-255.
[15] ROBINSON J T. The K-D-B-tree:A Search Structure for Large Multidimensional Dynamic Indexes[C]//Proceedings of the 1981 ACM SIGMOD international conference on Management of data. New York:ACM, 1981:10-18.
[16] 张泽宝. 空间数据库的索引技术研究[D]. 哈尔滨:哈尔滨工程大学, 2009. ZHANG Zebao. Research on Spatial Index Technology for Spatial Database[D]. Harbin:Harbin Engineering University, 2009.
[17] 张芩, 王振民. QR-树:一种基于R-树与四叉树的空间索引结构[J]. 计算机工程与应用, 2004(9):100-103. ZHANG Qin, WANG Zhenmin. QR-tree:A Kind of Spatial Index Structure Based on R-tree and Quad-tree[J]. Computer Engineering and Applications, 2004(9):100-103.
[18] 童晓冲, 贲进. 空间信息剖分组织的全球离散格网理论与方法[M]. 北京:测绘出版社, 2016. TONG Xiaochong, BEN Jin. The Principle and Method of Discrete Global Grid Systems for Geospatial Information Subdivision Organization Principle and Method of Discrete Global Grid Systems for Geospatial Information Subdivision Organization[M]. Beijing:Surveying and Mapping Press, 2016.
[19] 王晏民. 多比例尺GIS矢量空间数据组织研究[D]. 武汉:武汉大学, 2002. WANG Yanmin. Multiscale GIS Vector Spatial Data Organization Study[D]. Wuhan:Wuhan University, 2013.
[20] 夏宇, 朱欣焰, 李德仁. 空间信息多级网格索引技术研究[J]. 地理空间信息, 2006, 4(6):4-7. XIA Yu, ZHU Xinyan, LI Deren. Indexing Technology in Spatial Information Multi-grid[J]. Geospatial Information, 2006, 4(6):4-7.
[21] SAGAN H. Space-filling Curves[M]. New York:Springer-Verlag, 1994.
[22] 史绍雨, 唐新明, 吴凡, 等. 多级格网时空索引[J]. 测绘科学, 2006, 31(3):54-55. SHI Shaoyu, TANG Xinming, WU Fan, et al. Multi-level Grid Spatio-temporal Index[J]. Science of Surveying and Mapping, 2006, 31(3):54-55.
[23] 张小虎, 钟耳顺, 王少华, 等. 多尺度空间格网数据的索引编码研究[J]. 测绘通报, 2014(7):35-38. ZHANG Xiaohu, ZHONG Ershun, WANG Shaohua, et al. Research on Index and Code For Multi-scale Grid Data[J]. Bulletin of Surveying and Mapping, 2014(7):35-38.
[24] 周勇, 何建农, 凃平. 一种改进的自适应层次网格空间索引查询算法[J]. 计算机工程与应用, 2006, 42(7):159-161, 165. ZHOU Yong, HE Jiannong, TU Ping. An Algorithm of Improved Auto-selection Multi-layer Grid Spatial Index[J]. Computer Engineering and Applications, 2006, 42(7):159-161, 165.
[25] 童晓冲, 王嵘, 王林, 等. 一种有效的多尺度时间段剖分方法与整数编码计算[J]. 测绘学报, 2016, 45(S1):66-76. DOI:10.11947/j.AGCS.2016.F008. TONG Xiaochong, WANG Rong, WANG Lin, et al. An Efficient Integer Coding and Computing Method for Multiscale Time Segment[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(S1):66-76. DOI:10.11947/j.AGCS.2016.F008.
[26] ORENSTEIN J A, MERRETT T H. A Class of Data Structures for Associative Searching[C]//Proceedings of the 3rd ACM SIGACT-SIGMOD Symposium on Principles of Database Systems. Waterloo, Ontario, Canada:ACM, 1984:181-190.
[27] DAI H K, SU H C. Locality and Clustering Performances of Space-filling Curves[M]. Stillwater, OK, USA:Oklahoma State University, 2003:78-85.
[28] MURRAY C. Spatial and Graph Developer's Guide[DB/OL]. https://docs.oracle.com/database/121/SPATL/, 2017-01/2017-11.
[29] MURRAY C. Oracle Spatial User's Guide and Reference, Release 9.2[DB/OL], https://docs.oracle.com/cd/B10501_01/appdev.920/a96630.pdf, 2002-03/2017-11.
[30] RAVADA S, KAZAR B M, KOTHURI R. Query Processing in 3D Spatial Databases:Experiences with Oracle Spatial 11g[M]//LEE J, ZLATANOVA S. 3D Geo-information Sciences. Berlin:Springer, 2009:153-173.
[31] STOTER J E, ZLATANOVA S. 3D GIS, Where are We Standing?[C]//ISPRS Joint Workshop on ‘Spatial, Temporal and Multi-dimensional Data Modelling and Analysis’. Québec:ISPRS, 2003.
[32] BRAKATSOULAS S, PFOSER D, TRYFONA N. Modeling, Storing and Mining Moving Object Databases[C]//Proceedings of 2004 International Database Engineering and Applications Symposium. Coimbra:IEEE, 2004:68-77.

三维空间格网的多尺度整数编码与数据索引方法

Multiscale Integer Coding and Data Index of 3D Spatial Grid

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	吴宇豪, 曹雪峰, 余岸竹, 孙万忠. 三维Hilbert曲线层级演进模型与编码计算[J]. 测绘学报, 2022, 51(1): 104-114.
[2]	赵学胜, 贲进, 孙文彬, 童晓冲. 地球剖分格网研究进展综述[J]. 测绘学报, 2016, 45(S1): 1-14.