A fast grid generation algorithm for local irregular parts of hexagonal discrete global grid systems

ABSTRACT

Discrete Global Grid Systems (DGGS) provide a multi-resolution discrete representation of the Earth and are preferable for the organization, integration, and analysis of large and multi-source geospatial datasets. Generating grids for the area of interest is usually the premise and basis for DGGS applications. Owing to incongruent hierarchies that restrict the multi-resolution applications of hexagonal DGGS, current grid generation of hexagonal DGGS for local areas mainly depends on inefficient single-resolution traversal methods by judging the spatial relationship between each cell and the area. This study designs a fast generation algorithm for local parts of hexagonal DGGS based on the hierarchical properties of DGGS. A partition structure at intervals of multiple levels is first designed to ensure the coverage relevance between parent and children cells of different levels. Based on this structure, the algorithm begins with coarser resolution grids and recursively decomposes them into the target resolution, with multiple decomposition patterns used and a unique condition proposed to make the generated grids without gaps or overlaps. Efficient integer coordinate operations are used to generate the vast majority of cells. Experimental results show that the proposed algorithm achieves a significant improvement in efficiency. In the aperture 4 hexagonal DGGS, the efficiency ratio of the proposed and traversal algorithms increases from six times in level 14 to approximately 339 times in level 18. This study provides a solid foundation for subsequent data quantization and multi-resolution applications in hexagonal DGGS and has broad prospects.

KEYWORDS:

• Discrete global grid system
• hexagon
• local area
• grid generation
• multi-resolution

Acknowledgments

This work was supported by the Major Science and Technology Projects of Henan Province under Grant 201400210100 and the National Defense Science Innovation Special Zone Program under Grant 20-163-14-LZ-001-003-01. The authors would also like to thank the Editorial board and anonymous Reviewers for the review.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The data that support the findings of this study are available in figshare.com with the identifier(s) https://doi.org/10.6084/m9.figshare.19786348.v1.

Supplementary data

Supplemental data for this article can be accessed online at https://doi.org/10.1080/15230406.2023.2171492.

Additional information

Funding

The work was supported by the Major Science and Technology Projects of Henan Province [201400210100]; National Defense Science Innovation Special Zone Program [20-163-14-LZ-001-003-01].