=Paper=
{{Paper
|id=Vol-2323/SKI-Canada-2019-7-6-1
|storemode=property
|title=Discrete Global Grid Systems: Operational Capability of the Current State of the Art
|pdfUrl=https://ceur-ws.org/Vol-2323/SKI-Canada-2019-7-6-1.pdf
|volume=Vol-2323
|authors=Ben Bondaruk,Steven A. Roberts,Colin Robertson
}}
==Discrete Global Grid Systems: Operational Capability of the Current State of the Art==
https://ceur-ws.org/Vol-2323/SKI-Canada-2019-7-6-1.pdf
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