Encoding and Operation for the Planar Aperture 4 Hexagon Grid System

doi:10.11947/j.AGCS.2018.20170374

Abstract

Abstract: Discrete global grid system is a new data model which supports the fusion processing of multi-source geospatial information.Research into hexagon grid systems that have excellent geometric attributes has raised academic concern.Description of hierarchical relation and design of encoding scheme are research difficulties.According to the characteristics of the planar aperture 4 hexagon grid system, this paper designs an encoding scheme named Hexagon Lattice Quad Tree (HLQT).Code operations are defined, rules of them are generalized and based on these, transformation between 2-dimensional coordinates and addressing codes is implemented.Compared with similar schemes, HLQT overcomes the disadvantages caught by encoding schemes which divide the odd and even levels or mix the vertices and centers for encoding.In addition, operation rules of HLQT are simpler and easier for complementation.Contrast experiments show that the add operation efficiency of HLQT is about 6 times that of PYXIS and about 5 times that of HQBS, the efficiency of the transform algorithm from 2-dimensional coordinates to codes is about 5 times that of HQBS, and the efficiency of the transform algorithm from codes to 2-dimensional coordinates is about 3 times that of HQBS.

Key words: discrete global grid system, hexagon, addressing code, coordinate, transform

CLC Number:

P208

WANG Rui, BEN Jin, DU Lingyu, ZHOU Jianbin, LI Zhuxin. Encoding and Operation for the Planar Aperture 4 Hexagon Grid System[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(7): 1018-1025.

References

[1] GOODCHILD M F, YANG Shiren. A Hierarchical Spatial Data Structure for Global Geographic Information Systems[J]. CVGIP:Graphical Models and Images Processing, 1992, 54(1):31-44.
[2] SAHR K, WHITE D, KIMERLING A J. Geodesic Discrete Global Grid Systems[J]. Cartography and Geographic Information Science, 2003, 30(2):121-134.
[3] 贲进, 童晓冲, 周成虎, 等. 正八面体的六边形离散格网系统生成算法[J]. 地球信息科学学报, 2015, 17(7):789-797. BEN Jin, TONG Xiaochong, ZHOU Chenghu, et al. Construction Algorithm of Octahedron Based on Hexagon Grid Systems[J]. Journal of Geo-Information Science, 2015, 17(7):789-797.
[4] SAHR K. Hexagonal Discrete Global Grid Systems for Geospatial Computing[J]. Archives of Photogrammetry, Cartography and Remote Sensing, 2011, 22(2):363-376.
[5] BIRCH C P D, OOM S P, BEECHAM J A. Rectangular and Hexagonal Grids Used for Observation, Experiment and Simulation in Ecology[J]. Ecological Modelling, 2007, 206(3-4):347-359.
[6] LUCAS D. A Multiplication in N-Space[J]. Proceedings of the American Mathematical Society, 1979, 74(1):1-8.
[7] GIBSON L, LUCAS D. Spatial Data Processing Using Generalized Balanced Ternary[C]//Proceedings of IEEE Conference on Pattern Recognition and Image Processing. Las Vegas, Nevada:IEEE, 1982:566-571.
[8] MIDDLETON L, SIVASWAMY J. Hexagonal Image Processing:A Practical Approach[M]. London:Springer, 2005.
[9] SAHR K M. Discrete Global Grid Systems:A New Class of Geospatial Data Structures[D]. Ashland:University of Oregon, 2005:71-102.
[10] SAHR K. Location Coding on Icosahedral Aperture 3 Hexagon Discrete Global Grids[J]. Computers, Environment and Urban Systems, 2008, 32(3):174-187.
[11] PETERSON P. Close-packed, Uniformly Adjacent Multiresolutional, Overlapping Spatial Data Ordering:US, 8400451[P]. 2013-03-19.
[12] VINCE A, ZHENG X. Arithmetic and Fourier Transform for the PYXIS Multi-resolution Digital Earth Model[J]. International Journal of Digital Earth, 2009, 2(1):59-79.
[13] 贲进. 地球空间信息离散网格数据模型的理论与算法研究[D]. 郑州:信息工程大学, 2005. BEN Jin. A Study of the Theory and Algorithm of Discrete Global Grid Data Model for Geospatial Information Management[D]. Zhengzhou:Information Engineering University, 2005.
[14] 贲进, 童晓冲, 汪磊, 等. 利用球面离散格网组织空间数据的关键技术[J]. 测绘科学技术学报, 2010, 27(5):382-386. BEN Jin, TONG Xiaochong, WANG Lei, et al. Key Technologies of Geospatial Data Management Based on Discrete Global Grid System[J]. Journal of Geomatics Science and Technology, 2010, 27(5):382-386.
[15] 贲进, 童晓冲, 元朝鹏. 孔径为4的全球六边形格网系统索引方法[J]. 测绘学报, 2011, 40(6):785-789. BEN Jin, TONG Xiaochong, YUAN Chaopeng. Indexing Schema of the Aperture 4 Hexagonal Discrete Global Grid System[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(6):785-789.
[16] 童晓冲. 空间信息剖分组织的全球离散格网理论与方法[D]. 郑州:信息工程大学, 2010. TONG Xiaochong. The Principle and Methods of Discrete Global Grid Systems for Geospatial Information Subdivision Organization[D]. Zhengzhou:Information Engineering University, 2010.
[17] TONG Xiaochong, BEN Jin, WANG Ying, et al. Efficient Encoding and Spatial Operation Scheme for Aperture 4 Hexagonal Discrete Global Grid System[J]. International Journal of Geographical Information Science, 2013, 27(5):898-921.
[18] 贲进. 六边形格网系统的复进制数模型[R]. 第八届全国地图学与地理信息系统学术大会论文集, 南京:[s.n.], 2016. BEN Jin. The Model of Complex Number with a Radix System for the Hexagonal Grid System[C].Proceedings of the 8th National Conference on Cartography and Geography Information System, Nanjing:[s.n.], 2016.
[19] 张永生, 贲进, 童晓冲. 地球空间信息球面离散网格——理论、算法及应用[M]. 北京:科学出版社, 2007. ZHANG Yongsheng, BEN Jin, TONG Xiaochong. Discrete Global Grids for Geospatial Information:Principles, Methods and It's Applications[M]. Beijing:Science Press, 2007.
[20] 白建军. 基于正八面体的四孔六边形球面格网编码及索引[J]. 遥感学报, 2011, 15(6):1125-1137. BAI Jianjun. Location Coding and Indexing Aperture 4 Hexagonal Discrete Global Grid Based on Octahedron[J]. Journal of Remote Sensing, 2011, 15(6):1125-1137.
[21] VINCE A. Indexing the Aperture 3 Hexagonal Discrete Global Grid[J]. Journal of Visual Communication & Image Representation, 2006, 17(6):1227-1236.
[22] VINCE A. Indexing A Discrete Global Grid[C]//Special Topics in Computing and ICT Research, Advances in Systems Modelling and ICT Applications, Volume Ⅱ. Kampala:Fountain Publishers, 2006:3-17.
[23] BEN Jin, LI Yalu, ZHOU Chenghu, et al. Algebraic Encoding Scheme for Aperture 3 Hexagonal Discrete Global Grid System[J]. Science China Earth Sciences, 2018, 61(2):215-227.
[24] KNUTH D E. The Art of Computer Programming, Volume 2:Seminumerical Algorithms[M]. London:Addison-Wesley, 1969.
[25] GARRETT B, SAUNDERM L. A Survey of Modern Algebra[M]. 5th ed. Beijing:Posts & Telecom Press, 1977.