{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T15:14:44Z","timestamp":1774365284190,"version":"3.50.1"},"reference-count":57,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2024,10,22]],"date-time":"2024-10-22T00:00:00Z","timestamp":1729555200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Natural Sciences and Engineering Research Council of Canada (NSERC)","award":["RGPIN-2018-03935"],"award-info":[{"award-number":["RGPIN-2018-03935"]}]},{"name":"Natural Sciences and Engineering Research Council of Canada (NSERC)","award":["IT32593"],"award-info":[{"award-number":["IT32593"]}]},{"DOI":"10.13039\/501100004489","name":"Mitacs","doi-asserted-by":"publisher","award":["RGPIN-2018-03935"],"award-info":[{"award-number":["RGPIN-2018-03935"]}],"id":[{"id":"10.13039\/501100004489","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004489","name":"Mitacs","doi-asserted-by":"publisher","award":["IT32593"],"award-info":[{"award-number":["IT32593"]}],"id":[{"id":"10.13039\/501100004489","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Recent advancements in geospatial technologies have significantly expanded the volume and diversity of geospatial data, unlocking new and innovative applications that require novel Geographic Information Systems (GIS). (Discrete) Global Grid Systems (DGGSs) have emerged as a promising solution to further enhance modern geospatial capabilities. Current DGGSs employ a simple, low-resolution polyhedral approximation of the Earth for efficient operations, but require a projection between the Earth\u2019s surface and the polyhedral faces. Equal-area DGGSs are desirable for their low distortion, but they fall short of this promise due to the inefficiency of equal-area projections. On the other hand, efficiency-first DGGSs need to better address distortion. We introduce a novel mesh-based DGGS (MBD) which generalizes efficient operations over watertight triangular meshes with spherical topology. Unlike traditional approaches that rely on Platonic or Catalan solids, our mesh-based method leverages high-resolution spherical meshes to offer greater flexibility and accuracy. MBD allows high-resolution polyhedra (HRP) to be used as the base polyhedron of a DGGS, significantly reducing distortion. To address the operational challenges, we introduce a new hash encoding method and an efficient barycentric indexing method (BIM). MBD extends Atlas of Connectivity Maps to the BIM to provide efficient spatial and hierarchical traversal. We introduce several new base polyhedra with lower areal and angular distortion, and we experimentally validate their properties and demonstrate their efficiency. Our experimentation shows that we achieve constant-time operations for high-resolution MBD, and we recommend polyhedra to be used as the base polyhedron for low-distortion DGGSs, compact faces, and efficient operations.<\/jats:p>","DOI":"10.3390\/ijgi13110373","type":"journal-article","created":{"date-parts":[[2024,10,22]],"date-time":"2024-10-22T11:31:57Z","timestamp":1729596717000},"page":"373","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Constructing Efficient Mesh-Based Global Grid Systems with Reduced Distortions"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5253-7238","authenticated-orcid":false,"given":"Lakin","family":"Wecker","sequence":"first","affiliation":[{"name":"Department of Computer Science, Faculty of Science, University of Calgary, Calgary, AB T 2N 1N4, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Hall","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Faculty of Science, University of Calgary, Calgary, AB T 2N 1N4, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9440-7562","authenticated-orcid":false,"given":"Faramarz F.","family":"Samavati","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Faculty of Science, University of Calgary, Calgary, AB T 2N 1N4, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,10,22]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1080\/19475683.2018.1424737","article-title":"Reimagining the History of GIS","volume":"24","author":"Goodchild","year":"2018","journal-title":"Ann. GIS"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Alderson, T., Purss, M., Du, X., Mahdavi-Amiriand, A., and Samavati, F. (2019). Chapter on Digital Earth Platforms. Manual of Digital Earth, Springer.","DOI":"10.1007\/978-981-32-9915-3_2"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/j.cag.2019.05.029","article-title":"Multiscale NURBS Curves on the Sphere and Ellipsoid","volume":"82","author":"Alderson","year":"2019","journal-title":"Comput. Graph."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1080\/20964471.2022.2094926","article-title":"Area and shape distortions in open-source discrete global grid systems","volume":"6","author":"Kmoch","year":"2022","journal-title":"Big Earth Data"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"e15021","DOI":"10.1111\/cgf.15021","article-title":"GLS-PIA: N-Dimensional Spherical B-Spline Curve Fitting based on Geodesic Least Square with Adaptive Knot Placement","volume":"Volume 43","author":"Zhao","year":"2024","journal-title":"Computer Graphics Forum"},{"key":"ref_6","unstructured":"Veach, E. (2023, August 13). S2 Geometry. Available online: https:\/\/s2geometry.io\/."},{"key":"ref_7","unstructured":"Uber (2023, August 13). H3: Uber\u2019s Hexagonal Hierarchical Spatial Index. Available online: https:\/\/www.uber.com\/en-CA\/blog\/h3\/."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Harrison, E., Mahdavi-Amiri, A., and Samavati, F. (2011, January 4\u20136). Optimization of Inverse Snyder Polyhedral Projection. Proceedings of the 2011 International Conference on Cyberworlds (CW), Calgary, AB, Canada. IEEE Computer Society.","DOI":"10.1109\/CW.2011.36"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/978-3-642-32663-9_8","article-title":"Analysis of Inverse Snyder Optimizations","volume":"Volume 7380","author":"Gavrilova","year":"2012","journal-title":"Transactions on Computational Science XVI"},{"key":"ref_10","first-page":"1","article-title":"Real-time 3D reconstruction at scale using voxel hashing","volume":"32","author":"Izadi","year":"2013","journal-title":"ACM Trans. Graph. (ToG)"},{"key":"ref_11","first-page":"1","article-title":"Instant neural graphics primitives with a multiresolution hash encoding","volume":"41","author":"Evans","year":"2022","journal-title":"ACM Trans. Graph. (ToG)"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"5404","DOI":"10.1109\/TVCG.2023.3293121","article-title":"Interactive Volume Visualization Via Multi-Resolution Hash Encoding Based Neural Representation","volume":"30","author":"Wu","year":"2023","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.cag.2015.08.005","article-title":"A survey of digital earth","volume":"53","author":"Alderson","year":"2015","journal-title":"Comput. Graph."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.cag.2014.01.001","article-title":"Atlas of Connectivity Maps","volume":"39","author":"Samavati","year":"2014","journal-title":"Comput. Graph."},{"key":"ref_15","first-page":"69","article-title":"Discrete Global Grid Systems","volume":"30","author":"Sahr","year":"1998","journal-title":"Comput. Sci. Stat."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1559\/152304099782294186","article-title":"Comparing Geometrical Properties of Global Grids","volume":"26","author":"Kimerling","year":"1999","journal-title":"Cartogr. Geogr. Inf. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1130","DOI":"10.1111\/tgis.13173","article-title":"A general modeling scheme for spatiotemporal DGGS with emphasis on encoding and operating multiscale time grids","volume":"28","author":"Zhou","year":"2024","journal-title":"Trans. GIS"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Miao, S., Cheng, C., Zhai, W., Ren, F., Zhang, B., Li, S., Zhang, J., and Zhang, H. (2019). A Low-Altitude Flight Conflict Detection Algorithm Based on a Multilevel Grid Spatiotemporal Index. ISPRS Int. J. Geo-Inf., 8.","DOI":"10.3390\/ijgi8060289"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Fichtner, F., Mandery, N., Wieland, M., Groth, S., Martinis, S., and Riedlinger, T. (2023). Time-series analysis of Sentinel-1\/2 data for flood detection using a discrete global grid system and seasonal decomposition. Int. J. Appl. Earth Obs. Geoinf., 119.","DOI":"10.1016\/j.jag.2023.103329"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Kazemi, M., and Samavati, F.F. (2023). Automatic Soil Sampling Site Selection in Management Zones Using a Multi-Objective Optimization Algorithm. Agriculture, 13.","DOI":"10.3390\/agriculture13101993"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/s10291-022-01354-9","article-title":"An improved global grid model for calibrating zenith tropospheric delay for GNSS applications","volume":"27","author":"Huang","year":"2023","journal-title":"GPS Solut."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Zhai, W., Tong, X., Miao, S., Cheng, C., and Ren, F. (2019). Collision Detection for UAVs Based on GeoSOT-3D Grids. ISPRS Int. J. Geo-Inf., 8.","DOI":"10.3390\/ijgi8070299"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1038\/s41597-024-03354-5","article-title":"Employing discrete global grid systems for reproducible data obfuscation","volume":"11","author":"Caspari","year":"2024","journal-title":"Sci. Data"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1109\/MCG.2017.38","article-title":"Physical Visualization of Geospatial Datasets","volume":"38","author":"Djavaherpour","year":"2017","journal-title":"IEEE Comput. Graph. Appl."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1109\/TVCG.2018.2864503","article-title":"Visual Abstraction of Large Scale Geospatial Origin-Destination Movement Data","volume":"25","author":"Zhou","year":"2019","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"2641","DOI":"10.1109\/TVCG.2020.3037226","article-title":"Exploratory Volumetric Deep Earth Visualization by 2.5D Interactive Compositing","volume":"28","author":"Morse","year":"2022","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1080\/20964471.2021.2017539","article-title":"EASE-DGGS: A hybrid discrete global grid system for Earth sciences","volume":"6","author":"Thompson","year":"2022","journal-title":"Big Earth Data"},{"key":"ref_28","unstructured":"(2023, October 23). Bing Maps Tile System. Available online: https:\/\/learn.microsoft.com\/en-us\/bingmaps\/articles\/bing-maps-tile-system."},{"key":"ref_29","unstructured":"Google-Maps-Contributors (2023, October 23). Google Maps 2D Tiles Overview. Available online: https:\/\/developers.google.com\/maps\/documentation\/tile\/2d-tiles-overview."},{"key":"ref_30","unstructured":"OSM-Wiki-Contributors (2023, October 23). Open Street Map Quad Tiles. Available online: https:\/\/wiki.openstreetmap.org\/wiki\/QuadTiles."},{"key":"ref_31","unstructured":"Song, L., Kimerling, A.J., and Sahr, K. (2002). Developing an Equal Area Global Grid by Small Circle Subdivision, National Center for Geographic Information & Analysis."},{"key":"ref_32","unstructured":"Szalay, A.S., Gray, J., Fekete, G., Kunszt, P.Z., Kukol, P., and Thakar, A. (2007). Indexing the sphere with the hierarchical triangular mesh. arXiv."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Hall, J., Wecker, L., Ulmer, B., and Samavati, F. (2020). Disdyakis Triacontahedron DGGS. ISPRS Int. J. Geo-Inf., 9.","DOI":"10.3390\/ijgi9050315"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Mukundan, R. (2022). Mesh Tessellation. 3D Mesh Processing and Character Animation: With Examples Using OpenGL, OpenMesh and Assimp, Springer.","DOI":"10.1007\/978-3-030-81354-3"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"320","DOI":"10.3390\/ijgi4010320","article-title":"Categorization and Conversions for Indexing Methods of Discrete Global Grid Systems","volume":"4","author":"Samavati","year":"2015","journal-title":"ISPRS Int. J. Geo-Inf."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.cad.2016.04.005","article-title":"Hierarchical grid conversion","volume":"79","author":"Harrison","year":"2016","journal-title":"Comput.-Aided Des."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Bebis, G., Boyle, R., Parvin, B., Koracin, D., Li, B., Porikli, F., Zordan, V., Klosowski, J., Coquillart, S., and Luo, X. (2013). One-to-Two Digital Earth. Advances in Visual Computing, Springer.","DOI":"10.1007\/978-3-642-41939-3"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Gibb, R. (2016). The rHEALPix discrete global grid system. E&ES, 34.","DOI":"10.1088\/1755-1315\/34\/1\/012012"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Ben, J., Tong, X., and Chen, R. (2010, January 18\u201320). A spatial indexing method for the hexagon discrete global grid system. Proceedings of the 2010 18th International Conference on Geoinformatics, Beijing, China.","DOI":"10.1109\/GEOINFORMATICS.2010.5567972"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"64210J","DOI":"10.1117\/12.712679","article-title":"Discrete global grid systems: Generating algorithm and software model","volume":"Volume 6421","author":"Ben","year":"2006","journal-title":"Proceedings of the Geoinformatics 2006: Geospatial Information Technology"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Tong, X., Ben, J., and Wang, Y. (2010, January 18\u201320). A new effective hexagonal discrete global grid system: Hexagonal quad balanced structure. Proceedings of the 2010 18th International Conference on Geoinformatics, Beijing, China.","DOI":"10.1109\/GEOINFORMATICS.2010.5567908"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1080\/13658816.2017.1391389","article-title":"A discrete global grid system for earth system modeling","volume":"32","author":"Lin","year":"2018","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1080\/04353676.1974.11879899","article-title":"A system of domains for global sampling problems","volume":"56","author":"Wickman","year":"1974","journal-title":"Geogr. Ann. Ser. A Phys. Geogr."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Gorski, K.M., Hivon, E., Banday, A.J., Wandelt, B.D., Hansen, F.K., Reinecke, M., and Bartelmann, M. (2005). HEALPix: A Framework for High-Resolution Discretization and Fast Analysis of Data Distributed on the Sphere. Astrophys. J., 622.","DOI":"10.1086\/427976"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.cageo.2010.02.006","article-title":"Crusta: A new virtual globe for real-time visualization of sub-meter digital topography at planetary scales","volume":"37","author":"Bernardin","year":"2011","journal-title":"Comput. Geosci."},{"key":"ref_46","first-page":"16","article-title":"Central place indexing: Hierarchical linear indexing systems for mixed-aperture hexagonal discrete global grid systems","volume":"54","author":"Sahr","year":"2019","journal-title":"Cartogr. Int. J. Geogr. Inf. Geovisualization"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1080\/13658810110043603","article-title":"Continuous indexing of hierarchical subdivisions of the globe","volume":"15","author":"Goldsman","year":"2001","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1080\/17538947.2014.927597","article-title":"Hexagonal Connectivity Maps for Digital Earth","volume":"8","author":"Harrison","year":"2015","journal-title":"Int. J. Digit. Earth"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/j.compenvurbsys.2017.11.005","article-title":"Efficient encoding and decoding algorithm for triangular discrete global grid based on Hybrid Transformation Strategy","volume":"68","author":"Zhou","year":"2018","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_50","first-page":"10","article-title":"An Equal-Area Map Projection for Polyhedral Globes","volume":"29","author":"Snyder","year":"1992","journal-title":"Cartogr. Int. J. Geogr. Inf. Geovisualization"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1559\/152304006779500687","article-title":"A \u201cslice-and-dice\u201d approach to area equivalence in polyhedral map projections","volume":"33","author":"Strebe","year":"2006","journal-title":"Cartogr. Geogr. Inf. Sci."},{"key":"ref_52","first-page":"47","article-title":"Optimized spatial hashing for collision detection of deformable objects","volume":"Volume 3","author":"Teschner","year":"2003","journal-title":"Vmv"},{"key":"ref_53","unstructured":"Wikipedia contributors (2023, May 27). Line Plane Intersection. Available online: https:\/\/en.wikipedia.org\/wiki\/Line%E2%80%93plane_intersection."},{"key":"ref_54","unstructured":"Stutz, D. (2023, May 27). Learning Shape Completion from Bounding Boxes with Cad Shape Priors. Available online: https:\/\/davidstutz.de\/wordpress\/wp-content\/uploads\/2018\/04\/shape-completion-thesis2017.pdf."},{"key":"ref_55","doi-asserted-by":"crossref","unstructured":"Ericson, C. (2004). Real-Time Collision Detection, CRC Press.","DOI":"10.1201\/b14581"},{"key":"ref_56","unstructured":"Tissot, A. (1881). M\u00e9moire sur la Repr\u00e9sentation des Surfaces et les Projections des Cartes G\u00e9ographiques, Gauthier-Villars."},{"key":"ref_57","doi-asserted-by":"crossref","unstructured":"Snyder, J.P. (1987). Map Projections\u2014A Working Manual.","DOI":"10.3133\/pp1395"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/13\/11\/373\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T16:18:07Z","timestamp":1760113087000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/13\/11\/373"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,22]]},"references-count":57,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2024,11]]}},"alternative-id":["ijgi13110373"],"URL":"https:\/\/doi.org\/10.3390\/ijgi13110373","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,22]]}}}