Adaptive Hexagonal Hierarchical Grid for Point-in-spherical-polygon Tests
Author:
Affiliation:

Clc Number:

TP391

  • Article
  • | |
  • Metrics
  • |
  • Reference [42]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    Point-in-spherical-polygon tests are highly required in global data processing. For this reason, this study proposes an adaptive hexagonal hierarchical grid, which overcomes the difficulty of existing hexagonal hierarchical grids in adaptively subdividing grid cells, and applies it to point-in-spherical-polygon tests. First, the initial spherical hexagonal grid is built by uniformly partitioning a sphere using a regular icosahedron. Then, hierarchical grids are constructed by adaptively subdividing hexagonal cells according to whether a grid contains many polygon edges. As a result, the cells not subdivided contain no or only a few edges, called leaf cells. Finally, pre-computing is performed to determine the location attributes (inside/outside the polygon) of such cells or their center points. In the hierarchical structures, the topologies of related points, edges and faces between adjacent hexagonal grid levels are recorded, by which the leaf cells can be quickly located. For a test point, the leaf cell containing it is found quickly, and then whether it is located in the polygon is determined according to the local situation of the cell. Experimental results show that the proposed method has more stable and efficient performance than the existing methods.

    Reference
    [1] Li J, Zhang H, Wang WC. Fast and robust Point-in-Spherical-Polygon tests using multilevel spherical grids. In: Proc. of the 3rd Int’l Workshop on Next Generation Computer Animation Techniques. Bournemouth: Springer, 2017. 56–66.
    [2] Bevis M, Chatelain JL. Locating a point on a spherical surface relative to a spherical polygon of arbitrary shape. Mathematical Geology, 1989, 21(8): 811–828. [doi: 10.1007/BF00894449]
    [3] Manber U. Introduction to Algorithms: A Creative Approach. Reading: Addison-Wesley, 1989. 266–270.
    [4] Žalik B, Kolingerova I. A cell-based point-in-polygon algorithm suitable for large sets of points. Computers & Geosciences, 2001, 27(10): 1135–1145. [doi: 10.1016/S0098-3004(01)00037-1]
    [5] Li J, Wang WC. Point-in-polygon tests by determining grid center points in advance. In: Proc. of the 2013 Asia-Pacific Signal and Information Processing Association Annual Summit and Conf. IEEE, 2013. 1–7.
    [6] Brooks DR. Grid systems for earth radiation budget experiment applications. Technical memorandum, Hampton: National Aeronautics and Space Administration, 1981.
    [7] Sahr K. Hexagonal discrete global grid systems for geospatial computing. Archives of Photogrammetry, Cartography and Remote Sensing, 2011, 6(22): 363–376.
    [8] Xie JR, Yu HF, Ma KL. Interactive ray casting of geodesic grids. Computer Graphics Forum, 2013, 32(3pt4): 481–490. [doi: 10.1111/cgf.12135]
    [9] Xie JR, Yu HF, Ma KL. Visualizing large 3D geodesic grid data with massively distributed GPUs. In: Proc. of the 4th IEEE Symp. on Large Data Analysis and Visualization. Paris: IEEE, 2014. 3–10.
    [10] Brodsky I. H3: Uber’s hexagonal hierarchical spatial index. 2018. https://eng.uber.com/h3/
    [11] H3: Hexagonal hierarchical geospatial indexing system. https://github.com/mayhemheroes/h3-1
    [12] 韦程. 基于球面六边形网格系统的空间数据表达研究[硕士学位论文]. 南京: 南京师范大学, 2008.
    Wei C. Research on the representation of spatial data based on spherical hexagonal grid system [MS. Thesis]. Nanjing: Nanjing Normal University, 2008 (in Chinese with English abstract).
    [13] Hastings DA, Dunbar PK. Development & assessment of the global land one-km base elevation digital elevation model (GLOBE). In: Proc. of the ISPRS Commission IV Symp. on GIS— Between Visions and Applications. Stuttgart: ISPRS, 1998. 218–221.
    [14] Tobler W, Chen ZT. A quadtree for global information storage. Geographical Analysis, 1986, 18(4): 360–371. [doi: 10.1111/j.1538-4632.1986.tb00108.x]
    [15] Bjørke JT, Grytten JK, Hæger M, Nilsen S. A global grid model based on “constant area” quadrilaterals. In: Proc. of the 9th Scandinavian Research Conf. on Geographical Information Science. Espoo: Helsinki University of Technology, 2003. 239–250.
    [16] Google Inc. Google earth. https://google-earth.gosur.com/cn/
    [17] NASA. WorldWind Java. http://worldwind.arc.nasa.gov/java/
    [18] Schwartz J. Bing maps tile system. 2018. https://docs.microsoft.com/en-us/bingmaps/articles/bing-maps-tile-system
    [19] Mahdavi-Amiri A, Alderson T, Samavati F. A survey of digital earth. Computers & Graphics, 2015, 53: 95–117. [doi: 10.1016/j.cag.2015.08.005]
    [20] White D. Global grids from recursive diamond subdivisions of the surface of an octahedron or icosahedron. Environmental Monitoring and Assessment, 2000, 64(1): 93–103. [doi: 10.1023/A:1006407023786]
    [21] Vince A. Indexing the aperture 3 hexagonal discrete global grid. Journal of Visual Communication and Image Representation, 2006, 17(6): 1227–1236. [doi: 10.1016/j.jvcir.2006.04.003]
    [22] Goodchild MF, Shiren Y. A hierarchical spatial data structure for global geographic information systems. CVGIP: Graphical Models and Image Processing, 1992, 54(1): 31–44. [doi: 10.1016/1049-9652(92)90032-S]
    [23] 童晓冲, 贲进, 张永生. 全球多分辨率六边形网格剖分及地址编码规则. 测绘学报, 2007, 36(4): 428–435.
    Tong XC, Ben J, Zhang YS. The subdivision of global multi-resolution hexagonal grid and the rules of address coding. Acta Geodaetica et Cartographica Sinica, 2007, 36(4): 428–435 (in Chinese with English abstract).
    [24] Sahr K. Location coding on icosahedral aperture 3 hexagon discrete global grids. Computers, Environment and Urban Systems, 2008, 32(3): 174–187. [doi: 10.1016/j.compenvurbsys.2007.11.005]
    [25] Sahr K, White D, Kimerling JA. Geodesic discrete global grid systems. Cartography and Geographic Information Science, 2003, 30(2): 121–134. [doi: 10.1559/152304003100011090]
    [26] Amiri AM, Alderson T, Samavati F. Geospatial data organization methods with emphasis on aperture-3 hexagonal discrete global grid systems. Cartographica: The International Journal for Geographic Information and Geovisualization, 2019, 54(1): 30–50. [doi: 10.3138/cart.54.1.2018-0010]
    [27] 王蕊, 贲进, 杜灵瑀, 周建彬, 李祝鑫. 平面四孔六边形格网系统编码运算. 测绘学报, 2018, 47(7): 1018–1025. [doi: 10.11947/j.AGCS.2018.20170374]
    Wang R, Ben J, Du LY, Zhou JB, Li ZX. Encoding and operation for the planar aperture 4 hexagon grid system. Acta Geodaetica et Cartographica Sinica, 2018, 47(7): 1018–1025 (in Chinese with English abstract). [doi: 10.11947/j.AGCS.2018.20170374]
    [28] Wang R, Ben J, Zhou JB, Zheng MY. Indexing mixed aperture icosahedral hexagonal discrete global grid systems. ISPRS International Journal of Geo-Information, 2020, 9(3): 171. [doi: 10.3390/ijgi9030171]
    [29] Ivrissimtzis IP, Dodgson NA, Sabin MA. A generative classification of mesh refinement rules with lattice transformations. Computer Aided Geometric Design, 2004, 21(1): 99–109. [doi: 10.1016/j.cagd.2003.08.001]
    [30] Thuburn J. A PV-based shallow-water model on a hexagonal-icosahedral grid. Monthly Weather Review, 1997, 125(9): 2328–2347. [doi: 10.1175/1520-0493(1997)125<2328:APBSWM>2.0.CO;2]
    [31] Vince A, Zheng X. Arithmetic and Fourier transform for the PYXIS multi-resolution digital earth model. International Journal of Digital Earth, 2009, 2(1): 59–79. [doi: 10.1080/17538940802657694]
    [32] Tong XC, Ben J, Wang Y, Zhang YS, Pei T. Efficient encoding and spatial operation scheme for aperture 4 hexagonal discrete global grid system. International Journal of Geographical Information Science, 2013, 27(5): 898–921. [doi: 10.1080/13658816.2012.725474]
    [33] Uher V, Gajdoš P, Snášel V, Lai YC, Radecký M. Hierarchical hexagonal clustering and indexing. Symmetry, 2019, 11(6): 731. [doi: 10.3390/sym11060731]
    [34] Patel A. Red blob games—Hexagonal grids. http://www.redblobgames.com/grids/hexagons/
    [35] Mahdavi-Amiri A, Harrison E, Samavati F. Hexagonal connectivity maps for digital earth. International Journal of Digital Earth, 2015, 8(9): 750–769. [doi: 10.1080/17538947.2014.927597]
    [36] Harrison EE. Equal area spherical subdivision [MS. Thesis]. Calgary: University of Calgary, 2012.
    [37] Regular icosahedron. https://www.simpleplanes.com/a/04ZPeo/Regular-Icosahedron
    [38] 孙家广. 计算机图形学. 第3版, 北京: 清华大学出版社, 1998. 185–187.
    Sun JG. Computer Graphics. 3rd ed., Beijing: Tsinghua University Press, 1998. 185–187 (in Chinese).
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

李静,王文成.基于六边形的自适应层次网格及其应用于点在球面多边形内的判断.软件学报,2022,33(9):3485-3497

Copy
Share
Article Metrics
  • Abstract:750
  • PDF: 2389
  • HTML: 2173
  • Cited by: 0
History
  • Received:September 02,2020
  • Revised:November 10,2020
  • Online: July 15,2022
  • Published: September 06,2022
You are the first2044634Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063