Spatial Knowledge and Information Canada, 2019, 7(6), 1 Discrete Global Grid Systems: Operational Capability of the Current State of the Art BEN BONDARUK STEVEN A. ROBERTS COLIN R OBERTSON Department of Geography & Department of Geography & Department of Geography & Environmental Management Environmental Studies Environmental Studies University of Waterloo, Wilfrid Laurier University Wilfrid Laurier University Department of Geography & sroberts@wlu.ca crobertson@wlu.ca Environmental Studies Wilfrid Laurier University vbondaruk@uwaterloo.ca essential. As a result, new methods for ABSTRACT integrating, transmitting and representing The paper compares two current spatial data are required. Discrete Global implementations of Discrete Global Grid Grid Systems (DGGS) have been proposed Systems as potential new data models for as a new model for spatial data spatial data representation, integration, and representation, integration and analysis analysis. It outlines suitability of such suited to the current data-rich environment structures for spatial data modelling and (Li, 2013; Mahdavi-Amiri et el., 2016). GIS applications, as well as documents the DGGS are hierarchical tessellations of core criteria necessary for their successful regular shaped polygons (Figure 1.0) implementation. An experimental analysis initially designed as a global reference is performed in order to determine the system for mapping and navigational current state of their development and their purposes (Purss, Gibb, Samavati, Peterson practical applicability for data integration, & Ben, 2016). analysis and visualization. The work concludes with a reflection on the current implementations compared to the industry standards and some future projections of geospatial analysis within Discrete Global Grid Systems framework. 1. Introduction Spatial data handling and integration has become one of the prevailing needs in geospatial analysis and computation. In the modern digital context spatial data are usually collected and stored as either raster or vector representations, along with attribute data for these spatial features (Mahdavi-Amiri, Alderson & Samavati, 2016). These representations have evolved to serve a number of specialist communities and workflows in GIS analysis (e.g., Figure 1.0. Example of a hierarchical structure of the Earth satellite-based remote sensing); however surface using hexagon shapes for the cell refinement generated with continuing increases in spatial data for the purposes of this study. heterogeneity and volume, the necessity for efficient data integration has become 2 Discrete Global Grid Systems Over time, due to its discrete construction requirements of the selected software DGGS have also started to be used as a data libraries to the released OGC standards. It is structure for consistent storage, reference very likely that certain requirements might and analysis of spatial data and its attribute not be met by either of the software, information. DGGS suggest a different suggesting further advancing of DGGS approach for geospatial data handling that packages. Both H3 and OpenEAGGR are allows interoperability of resources and open source software available via the elimination of inaccurate and complex data GitHub source code repository (Uber, 2015; synthesis operations (Purss et el., 2016). Riskaware, 2017). In order for a grid network to qualify as For the testing purposes both libraries DGGS it must consist of core elements were built directly from their source in their documented and summarized in the Open natural development environments. This Geospatial Consortium (OGC) standard data step is necessary in order to gain access to protocol (Open Geospatial Consortium, the full list of available functionality, which 2017). The work of Goodchild and Kimerling might not be available through other (2002), on defining DGGS and some of their language bindings. In particular, the H3 core requirements, have contributed greatly library is built from its source using CMake to the overall advancement of this new data packaging software, Visual Studio standard; yet some of the earlier research on development environment with integrated DGGS had already begun in the 1980s C++ compiler; whereas OpenEAGGR is built (Dutton, 1984). Their initial ideas and using the MinGW compiler and Eclipse thoughts served as the basis for a fully development environment. In addition, functional and well-designed DGGS data JavaScript binding for H3 and Python standards set by OGC. OGC requirements binding for OpenEAGGR libraries were also were put in place in order to guarantee the used in order to evaluate their flexibility and explicit resolution, area preservation and ease of use. Although not a requirement the positional uniqueness at each level of libraries were also evaluated based on their hierarchy which account for scale availability for programing language differences and spatial distortion globally. bindings for the user’s convenience. In addition, the unique topological In this study the main focus is put on properties of regular shape tessellation hexagon shape structures due to their might also naturally suggest looking for new availability on both platforms, as well as forms of spatial analysis. The referencing their advantages in sampling, circularity, and indexing mechanisms, on the other packing and uniform connectivity properties hand, provide reliable methods to access, over the other regular shapes (e.g., triangles, store and retrieve data. As a result, various squares) (Li, 2013; Peterson, 2017). The algorithms might integrate the existing particular interest of this study is to evaluate indexing system for data assimilation via the the operational capability of both libraries. refinement methods using the above In other words, the aim is to test practical properties (Peterson, 2017; Purss el al., applications of available DGGS software for 2016). their basic functionality, such as importing The aim of this paper is an in-depth of spatial data, querying spatial analysis analysis of two DGGS implementation: the algorithms as well as exporting and H3 (Uber, 2015) and OpenEAGGR visualizing the end results. (Riskaware, 2017) open source software libraries. In addition, their operational and 3. Results practical applications are also reviewed. A summary of H3 and OpenEAGGR implementations compared to OGC 2. Methods standards is outlined in Table 1.0. The The following section outlines the existing DGGS software provide a methodology for comparing core data model comprehensive approach for geocoding, Discrete Global Grid Systems 3 indexing, addressing and processing consecutive cell’s location of a higher geospatial data into discrete forms. Due to resolution, whereas offset addressing uses their hierarchical structures, positional fixed axis orientation and offset distances uniqueness and discrete representation of from their origin to determine location of a spatial resolution, DGGS are gaining cell (Bush, 2017). Both implementations use popularity and acceptance in the modern an icosahedron as a base polyhedron for geospatial analysis and data integration. creating planar faces approximating a sphere. The grid partitioning method of H3 3.1 Technical specifications uses hexagon aperture 7, whereas OpenEAGGR incorporates both hexagon A detailed technical analysis show basic aperture 3 and triangle aperture 4 functionality of DGGS for modeling Earth’s hierarchical models (Uber, 2015; Riskaware, surface via hierarchical networks of equal 2017). Aperture is a method known to area cells. Both libraries support partition a DGGS cell using additional hierarchical tessellation of regular polygons partial self-similar shapes (e.g., hexagons) at increasingly fine resolutions up to a m 2 in order to preserve equal area property and cm2 in areal size for H3 and across multiple resolutions (Figure 2.0). OpenEAGGR respectively (Uber, 2015; Riskaware, 2017). Each cell has a unique index and is accessible throughout the hierarchies. The given software also provides functionality to convert from latitude-longitude coordinates to DGGS indexes and vice versa referencing all cell Figure 2.0. Hierarchical partition of space using hexagon centroids. apertures 3 (left), 4 (middle) and 7 (right) (Sahr, 2013). Since addressing and referencing are two major properties of DGGS (criteria 11-12) The results of this subsection indicate (Table 1.0) it is important to mention that that both implementations fail to meet the H3 and OpenEAGGR use hierarchy-based complete list of required criteria outlined by and offset coordinate addressing structure OGC and therefore cannot be classified as for hexagonal cell systems respectively. fully functional DGGS (Table 1.0). Hierarchical addressing is based on the lower resolution grid to find next Table 1.0: The following table outlines a core set of criteria to be met by software and classified as DGGS. The table also summarizes technical specifications of H3 and OpenEAGGR libraries and compares them to the OGC standards. Criteria OGC Requirement H3 OpenEAGGR Notes 1 Core Data Model () () This requirement includes definition of conceptual data model of DGGS Partial Partial including reference frame (criteria 2-13) and functional algorithms fulfillment fulfillment (criteria 14-18) elements, which are partially fulfilled by each library. 2 Area () () Guarantees the coverages of the entire globe. Each library fulfills the Fulfilled Fulfilled requirement for covering the entire surface of the earth. 3 Overlap () () Ensures positional uniqueness without overlapping cells. Theoretically, Fulfilled Not this requirement is met by both libraries; however practical application of fulfilled OpenEAGGR fails to meet the requirement (see Figure 3.0). 4 Tessellation () () Forms a sequence of hierarchical tessellations at multiple spatial sequence Fulfilled Fulfilled resolutions. Both libraries are capable of generating hierarchical grids at various resolutions. 5 Area preservation () () A total surface area must be preserved throughout hierarchical Fulfilled Not tessellations. The following requirement is not met by OpenEAGGR due fulfilled to the overlapping cells in criterion 3 and perhaps inconsistent geometry of the offset coordinate system. 4 Discrete Global Grid Systems Table 1.0: Continued. Criteria OGC Requirement H3 OpenEAGGR Notes 6 Shape () () DGGS cells must be formed of simple regular polygons. Both libraries Fulfilled Fulfilled have met the requirement with H3 using mostly hexagons and OpenEAGGR mostly hexagons and triangles (see criterion 8). 7 Equal area () () Any DGGS implementation will have equal area uncertainties of cells precision Not Partial caused by the factors such as converging calculation, the rate of fulfilled fulfillment convergence or the precision of real numbers (e.g., ) used to calculate DGGS cell geometry. H3 seems to omit such technical details for the computational precision of equal area cells, whereas OpenEAGGR summarizes some technical benchmarks in its prototype evaluation framework (Bush, 2017). 8 Equal area () () For each successive resolution equal area cells must be defined within the Fulfilled Fulfilled specified level of precision. Both libraries are constructed on the icosahedron with H3 using equal area hexagons and OpenEAGGR – hexagons and triangles. The only exception is that both hexagon grid libraries contain 12 pentagon cells centered at each icosahedron vertices and resolution. Pentagon cells are necessary in order to tile the sphere completely. 9 Initial tessellation () () The initial partition of a sphere must be specified as a base unit Fulfilled Fulfilled polyhedron. Both libraries meet the requirement and use an icosahedron as a base. 10 Refinement () () Cell refinement methods and maximum number of refinements must be (aperture) Fulfilled Fulfilled specified for each DGGS. H3 uses hexagonal aperture 7 grid partitioning method, whereas OpenEAGGR triangular aperture 4 and hexagonal aperture 3 cell partitioning. 11 Addressing () () A spatial referencing method for an assignment of a unique identifier Fulfilled Fulfilled (index) must be specified. H3 implements hierarchy-based indexing method, whereas OpenEAGGR uses hierarchical indexing for triangular and offset coordinate indexing for hexagonal cell systems. 12 Spatial reference () () A unique identifier must be assigned to each DGGS cell. Both libraries Fulfilled Fulfilled meet this requirement by assigning unique index to each DGGS cell using both hierarchical-based and offset coordinate indexing methods. 13 Cell centroid () () The location of each DGGS cell must be referenced by the location of Fulfilled Fulfilled their centroids. Both libraries meet this property. It was tested by converting random latitude-longitude coordinates to a DGGS cell and vice versa. The new output coordinates were assigned to the cell centroids. 14 Quantization () () Quantization methods for assigning and retrieval of data to individual Not Not DGGS cells must be documented; however such functionalities are not fulfilled fulfilled supported at this stage of the development. 15 Cell navigation () () Methods for hierarchical and neighbourhood navigation must be Fulfilled Partial provided. The H3 library is equipped with functions for navigating fulfillment between different resolutions and neighbouring cells. The OpenEAGGR library, however, does not support the neighbourhood query, but only the navigation queries through hierarchy. 16 Spatial analysis () () Methods for performing simple spatial analysis operations on the grids Not Fulfilled must be provided. At this stage of the development only OpenEAGGR fulfilled library is equipped with spatial analysis functions, such as equals, contains, intersects, etc. for two DGGS shape objects. 17 Query () () Methods for receiving, interpreting and processing data queries by DGGS Not Partial algorithms must be provided. The OpenEAGGR library supports fulfilled fulfillment integration with third party software, however those extensions are challenging to use due to the outdated technical support for the newer software releases. 18 Broadcast () () Methods for integration, processing and transmitting data to external Not Partial applications or web-based clients must be provided. The OpenEAGGR fulfilled fulfillment library also provides theoretical broadcasting functionality to external applications, however due to the limited technical support this property was not deployed in this study. Discrete Global Grid Systems 5 However, their applications are limited to their development environments and must be executed via direct function calls from within. In other words, the libraries do not support a user friendly interface. In addition, their practical applications for importing user data, performing spatial analysis as well as exporting and visualizing the end result still requires further development. The integration with other third party software should be more Figure 3.0. Example of the failed requirements for positional uniqueness and area preservation due to the overlapping cells effortless, with up-to-date technical support. generated via OpenEAGGR software library. On the bright side, both libraries provide seamless functionality of coordinate 3.2 Operational proficiency conversion to a DGGS cell indexes for individual point locations at different Both H3 and OpenEAGGR libraries resolutions, which is also illustrated in deliver a reasonable amount of functionality practice (Figures 4.0, 5.0). (Table 2.0) in order to meet basic DGGS requirements for operational capability of conversion, query and search across DGGS hierarchy. Table 2.0: Outlines the list of available language bindings, software extensions and API functions for H3 and OpenEAGGR libraries. Evaluation H3 OpenEAGGR Language Erlang C bindings Go C++ Java Java JavaScript Python OCaml PHP Python R Software PostgreSQL/PostGIS extensions Elasticsearch Basic API geoToH3 convertPointToDggsCell functions h3ToGeo convertShapesToDggsShapes h3ToGeoBoundary convertShapeStringToDggsSh h3GetResolution apes Figure 4.0. Conversion of Toronto’s latitude longitude h3GetBaseCell convertDggsCellToPoint coordinates into DGGS cells via H3 library. The images are at stringToH3 convertDggsCellsToPoints DGGS resolution 1 (top) and 14 (bottom), which are equivalent to h3ToString convertDggsCellsToShapeStri 2 2 the 6.3 m and 607,221 km average surface area. h3IsValid ng h3IsPentagon getCellParents kRing getCellChildren kRingDistances getCellSiblings h3ToParent getBoundingCell h3ToChildren createKmlFile compact convertDggsCellOutlineToSha uncompact peString polyfill compareShapes hexAreaKm2 hexAreaM2 numHexagons 6 Discrete Global Grid Systems Figure 5.0. Conversion of Toronto’s latitude longitude coordinates into DGGS cells via OpenEAGGR library. The 2 resolutions accuracy were approximated to 1000 m (top) and 2 1,000,000,000 km (bottom) of the surface area. Figure 6.0. Performing a search query of neighboring cells via H3 kRing function with ring distance of 10 (top) and 1 (bottom) from Cell navigation functionality is also well a cell of interest (black). implemented by the H3 library, which allows performing basic distance and search queries in order to identify and generate neighboring hexagons within a desired distance from a cell of interest (Figure 6.0). The OpenEAGGR library, however, lacks such functionality and only supports basic parent-child cell relationship (Figure 7.0). Furthermore, the developers indicate that parent-child queries perform significantly worse for hexagonal grids due to the implemented offset coordinate indexing system (Bush, 2017). With offset coordinates the parent-child identification is based purely on the grid geometry, which might lead to the sources of error for positional uniqueness and area preservation. As a result, it is suggested to use caution when integrating offset coordinate indexing system for DGGS implementation. Figure 7.0. Performing a parent search query via OpenEAGGR getCellParents function for high (top) and low (bottom) resolution cells. Discrete Global Grid Systems 7 In comparison, the H3 library does not The H3 library also supports more support built-in functionality for exporting advanced functionalities, such as filling shape geometries directly. As a result, a polygon areas with hexagons as well as script for converting such data objects into compressing them into more efficient GeoJSON file format was implemented representation (Figure 8.0). separately in order to visualize the output via third party applications such as Google Earth or geojson.io. EQUALS False CONTAINS False WITHIN False TOUCHES False DISJOINT False INTERSECTS True COVERS False COVERED_BY False Figure 8.0. The above figure demonstrates H3 functionality for CROSSES False tessellating area of interest (top) with hexagons (bottom, grey), OVERLAPS True as well as the ability to compact them into a more concise shape Figure 9.0. The above figure demonstrates output of spatial (bottom, blue) analysis queries performed on two DGGS cell shapes via Open EAGGR library. Although they are useful, these APIs might not be classified as spatial analysis functions for performing operations and determining 4. Conclusion relationship between DGGS cells. The Traditional spatial analysis includes OpenEAGGR, on the other hand, does multiple techniques to study geographic support spatial analysis APIs for shape phenomena by interacting with existing data comparison of DGGS cells, linestrings and related to a specific geographic location. polygons with variety of available operations Such data are then used to extract (Figure 9.0). meaningful information with the help of Visualization is not inherently available computer processing and applications. in the tested libraries. In other words, in Several problems might occur during such a order to visualize the output results the chain of events, but integration of multiple object or shape must be exported into one of data sources at once is an important aspect the available file formats, such as GeoJSON of the problem. DGGS set a benchmark for a or KML via OpenEAGGR APIs; however, more scalable and comprehensive data this functionality might not be applicable to handling that can be distributed across all DGGS shapes. If export is not possible different platforms and accessed via the the spatial data objects will remain stored in web, and therefore have been investigated in memory and could be accessed via direct detail in this paper. memory calls as a workaround. 8 Discrete Global Grid Systems Both H3 and OpenEAGGR software References deliver basic functionality of DGGS, Bush, I. (2017). OpenEAGGR literature however cannot be classified as such due to review & prototype evaluation. [online] the unfulfilled OGC requirements (Table Retrieved August 2018, from 1.0). It was found that H3 library is missing https://github.com/riskaware-ltd/open- some of the key functionality for assigning eaggr/blob/master/Documents/Literatur and retrieval of spatial data, data e%20Review%20%26%20Prototype%20 quantization as well as basic spatial Evaluation.pdf analysis, query and broadcasting Dutton, G. (1984). Part 4: Mathematical, functionalities. The OpenEAGGR library is Algorithmic and Data Structure Issues: more successful with spatial analysis, data Geodesic Modelling Of Planetary Relief. query and broadcasting implementations, Cartographica: The International yet still lacks support for data quantization Journal for Geographic Information and and some essential properties of positional Geovisualization, 21(2-3), 188-207. uniqueness and area preservation. doi:10.3138/r613-191u-7255-082n Both implementations provide great Goodchild, M. F, & Kimerling, A. (2002). variety of language bindings available for Discrete Global Grids: A Web Book. integration with third party applications Retrieved August 2018, from (Table 2.0), however not all of them are at https://escholarship.org/uc/item/9492q the same level of development. In terms of 6sm the current progress, it also seems that the Li, X. (2013). Storage and addressing H3 project undergoes more rapid scheme for practical hexagonal image development compared to the OpenEAGGR processing. Journal of Electronic and has greater functional availability. New Imaging, 22(1), 010502. doi:10.1117 H3 features and corrections are being /1.jei.22.1.010502 implemented regularly, and connections Mahdavi-Amiri, A., Alderson, T., & with other third party software continuously Samavati, F. (2016). Data Management explored for data query and broadcasting. Possibilities for Aperture 3 Hexagonal This includes Uber’s own operational needs Discrete Global Grid Systems. Retrieved for dynamic optimization of ride prices, as August 2018, from http://dx.doi.org well as spatial decision making on a city /10.5072/PRISM/30988 level (Uber, 2018). As of now, however, the Open Geospatial Consortium. (2017). current open source implementations are Discrete Global Grid Systems Abstract not at the point where they can be used at Specification. [online] Retrieved August the larger scales with convenience and 2018, from http://docs.opengeospatial. minimal technical experience. org/as/15-104r5/15-104r5.html. Therefore, all these components should Peterson, P. (2017). Discrete Global Grid receive additional attention in order to Systems. International Encyclopedia Of make them more practical and possible for Geography: People, The Earth, average users to tailor for their specific Environment And Technology, 1-10. doi: needs. Once accomplished, however, it is 10.1002/9781118786352.wbieg1050 very likely that DGGS will set new standards Purss, M., Gibb, R., Samavati, F., Peterson, for geospatial analysis and open up new P., & Ben, J. (2016). The OGC® Discrete research prospects. Global Grid System core standard: A framework for rapid geospatial Acknowledgements integration. 2016 IEEE International This work was funded by the Global Geoscience And Remote Sensing Water Futures Programme through the Symposium (IGARSS). doi: 10.1109 Global Water Citizenship Project. /igarss.2016.7729935 Discrete Global Grid Systems 9 Riskaware Ltd. (2017). OpenEAGGR (Open Uber Technologies Inc. (2015). H3: A Equal Area Global GRid). Retrieved hexagonal hierarchical geospatial August 2018, from https://github.com indexing system. Retrieved August 2018, /riskaware-ltd/open-eaggr/ from https://uber.github.io/h3/#/ Sahr, K. (2013). On the Optimal Uber Technologies Inc. (2018). H3: Uber’s Representation of Vector Location using hexagonal hierarchical spatial index. Fixed-Width Multi-Precision Quantizers. Retrieved November 2018, from ISPRS - International Archives of the https://eng.uber.com/h3/ Photogrammetry, Remote Sensing and Spatial Information Sciences, XL-4/W2, 1-8. doi:10.5194/isprsarchives-xl-4-w2-1- 2013