i. Abstract

This document specifies the core Abstract Specification and extension mechanisms for Discrete Global Grid Systems (DGGS). A DGGS is a spatial reference system that uses a hierarchical tessellation of cells to partition and address the globe. DGGS are characterized by the properties of their cell structure, geo-encoding, quantization strategy and associated mathematical functions.The OGC DGGS Abstract Specification supports the specification of standardized DGGS infrastructures that enable the integrated analysis of very large, multi-source, multi-resolution, multi-dimensional, distributed geospatial data. Interoperability between OGC DGGS implementations is anticipated through implementation standards, and extension interface encodings of OGC Web Services.

ii.    Keywords

The following are keywords to be used by search engines and document catalogues.

ogcdoc, OGC document, Discrete Global Grid System, DGGS, Digital Earth, DGGS-core, Spatial Reference System, Global Data Structure, Geographic Information Systems, DE-9IM, standard, specification

iii.  Preface

This document specifies the core of an OGC Discrete Global Grid System Abstract Specification.

The intention of this Abstract Specification is to provide the geomatics and decision-making community with a formal document with which DGGS can be recognized, designed, built and used. This Abstract Specification defines the framework components that make up a compliant DGGS and the variability within those components.  The value of a DGGS as a spatial reference system is also discussed, as is the opportunity to interoperate between other DGGS and to utilize other OGC/ISO standards within the implementation of DGGS. As with any spatial reference, and especially an approach that is early in adoption, intellectual property rights pertaining to various methods of creating and using DGGS should be expected. For example, there exist multiple patents for indexing DGGS, and the implementers of this Abstract Specification should make themselves aware of these patents.

Attention is drawn to the possibility that some of the elements of this document may be the subject of patent rights. The Open Geospatial Consortium shall not be held responsible for identifying any or all such patent rights.

Recipients of this document are requested to submit, with their comments, notification of any relevant patent claims or other intellectual property rights of which they may be aware that might be infringed by any implementation of the Abstract Specification set forth in this document, and to provide supporting documentation.

iv. Submitting organizations

The following organizations submitted this Document to the Open Geospatial Consortium (OGC):

Geoscience Australia

Landcare Research New Zealand

University of Calgary

PYXIS

SpaceCurve

Zhengzhou Institute of Surveying & Mapping

ESRI

v. Submitters

All questions regarding this submission should be directed to the editor or the submitters:

Roger Lott’s significant contribution is acknowledged for his eleventh-hour assistance in working through the relationship between DGGS concepts and ISO concepts and for ensuring the document structure complies with both OGC and ISO requirements.

vi.   Introduction

A Discrete Global Grid System (DGGS) is designed as a framework for information as distinct from conventional coordinate reference systems originally designed for navigation. For a grid based global spatial information framework to operate effectively as an analytical system it should be constructed using cells that represent the surface of the Earth uniformly. This ensures that, at multiple resolutions, each cell has an equal probability of contributing to an analysis. A DGGS is a spatial reference system that uses a hierarchy of equal area tessellations to partition the surface of the Earth into grid cells or their analogous lattice points. In this way information recorded about phenomena at a location can be easily referenced to the explicit area of the associated cell, integrated with other cell values, and provides statistically valid summaries based on any chosen selection of cells. With equal area partitioning, spatial analysis can be replicated consistently anywhere on the Earth independent of resolution or scale.

OGC DGGS reference systems are polyhedral reference systems on the surface of a base unit polyhedron’s circumscribed ellipsoid. The base unit polyhedron’s location and orientation is defined in Earth Centered (EC) coordinates. The initial equal area tessellation of the chosen ellipsoidal Earth model is achieved by scaling a unit polyhedron of defined orientation until its vertices all touch the ellipsoid and connecting adjoining vertices with arcs selected from the set of permitted arcs, the simplest of which are geodesic, small circle or small ellipse arcs. Appropriate differential scaling is applied to the unit polyhedron to ensure an equal area initial tessellation. For the simple case of regular polyhedra and geodesic (i.e. great circle) arcs on its circumscribed spheroid the scaling is uniform. Figure 1 illustrates their simplest form using a regular spherical polyhedron with a spheroidal circumscribing ellipsoid and geodesic arcs. Small circle arcs are typically used to construct arcs along lines of latitude for both ellipsoids and spheroids. Both small circle and small ellipse arcs are formed from the intersection of a defined plane with the ellipsoid, and in that sense they can be considered equivalent to the ‘straight’ lines of 2D cell boundaries. More complex forms of straight line, such as arcs that project to a straight line in an equal area projection are also allowed.

There is a gap between conventional coordinate reference systems and the reference system needed to define DGGS. This OGC Abstract Specification fills the gap in existing OGC and ISO standard reference systems and establishes requirements for globally interoperable equal-area cell- or lattice-based information frameworks.

Existing spatial reference systems (e.g. ECEF [Earth Centered Earth Fixed], WGS 84 or Web Mercator) build grids from projected Cartesian or ellipsoidal coordinate axes. Rectangular planar grids are typically formed by establishing a set of regular ticks on a pair of linear axes with grids cells being formed by the intersection of straight lines drawn normal to the ticks on each axis. Analogous construction techniques can be used to create triangular or hexagonal grids. The properties of grids built this way arise from the premise of planar geometry and not the curved geometry of the surface of a sphere or ellipsoid. While these properties hold true at local scales, in curved geometries they increasingly fail at progressively larger regions of interest (see Figure 2). Take for example the assumption that a grid cell’s geometric properties are independent of its size or resolution – which is implicit in constructing sets of planar aligned (or ‘nested’) 10m, 30m and 90m grids. As shown in Figure 3, a 90m square cell formed from nine 30m square child cells has the following properties:

1. It is also square;
2. Its edges are three times the edge length of its 30m child cells, which in turn all are three times the edge length of their 10m child cells;
3. Its interior angles are all right angles and identical to the interior angles of all of the child cells;
4. Its edges follow the shortest linear path between neighboring cell vertices; and,
5. The angles or bearings from centroid to centroid between cells are preserved irrespective of the direction of travel.

On a curved surface, however, this is never the case, and yet we often make the same assumption; that all cells are geometrically identical in, for example, a country, or continental, wide mosaic comprising many satellite images. Consequently, under this paradigm assumption, choosing a fixed cell size for a global grid whose cells represent equal areas and seamlessly fit the earth’s surface is therefore problematic. When this is required, conventional spatial standards enforce latitude-longitude axes to be used and these grids are therefore described in these spherical coordinates. But the cells of these types of (equal-angular) grids do not have the same properties of planar grids. Figure 4 shows a similar consideration to that of Figure 3, only the grids are constructed using spherical instead of planar Cartesian coordinates. In this scenario, the largest (parent) cell does not necessarily have the same shape or internal angles as the child cells. Also, its edges do not follow the shortest linear path from corner to corner. Bearing directions between cell centroids, however, are preserved in both planar and curved geometry spaces.

In an attempt to address this dichotomy, conventional spatial standards therefore support either small local well-behaved planar grids or global grids that preserve bearings and angular lengths, and do not preserve area; but not both at the same time. This OGC Abstract Specification fills this gap by providing a formal specification for area preserving reference systems based on the surface model of the Earth that respect the accuracy and precision of spatial data at all scales from local to global.  These systems use a hierarchical tessellation of the entire Earth to produce equal-area grids. Figure 5 shows two examples.We anticipate that future extensions of the DGGS Core will support higher dimensions, such as the volume of the Earth and its atmosphere, and the Earth through time.

The language and foundations of current geospatial standards are deeply rooted in planar thinking, so while this OGC Abstract Specification leverages as much as it can from existing standards, it also introduces new concepts that are subtly yet fundamentally different from those described by the standards that it draws from. These subtle differences do challenge our thinking. As a consequence, this OGC Abstract Specification is an evolution of both existing raster processing practice and past usage of discrete global grids.

As a specification for an area preserving earth reference system this OGC Abstract Specification defines more than just grids and lattices. The underlying geometry of the cells and the topological relationships between neighboring cells can be used to define globally unique identifiers (GUIDs) for the cells at any resolution.

Earlier we noted that planar grids are formed from the pairs of axes each with regular ticks corresponding to the cell dimension, facilitating a simple topological referencing schema for each cell (usually via a matrix style index for each cell along the axes of the grid – i.e. rows and columns for a 2D grid). With DGGS we introduce a more sophisticated set of cell referencing schemas; such as, space filling curves that traverse all the cells in a manner that is functionally equivalent to the axes. As shown in Figure 6, cell indices are assigned to cells along the path of the space filling curve. These indices together with the geometry of the space filling curve carry the metrics of the curved surface and the topological relationships between neighboring cells. The cell indices are explicitly treated as GUIDs.

The mathematical properties of integers and real numbers on axis pairs in a plane are known implicitly and are therefore not part of any OGC specification for planar grids. The theoretical basis on which the separate disciplines for space filling curves, GUIDs, grids, spatial topology and DGGs are also well founded; however, their roles in a global reference frame defined through DGGS are not implicitly understood. This OGC Abstract Specification therefore defines these roles and relationships explicitly. This is a necessary departure from previous DGGS work that is needed to ensure a robust spatial reference frame standard. A brief history of DGGS is provided in Annex B for reference.

1. Scope

This OGC Abstract Specification defines the DGGS core data model and the core set of requirements to which every two dimensional OGC DGGS encoding must adhere. An OGC DGGS is a model of the entire Earth, using a hierarchical tessellation of equal-area cells that is analogous to a coordinate reference system. This OGC Abstract Specification does not prescribe any specific surface model of the Earth, polyhedron or class of polyhedra, but is intended to allow for a range of options that produce DGGS with compatible and interoperable functional characteristics.

This Abstract Specification defines:

1. A concise definition of the term Discrete Global Grid System as an earth centered spatial reference system comprised of spatial units of equal area;
2. The essential characteristics of a conformant DGGS; and,
3. The core functional algorithms required to support the operation of a conformant DGGS.

Extensions to the DGGS core Abstract Specification will add further functionality to the core requirements. In particular, DGGS extensions to the core will be required to support additional functional capabilities and interoperability using OGC Web Service (OWS) architectures, such as OGC Web Coverage Service (WCS) and Web Coverage Processing Service (WCPS) interfaces. This Abstract Specification anticipates:

The creation of a registration system for DGGS analogous to the registration for Coordinate Reference Systems (CRS); The elaboration of extensions to the core Abstract Specification to define additional functional algorithms and/or schemas that will support interoperability protocols through multi-DGGS processing operations; Potential additions and follow-on additions to other specifications; and The elaboration of the core requirements to specify higher dimensional DGGS as either a subsequent version of this Abstract Specification, or as an extension to the core Abstract Specification.

Every endeavor is made to use terms and data models from ISO19111, ISO19112 and ISO19115. However, DGGS are just sufficiently different to preclude use of many existing terms. Patterns are inherited from ISO data models but with redefined classes and their associations. Some of the fundamental differences are highlighted by the need to introduce DGGS coordinate reference system, geodetic identifier, and ellipsoidal polygons in order to distinguish them from their ISO equivalents of geodetic coordinate reference system, geographic identifier, and geodesic polygons.

2. Conformance

This Abstract Specification defines a single requirements class, core, of http://www.opengis.net/spec/dggs/1.0/req/core with a single pertaining conformance class, core, with URI http://www.opengis.net/spec/dggs/1.0/conf/core.

Conformance with this Abstract Specification shall be checked using all the relevant tests specified in Annex A (normative) of this document. The framework, concepts, and methodology for testing, and the criteria to be achieved to claim conformance are specified in the OGC Compliance Testing Policies and Procedures [OGC 08-134r10] and the OGC Compliance Testing web site ^[1].

All requirements-classes and conformance-classes described in this document are owned by the standard(s) identified.

3. References

The OGC DGGS Core Abstract Specification consists of this document.

The complete Abstract Specification is identified by OGC URI http://www.opengis.net/spec/dggs/1.0.

The document has OGC URI http://www.opengis.net/doc/AS/dggs/1.0

The following normative documents contain provisions that, through reference in this text, constitute provisions of this document. For dated references, subsequent amendments to, or revisions of, any of these publications do not apply. For undated references, the latest edition of the normative document referred to applies.

ISO: ISO 19101-1:2014,

Geographic information – Reference model – Part 1: Fundamentals, 2014

ISO: ISO 19103:2015,

Geographic information – Conceptual schema language, 2015

ISO: ISO 19107:2003,

Geographic information – Spatial schema, 2003

ISO: ISO 19111:2007,

Geographic information – Spatial referencing by coordinates, 2007

ISO: ISO 19112:2003,

Geographic information – Spatial referencing by geographic identifiers, 2003

ISO: ISO 19115-1:2014,

Geographic information – Metadata – Part 1: Fundamentals, 2014

ISO: ISO 19123:2005,

Geographic information – Schema for coverage geometry and functions, 2005

ISO: ISO 19125-1:2004,

Geographic information – Simple feature access – Part 1: Common architecture, 2004

ISO: ISO 19136:2007,

Geographic information – Geography Markup Language, 2007

ISO: ISO 19143:2010,

Geographic information – Filter encoding, 2010

ISO: ISO 19156:2011(E),

Geographic information – Observations and Measurements, 2011

ISO: ISO/IEC 19501:2005,

Information technology – Open Distributed Processing – Unified Modelling Language (UML),Version 1.4.2, 2005

OGC: OGC 06-103r4,

Implementation Standard for Geographic information – Simple feature access – Part 1: Common Architecture. Version 1.2.1

(identical in normative content to ISO 19125-1:2004), 2011

OGC: OGC 07-036,

OpenGIS Geography Markup Language (GML) Encoding Standard. (identical in normative content to ISO 19136:2007), 2007

OGC: OGC 08-015r2,

Abstract Specification[2]– Topic 2: Spatial referencing by coordinates.Version 4.0.0. (identical in normative content to ISO 19111:2007), 2010

OGC: OGC 10-004r3,

Abstract Specification²– Topic 20: Observations and Measurements. Version 2.0 (identical in normative content to ISO 19156:2011(E)), 2013

4. Terms and Definitions

For the purposes of this document, the following terms and definitions apply.

4.1 base unit polyhedron

polyhedron, with a circumsphere radius of one (1), used to construct the DGGS reference frame of a DGGS specification

Note 1 to entry: Vertex coordinates are specified as a sequence of spherical coordinates

[(θ₁, φ₁), (θ₂, φ₂),  (θ₃, φ₃),  (θ₄, φ₄),…,  (θ_n-1, φ_n)].

Note 2 to entry: Edges are specified as a sequence of vertex pairs

[(Vertex₁, Vertex₂), (Vertex₂, Vertex₃), (Vertex₃, Vertex₄)…, (Vertex_n-1, Vertex_n), or,

  ((θ₁, φ₁),(θ₂, φ₂)), ((θ₂, φ₂),(θ₃, φ₃)), ((θ₃, φ₃),(θ₄, φ₄))…, ((θ_n-1, φ_n-1),(θ_n, φ_n))]

4.2  boundary

set that represents the limit of an entity

Note 1 to entry: Boundary is most commonly used in the context of geometry, where the set is a collection of points or a collection of objects that represent those points. In other arenas, the term is used metaphorically to describe the transition between an entity and the rest of its domain of discourse.

[SOURCE:  ISO 19107:2003, definition 4.4].

4.3 centroid

center of mass of a geometric object of uniform density

Note 1 to entry: The centroid of a DGGS Cell is calculated as the geodesic center of the surface area of that DGGS Cell.

4.4   cell refinement

full specification for generating child cells from their parent cell(s) including the method of subdividing parent cells into child cells using a specified refinement ratio

Note 1 to entry: Iterative application of cell refinements results in a hierarchy of cell levels.

Note 2 to entry: Cell refinement methods may result in child cells that all have unique parents or child cells that may share parents.

4.5   class

description of a set of objects that share the same attributes, operations, methods, relationships, and semantics [ISO 19103:2015]

Note 1 to entry: A class may use a set of interfaces to specify collections of operations it provides to its environment. The term was first used in this way in the general theory of object oriented programming, and later adopted for use in this same sense in UML.

[SOURCE:  ISO 19107:2003, definition 4.7].

4.6   connected

property of a geometric object implying that any two direct positions on the object can be placed on a curve that remains totally within the object

Note 1 to entry: A topological object is connected if and only if all its geometric realizations are connected. This is not included as a definition because it follows from a theorem of topology.

[SOURCE:  ISO 19107:2003, definition 4.15].

 

4.7   curve

1-dimensional geometric primitive, representing the continuous image of a line

Note 1 to entry: The boundary of a curve is the set of points at either end of the curve. If the curve is a cycle, the two ends are identical, and the curve (if topologically closed) is considered to not have a boundary. The first point is called the start point, and the last is the end point. Connectivity of the curve is guaranteed by the “continuous image of a line” clause. A topological theorem states that a continuous image of a connected set is connected.

[SOURCE:  ISO 19107:2003, definition 4.23].

4.8   coordinate

one of a sequence of n numbers designating the position of a point in n-dimensional space

Note 1 to entry: In a coordinate reference system, the coordinate numbers are qualified by units.

[SOURCE:  ISO 19111:2007, definition 4.8].

Note 2 to entry: In the context of a DGGS specification, coordinates are used to reference the vertices and centroid of a DGGS Cell. Coordinates may also be used as part of an indexing schema for referencing DGGS Cells within a DGGS reference frame.

4.9   coordinate reference system

coordinate system that is related to an object by a datum

Note 1 to entry: For geodetic and vertical datums, the object will be the Earth.

[SOURCE:  ISO 19111:2007, definition 4.8].

4.10   data cell

quantization operation role where each DGGS Cell is assigned data sampled/mapped from a feature using the DGGS Cell’s geometry to govern the sampling operation

4.11   data tile

quantization operation role where feature values are aggregated and clipped to the boundary of a DGGS Cell and stored as a tile with no resampling or mapping of the individual feature values to individual DGGS Cells

Note 1 to entry: the DGGS Cell Index is used in the naming convention for data tiles

4.12   data type

specification of a value domain with operations allowed on values in this domain

[SOURCE: ISO 19103:2015, definition 4.14]

Example: Integer, Real, Boolean, String, Date (conversion of a date into a series of codes).

Note 1 to entry: Data types include primitive predefined types and user-definable types. All instances of a data type lack identity.

[SOURCE:  ISO 19156:2011(E), definition 4.3].

4.13   datum

parameter or set of parameters that define the positions of the origin, the scale, and the orientation of a coordinate system

[SOURCE:  ISO 19111:2007, definition 4.14].

 

4.14   DGGS cell

fundamental atomic object of a DGGS Reference Frame at each cell refinement level

Note 1 to entry: A DGGS cell can be considered a container for storing and retrieving data within a DGGS implementation. A DGGS cell may be considered either as a parent cell or as a child cell of at least one parent. In different DGGS implementations this container may be explicit (i.e. tightly coupled to the data stored on disc) or virtual (i.e. loosely coupled to the data stored on disc through a lookup table or database).

4.15   DGGS coordinate reference system

coordinate reference systemtied to the earth by a set of datums that cover the DGGS domain

Note 1 to entry: A DGGS coordinate reference system in two-dimensions is analogous to an ISO19111 geodetic coordinate reference system tied to one horizontal datum. DGGS coordinate reference systems however may in future be extended to include other dimensions (vertical, time) each with an appropriate datum. DGGS coordinate reference systems of higher dimensionality are therefore considered to be analogous to ISO19111 single coordinate reference systems and not ISO19111compound coordinate reference systems.

4.16   DGGS domain

spatio-temporal domain defined by a DGGS specification

Note 1 to entry: By definition, the surface domain of a DGGS is the surface of the entire globe. It may be extended to include other dimensions (vertical, time).

4.17   DGGS extent

extent of data assigned to a DGGS

Note 1 to entry: The DGGS extent may be local, regional or global and is independent of the DGGS domain.

4.18   DGGS reference frame

fixed structural elements of a DGGS specification that define the hierarchical spatial framework within which the DGGS’s functional algorithms operate

Note 1 to entry: The DGGS reference frame includes a DGGS coordinate reference system and a sequence of equal area discrete global grids defined on that DGGS coordinate reference system that govern the properties of the associated DGGS Cells. 

4.19   dimensionally extended nine-intersection model

topological model framework used to test whether a spatial topological relationship exists between two spatial objects

Note 1 to entry: DE-9IM is a mathematical approach that defines the pair-wise spatial relationship between geometries of different types and dimensions based on intersections of their interior, boundary, and exterior. It was developed by Clementini et. al. [5-7], extending the Nine Intersection Model of Egenhofer and Herring [8].

Note 2 to entry: DE-9IM used here is its extended form defined in OGC [OGC 06-103r4] identical in normative content to ISO/TC 211 [ISO 19125-1:2004].

4.20   direct position

position described by a single set of coordinates within a coordinate reference system

[SOURCE:  ISO 19107:2003, definition 4.26].

4.21   discrete global grid

single Tessellationof a chosen surface model of the Earth

Note 1 to entry: A discrete global grid must represent the entire surface model of the Earth.

Note 2 to entry: A single discrete global grid may be either an initial discrete global grid or a refinement of the initial discrete global grid.

Note 3 to entry: A discrete global grid system is constructed from a sequence of discrete global grids, each with successively smaller DGGS Cells.

4.22   discrete global grid system

spatial reference system that uses a hierarchical sequence of equal area discrete global grids to model, partition and address the globe.

 

Note 1 to entry: DGGSs are characterized by the properties of their cell structure, geo-encoding, quantization strategy and associated mathematical functions.

 

4.23   Earth grid system

one or more spatial or spatio-temporal grids constructed on the surface model of the Earth

4.24   edge type

topological descriptor used to define the path between DGGS Cell vertices along the surface model of the Earth used to define the DGGS Reference Frame

Note 1 to entry: choices for edge type include, inter alia, geodesic – shortest path, small circles– intersection of a plane oriented perpendicular to an ellipsoid’s axis of rotation and the ellipsoid, small ellipse–intersection of a defined plane and the ellipsoid and arcs that project to a straight line under equal-area projection. The list of allowed edge types is not fixed in the standard, but rather managed as a governed codelist.

4.25   ellipsoidal polygon

polygon constituting the boundary of a DGGS cell on the surface model of the Earth.

Note 1: DGGS are not bound to any one surface model of the Earth (e.g. spherical and ellipsoidal models of the Earth are both valid surface models to construct a DGGS Reference Frame).

Note 2: Different DGGS configurations will constrain each arc that forms part of its edge to one of the allowed edge types.

4.26   end point

last point of a curve

[SOURCE:  ISO 19107:2003, definition 4.36].

4.27   feature

abstraction of real-world phenomena

 

[SOURCE: ISO 19101-1:2014, definition 4.1.11]

 

Note 1 to entry: A feature may occur as a type or an instance. In this International Standard, feature instance is meant unless otherwise specified.

 

[SOURCE ISO 19156:2011(E), definition 4.6]

4.28   feature type

class of features having common characteristics

[SOURCE: ISO 19156:2011(E), definition 4.7]

4.29   geo-encoding

process of assigning a geodetic identifier to a DGGS cell

Note 1 to entry: Each cell of a DGGS is given a unique self-descriptive geodetic identifier or encoded cell address which represents a spatial reference that implicitly identifies its location and hierarchical relationship with other DGGS cells. Geometric transformation and indexing of cells can be implemented directly by address code operations alone.

4.30   geodetic identifier

spatial reference in the form of a label or code that identifies a DGGS cellin a DGGS reference frame

Note 1 to entry: By analogy to [SOURCE: ISO 19112:2003, definition 4.3] a geographic identifier is a spatial reference in the form of a label that identifies a location, whereas in a DGGS each cell is deemed to be a location in a DGGS Reference Frame.

4.31   geometric object

spatial objectrepresentingageometric set

Note 1 to entry: A geometric object consists of a geometric primitive, a collection of geometric primitives, or a geometric complex treated as a single entity. A geometric object may be the spatial representation of an object such as a feature or a significant part of a feature.

[SOURCE: ISO 19107:2003, definition 4.47]

4.32   geometric primitive

geometric objectrepresenting a single, connected,homogeneous element of space

Note 1 to entry: Geometric primitives are non-decomposed objects that present information about geometric configuration. They include points, curves, surfaces, and solids

[SOURCE: ISO 19107:2003, definition 4.48]

4.33   geometric set

setof direct positions

Note 1 to entry: This set in most cases is infinite.

[SOURCE: ISO 19107:2003, definition 4.50]

4.34   graphic cell

cellcontaining quantized information produced by a rendering process for delivery to a display system

Note 1 to entry: graphic cell is a term used to describe a quantization role. Examples include cells delivered by a WMS.

4.35   graphic tile

cellcontaining graphic cells aggregated into a tile and cached for delivery to a display system.

Note 1 to entry: graphic tile is a term used to describe a DGGS quantization role. A WMS service whose tiles correspond to DGGS cells is an example of a graphic tile.

Note 2 to entry: the DGGS Cell Index associated with the aggregated graphic cell is used in the naming convention for graphics tiles.

4.36   grid

network composed of two or more sets of curves in which the members of each set intersect the members of the other sets in an algorithmic way

[SOURCE: ISO 19123:2005]

Note 1 to entry: The curves partition a space into grid cells.

[SOURCE: ISO 19136:2007, definition 4.1.38]

4.37   hierarchy

organization and ranking of successive levels of cell refinement of a DGGS reference frame

4.38  initial discrete global grid

discrete global grid tessellation created by circumscribing a defined path along the chosen surface model of the Earth between the vertices of the scaled base unit polyhedron

4.39   object

entity with a well-defined boundary and identity that encapsulates state and behavior

Note 1 to entry: This term was first used in this way in the general theory of object oriented programming, and later adopted for use in this same sense in UML. An object is an instance of a class. Attributes and relationships represent state. Operations, methods, and state machines represent behavior.

[SOURCE: ISO 19107:2003, definition 4.59]

4.40   observation

act of measuring or otherwise determining the value of a property

[SOURCE: ISO 19156:2011(E), definition 4.11]

4.41   point

0-dimensional geometric primitive, representing a position

Note 1 to entry: The boundary of a point is the empty set.

[SOURCE: ISO 19107:2003, definition 4.61]

4.42   property

attribute of an object referenced by a name

[SOURCE: ISO 19143:2010, definition 4.21]

Example: Abby’s car has the color red, where “color red” is a property of the car.

[SOURCE: ISO 19156:2011(E), definition 4.15]

4.43   property type

characteristic of a feature type

Example: Cars (a feature type) all have a characteristic color, where “color” is a property type.

Note 1 to entry: The value for an instance of an observable property type can be estimated through an act of observation.

Note 2 to entry: In chemistry-related applications, the term “determinand” or “analyte” is often used.

Note 3 to entry: Adapted from ISO 19109:2005.

[SOURCE: ISO 19156:2011(E), definition 4.16]

4.44   quantization

process of digital assignment of data values that have been sampled from other data sources to the cells of a DGGS specification

4.45   refined discrete global grid

discrete global grid tessellation created by applying a refinement ratio to the DGGS Cells of an existing discrete global grid tessellation (either the initial discrete global grid or another refined discrete global grid)

4.46   refinement ratio

ratio of the number of child cells to parent cells

Note 1 to entry: A positive integer ratio n refinement of DGGS parent cells yield n times as many child cells as parent cells.

Note 2 to entry: For a two dimensional DGGS (as defined by this Abstract Specification) this is the surface area ratio.

Note 3 to entry: In DGGS literature [2] the term aperture has been used instead of refinement ratio. We prefer refinement ratio because it is clearer in meaning to audiences outside the early DGGS community.

4.47   sequence

finite, ordered collection of related items (objects or values) that may be repeated

[SOURCE: ISO 19107:2003, definition 4.64]

4.48   set

unordered collection of related items (objects or values) with no repetition

[SOURCE: ISO 19107:2003, definition 4.65]

4.49   simple polygon

polygon with a non-self-intersecting boundary

Note 1 to entry: In the context of a two dimensional DGGS (as defined by this Abstract Specification) a simple polygonis not a planar polygon but a curved polygon on the surface model of the Earth.

4.50   solid

3-dimensional geometric primitive, representing the continuous image of a region of Euclidean 3 space

Note 1 to entry: A solid is realizable locally as a three parameter set of direct positions. The boundary of a solid is the set of oriented, closed surfaces that comprise the limits of the solid.

[SOURCE: ISO 19107:2003, definition 4.68]

4.51   spatial object

object used for representing a spatial characteristic of a feature

[SOURCE: ISO 19107:2003, definition 4.69]

4.52   spatial reference

description of position in the real world

Note 1 to entry: This may take the form of a label, code or set of coordinates related to a position.

[SOURCE: ISO 19112:2003, definition 4.5]

4.53   spatial reference system

system for identifying position in the real world

[SOURCE: ISO 19112:2003, definition 4.6]

4.54   start point

first point of a curve

[SOURCE: ISO 19107:2003, definition 4.72]

4.55   surface

2-dimensional geometric primitive, locally representing a continuous image of a region of a plane

Note 1 to entry: The boundary of a surface is the set of oriented, closed curves that delineate the limits of the surface. Surfaces that are isomorphic to a sphere, or to an n-torus (a topological sphere with n- “handles”) have no boundary. Such surfaces are called cycles.

[SOURCE: ISO 19107:2003, definition 4.75]

4.56   tag

quantization operation role where individual DGGS Cell Index values are referenced to individual data objects that represent a feature.

Note 1 to entry: The DGGS Cell operates in this context as a Minimum Bounding Container (similar to a Minimum Bounding Rectangle) where the boundary of the DGGS Cell wholly encloses a set of features assigned to that cell.

Note 2 to entry: The refinement level of a DGGS Cell index used to tag a feature (or set of features) provides an indication of the level of precision and/or the spatial extents of that feature.

4.57  tessellation

partitioning of a space into a set of conterminous subspaces having the same dimension as the space being partitioned

[SOURCE: ISO 19123:2005, definition 4.1.39]

Note 1 to entry: In the context of a DGGS specification, an initial “Polyhedral” tessellation is the process of creating an initial partitioning of the ellipsoid into DGGS cells, and subsequent discrete global grid tessellations apply cell refinement methods resulting in child DGGS cells.

Note 2 to entry: The “Polyhedral” tessellation operation scales and maps the base unit polyhedron to the chosen surface model of the Earth in such a way that all DGGS cells of the Initial Discrete Global Grid have an equal surface area.

Note 3 to entry: The “Discrete Global Grid” tessellation refines a discrete global grid (either the Initial Discrete Global Grid or another Refined Discrete Global Grid) by applying a refinement ratio to the DGGS Cells of the given discrete global grid in such a way that all of the DGGS Cells of the new discrete global grid have an equal surface area and the combined surface area of all DGGS Cells is equal to the surface area of the surface model of the Earth used to define the DGGS Reference Frame.

4.58   value

element of a type domain

[SOURCE: ISO/IEC 19501:2005]Note 1 to entry: A value considers a possible state of an object within a class or type (domain).

 

Note 2 to entry: A data value is an instance of a datatype, a value without identity.

 

Note 3 to entry: A value can use one of a variety of scales including nominal, ordinal, ratio and interval, spatial and temporal. Primitive datatypes can be combined to form aggregate datatypes with aggregate values, including vectors, tensors and

images.

[SOURCE: ISO 19156:2011(E), definition 4.18]

5.    Conventions

This section provides details and examples for any conventions used in the document. Examples of conventions are symbols, abbreviations, use of XML schema, or special notes regarding how to read the document.

5.1    Identifiers

The normative provisions in this specification are denoted by the URI

http://www.opengis.net/spec/dggs/1.0  

All requirements and conformance tests that appear in this document are denoted by partial URIs which are relative to this base.

5.2    UML notation

All the diagrams that appear in this specification are presented using the Unified Modeling Language (UML) static structure diagram, as described in Sub-clause 5.2 of OGC Web Service Common [OGC 06-121r9].

5.3    Abbreviated terms

CRS           coordinate reference system

DE-9IM    dimensionally extended nine-intersection model

DGGS       discrete global grid system

ISO            International Organization for Standardization

OGC         Open Geospatial Consortium

OWS         OGC Web Service

6.    DGGS Core Data Model (normative)

This Clause specifies the underlying data model and core requirement class for a DGGS specification.

6.1    DGGS Core Data Model Overview

For an Earth grid system to be compliant with this Abstract Specification it must define a hierarchical tessellation of equal area cells that both partition the entire Earth at multiple levels of granularity and provide a global spatial reference frame. The system must also include encoding methods to: address each cell; assign quantized data to cells; and perform algebraic operations on the cells and the data assigned to them.

Figure 7 shows the packages comprising a DGGS with the core elements grouped into the two (2) main components of:

1.  reference frame elements, and,
2. functional algorithm elements; comprising:
   1.    quantization operations,
   2.    algebraic operations, and
   3.    interoperability operations.

6.2    DGGS Reference Frame Elements

The reference frame of a DGGS consists of the fixed structural elements that define the spatial framework on which the DGGS functional algorithms operate. The following sub-clauses define the core requirements for an Earth grid system to be considered a DGGS.

Figure 8 shows the class structure for the reference frame of a DGGS specification and how the classes relate to each other.

6.2.1    Global Domain

For an Earth grid system to be considered a DGGS specification it must be defined over the entire surface of the Earth, representing the DGGS Domain. As defined by Goodchild [9] global domain is achieved when the areal cells defined by the grid “exhaustively cover the globe without overlapping or underlapping”.

6.2.2    Tessellation Sequence

Unlike a single resolution spatial grid, a DGGS must define multiple discrete global grids forming a system of hierarchical tessellations each with progressively finer spatial resolution, each related by Cell Refinement methods.

6.2.3    Area Preservation

Preservation of total surface area throughout the range of hierarchical tessellations is a necessary property of DGGS in order to represent information consistently at successive resolutions. This requirement ensures that each level of grid refinement completely covers the globe without cell overlaps.

6.2.4    Cell Structure

Cell structure is an important aspect of any DGGS. Each cell can be considered to be an ellipsoidal polygon on the surface model of the Earth, for which several different cell shapes can be used.  Each cell shape has its own advantages and disadvantages [2] (e.g. hexagonal cells are optimized for high fidelity sampling [2, 10], while triangular cells enable fast access and visualization) and it is usually desired for each grid refinement of a DGGS to have a majority of cells with the same shape [10, 11].  Triangular, quadrilateral and hexagonal cells are common choices used in DGGS. These shapes provide regular tiling of the plane [10], which can be mapped to a curved surface such as the surface model of the Earth.

The cell structures in each successive level of cell refinement are constrained by the properties of the initial tessellation, but do not necessarily have the same geometry as the initial tessellation.

6.2.4.1    Simple Cells

For DGGS a specification to have cells which completely cover the surface of the Earth without any gaps or overlaps it is necessary for the shape of all cells defined by the DGGS Domain to be simple polygons on the surface model of the Earth. Simple polygons have the following properties:

a)     Edges that meet only at the vertices;

b)    Exactly two edges meeting at each vertex;

c)     Exactly the same number of edges and vertices; and,

d)    Enclosing a region which always has a measureable area.

The cell shapes derived from the five (5) Platonic solids and (13) Archimedean solids (triangle, quadrilateral, pentagon, hexagon, and octagon) are all simple polygons that  satisfy this requirement.

6.2.4.2    Equal Area Cells

This Abstract Specification defines DGGS as an Earth Reference System based on a hierarchy of equal area tessellations. Equal area cells provide global grids with spatial units that (at multiple resolutions) have an equal probability of contributing to an analysis. Equal area cells also help to minimize the confounding effects of area variations in spatial analyses where the curved surface of the earth is the fundamental reference frame.

By equal area we refer to the ‘derived SI unit’ of area as it is applied to the surface model of the earth within the boundary of defined by a DGGS cell. This is not an absolute value and is dependent on the precision (or uncertainty) of the tessellation of the Earth’s surface model (and the uncertainty of the Earth model itself). Just as a unit of length is dependent on the precision by which it is measured - for example, within the respective levels of precision, 1 meter can be correctly and accurately described as both:

a)     1/10,000,000 of the meridian through Paris between the North Pole and the Equator (+/- ~10^-4m) [original SI definition of 1m], and,

b)    The length of the path travelled by light in a vacuum in 1/299,792,458^th of a second (+/- 10^-10 m) [current SI definition of 1m].

This is despite the precision of both representations being 6 orders of magnitude different.

For DGGS cells constructed to approximate equal area but derived in other ways, we require that the cell refinement method be iterative, regular and predictably convergent on equal area.

In any specification of a DGGS, there will be a practical limit to the computational precision that is acceptable for that specification. This precision is represented as the ratio of DGGS cell area uncertainty to DGGS cell area. The DGGS cell area uncertainty may arise for example from the number of iterations undertaken in any iteratively converging calculation, the rate of convergence, the number of bits in the underlying computer’s CPU or storage architecture, or the precision of critical real values such as π, and the parameters defining the DGGS reference frame.

DGGS may validly comprise more than one cell geometry. This most typically arises for systems based on truncated polyhedra such as the cuboctahedron – with both square and triangular faces, and the truncated icosahedron – with pentagonal and hexagonal faces. In these situations equal area is interpreted to mean that all the cells of a particular geometry are equal area, and that the ratio of the areas of the two geometries is preserved through the tessellations. For example in the truncated icosahedron used by ISEA the ratio of pentagonal to hexagonal areas within a tessellation level is always 5/6.

6.2.5    Tessellations

A multiresolution hierarchical tessellation of cells is created by constructing a sequence of discrete global grids, each with successively finer DGGS Cell resolutions. First an initial discrete global grid is constructed as described in sub-clause 6.2.5.1. The cells of this initial tessellation are then iteratively refined by application of cell refinement method(s) [2] to create finer resolution child cells.  The initial tessellation, the cell shape, the refinement methods and indexing methods may all vary for different DGGS.

6.2.5.1    Initial Tessellation

The entire globe must be partitioned to a finite/discrete set of regions. Most methods initially approximate the globe using a simple base unit polyhedron which is scaled so that all vertices are located on the surface model of the Earth. The shortest path along that surface are then mapped to produce an initial discrete global grid tessellation of the same general form as the chosen base unit polyhedron. Each DGGS Cell of the initial tessellation represents one face of the chosen base unit polyhedron mapped to the chosen surface model of the Earth. This Abstract Specification refers to this initial tessellation as the “polyhedral tessellation”. The most common choices for an initial base unit polyhedron are discussed in sub-clause B.4 [22].

6.2.5.2    Tessellation by Cell Refinement

To support multiple spatial resolutions, a series of increasingly finer resolution tessellations are needed [11].  Each successive resolution is generated from its parent by recursive application of one or more refinement methods. Each refinement method is categorized according to parent cell shape(s), child cell shape(s) – often the same as the parent shape, parent-child alignment, rotation and refinement ratio [2].  This Abstract Specification refers to tessellation by cell refinement as the “Discrete Global Grid tessellation”. Theoretically there are an infinite number of cell refinements that can be implemented on a DGGS; however, as a best practice it is recommended [3] that a DGGS specification should specify a maximum number of refinements that considers the particular use-case and the limitations in spatial resolution and precision of the Earth model used by the DGGS Reference Frame.

6.2.5.3    Cell Addressing

Cell addresses, or indices, for DGGSs are derived from four general indexing methods: hierarchy-based, space-filling curve based, coordinate [1] and encoded address schemas (such as those used for IP addresses [12]).  The use of labels as geographic identifiers might also achieve an acceptable addressing if DGGS operations can be maintained. Under this Abstract Specification each cell of a DGGS specification must have a unique cell address assigned using one or more of these methods.

6.2.6    Spatial Referencing

Spatial referencing (or geo-encoding) is achieved by addressing an identifier – an index or geographic identifier – to each DGGS cell.  The cell address must be unique across the entire domain of hierarchical tessellations of the DGGS.

6.2.6.1    Cells Referenced at their Centroid

Each DGGS Cell must be referenced at its centroid. This is because the centroid is the only location that will provide a systematic and consistent spatial reference point for all cells regardless of their shape.

To demonstrate this, consider that we have a DGGS constructed with square/rectilinear shaped cells and one of the cell vertices (say the top left-hand corner) is chosen as the primary spatial reference location for that cell, and the method of cell refinement is aligned (i.e. no cell rotation throughout successive levels of grid refinement). In this case, the method and schema required to define a vertex as the primary spatial reference location is simple, intuitive and requires less work to define than, for example, computing the geodesic cell centroid. However, if the cells are rotated as part of the grid refinement schema then you would need to add the complexity of determining which vertex will be deemed the ‘top left-hand corner’ of successive ‘rotated’ levels of refinement; again, this is only a little more complex but now the schema is tailored to a particular type of DGGS specification. Further, if we wish to apply a similar vertex focused referencing schema to a triangular or hexagonal structured DGGS how would we easily and systematically define which vertices are equivalent to the ‘top left-hand corner’ in the rectilinear case. And for each new style of tessellation and refinement schema there would need to be an individual schema established to assign the primary vertex for the spatial reference. By contrast the geodesic centroid location is calculated using the same mathematical algorithm regardless of the shape of the cell and is not affected by changes in cell orientation throughout the DGGS Domain.

The centroid location is calculated as the geodesic center of surface area of a DGGS cell. The centroid enables a dual representation of a DGGS tessellation as both n-dimensional areal cell grids and as point-based lattices of cell reference locations.

6.3    DGGS Functional Algorithms

The ability to locate and perform algebraic operations on data assigned to a DGGS is critical for a DGGS specification. Additionally, it should support connectivity and hierarchical operations on cells. As a minimum, a DGGS specification must include definitions for:

1. Quantization Operations – Assigning and retrieving data to and from cells;
2. Algebraic Operations –Performing algebraic operations on cells and the data assigned to them and cell navigation; and
3. Interoperability Operations – Translating cell addresses to other Coordinate Reference Systems (CRS), such as a conventional latitude-longitude.

6.3.1    Quantization Operations

A DGGS is defined based on the geometry of the globe in a data agnostic manner. Therefore, a DGGS specification must define mechanism for assigning data to cells and retrieving data from cells. Different quantization strategies may be used for sampling content into cells. For example, a single DGGS may be used as a data structure for integrating multiple datasets of different types (e.g. vector and raster datasets) [11] and in different ways (e.g. DGGS cells as data tiles, or one raster pixel per DGGS cell or DGGS cell indices as vector coordinate-pairs). This Abstract Specification makes use of the concepts defined by the Observations and Measurements abstract standard [ISO 19156:2011(E)] to facilitate the association of observations/spatial data to a DGGS cell(s).  Some DGGS/polyhedron choices are more efficient for sampling (e.g. DGGS based on an icosahedron).

Multiple observation contexts are recognized for quantization, each corresponding to a distinct role for DGGS Cells to play. In any particular DGGS specification, one or more (and potentially all) roles may be described for either internal or external use to support interoperability, as follows.

1. Data Tiles:
   •   In Data Tile quantization, spatial feature/observations (e.g. point clouds, images, vectors, etc.) are aggregated and clipped to cell boundaries and stored in tiles without any changes made to the feature type parameters. The cells of the DGGS provide a multi-, or single-, resolution tiling schema with the cell index used as the identifier in the tile naming convention. In the context of “Big Data Analytics” ‘asDataTile’ support will likely be the most efficient type of granularity for job submission on HPC/HPD or Cloud ICT infrastructure; particularly for embarrassingly parallel analyses. It is also likely to be the most efficient granularity for many data transfer requests.
2. Data Cells:
   •   In Data Cell quantization, the spatial features/observations (e.g. point clouds, images, vectors, etc.) are sampled to each DGGS Cell by assignment of data value(s) using the cell’s geometry to govern the quantization operation.
3. Coordinates:
   •   In coordinate quantization, each coordinate tuple from the spatial feature/observation is converted to a cell index of an appropriate level of precision. The cell data package will include appropriate vector topology to preserve the structure of the spatial feature in the context of the DGGS.
4. Tags:
   •   In Tag quantization, cell index values are “tagged” to data objects in a similar fashion to social media records. The refinement level of the cell index is indicative of the precision with which the location of a spatial feature/observation and/or its spatial extent are known. This can be thought of as a convex hull with the same geometry of the DGGS Cell surrounding the objects to be assigned to that cell.
5. Graphic Cells:
   •   In Graphic Cell quantization, data is rendered to cells, and refinement levels are leveraged to support corresponding levels of detail or zoom levels.
6. Graphic Tiles:
   •   In Graphic Tile quantization, graphic cells are tiled, and often cached for delivery to a display system. As with data Tiles, the cell index is used as the identifier in the tile naming convention.

The data assigned to a particular DGGS implementation defines its DGGS Extent and will vary over its lifecycle as the amount of data assigned to it changes. The DGGS Domain, however, must always be fixed and be defined over the entire surface model of the Earth.

Figure 9 shows the key functional algorithm elements required to perform data quantization operations in a DGGS specification.

6.3.2    Algebraic Operations

A DGGS specification must include methods to support analytic and algebraic processes on the data assigned to it across its entire domain. There are two key classes of operations that support this:

1. Cell Navigation Operations – supporting navigation operations through both parent-child DGGS Cell relationships and neighbourhood associations across the entire DGGS Domain; and,
2. Spatial Analysis Operations – supporting spatial analysis operations using DE-9IM to determine the spatial relationships between DGGS Cells and spatial query objects.

These two classes of operators facilitate the hierarchical and spatial queries necessary to retrieve data from DGGS cell(s). Further algebraic and analytic processes may then be applied to the returned data through additional software bindings. This Abstract Specification does not specify any requirements for the binding or implementation of further, extension, algebraic or analytic processes.   

Figure 10 shows the key classes of algebraic operations required by a DGGS specification.

6.3.3    Interoperability

While the quantization and algebraic functional algorithms enable a DGGS implementation to successfully operate internally; in order to facilitate connectivity with other spatial data infrastructures additional interoperability operations/methods are required. As a minimum, these interoperability operations must include functions to:

1.   Interpret and translate external data queries and/or process commands sent to the DGGS implementation; and,
2. Convert the result set returned from a DGGS data operation from internal data format(s) (optimized for that DGGS implementation) to format(s) suitable for external data delivery.

This document does not specify the specific interface protocol encodings required to connect a DGGS implementation to an external client and facilitate the transfer of information into and out of a DGGS. This Abstract Specification makes use of the tools available in the Observations and Measurements Standard [ISO 19156:2011(E)] to facilitate the linkage between external query operations and the data/observations assigned to the DGGS cell(s) of interest. Specific interface encodings are anticipated to be elaborated as extensions to this Abstract Specification.

6.3.3.1    External Query/Process Interpretation

External queries and processes may originate from an external client application and range in syntax from “natural language queries” (e.g. ‘Where are the gas pipelines in Western Canada located?’, or, ‘How has the Murray-Darling Basin in Australia changed over the past 27 years?’, or ‘Compute the watershed area of the Kawarau Catchment in New Zealand’), to an OWS ‘GetCapabilities’ or similar type of query, to an SQL (or similar) statement. To support interoperability, a DGGS specification must define methods to receive, interpret and translate an external data query (or process) request into a form that can be processed by the internal DGGS data retrieval algorithms and/or algebraic operations.

Figure 11 shows on the left hand side the key functional algorithm elements required for DGGS to translate and execute a external query or process operations.

6.3.3.2    Query/Process Result Broadcasting

Just as it is necessary for DGGS to be able to interpret and execute external data queries, DGGS must also be able to broadcast results from data queries to external client(s) or data infrastructure(s). External clients are anticipated to be web-based client(s), software client(s) on the same ICT infrastructure as the DGGS, or even other DGGS.

Figure 11 shows on the right hand side the basic elements required to translate the result set(s) returned from a DGGS data query into a suitable data format for transfer and broadcast the reformatted result set via one or a number of data/information transfer protocols [4].

Annex : Conformance Class Abstract Test Suites (Normative)

This Annex specifies an Abstract Test Suite which shall be passed in completeness by any specification claiming conformance with this Abstract Specification.

Tests identifiers below are relative to http://www.opengis.net/spec/DGGS/1.0/.

A.1     Conformance class: Core

Annex : Background to DGGS (Informative)

B.1 DGGS as a Digital Information Medium

Conventional coordinate reference systems address the globe with a continuous field of points suitable for repeatable navigation and analytical geometry. While this continuous field is represented on a computer in a digitized and discrete fashion by tuples of fixed-precision floating point values, it is a non-trivial exercise to relate point observations spatially referenced in this way to areal features on the surface of the Earth. In contrast, a DGGS is designed to be an information grid not a navigation grid.  DGGS provide a fixed areal based geospatial reference frame for the persistent location of measured Earth observations, feature interpretations, and modelled predictions.  DGGS address the entire planet by partitioning it into a discrete hierarchical tessellation of progressively finer resolution cells.  The geometry and location of the cell is the principle aspect of a DGGS.  Data integration, decomposition, and aggregation is optimized in the DGGS hierarchical structure and can be exploited for efficient multi-source data processing, storage, discovery, transmission, visualization, computation, analysis, and modeling. 

B.2 History

The concept of using polyhedra to model the surface of the Earth is by no means new. In 1509 Lucia Pacioli published “De Devina Proportione” [14] a treatise, illustrated by Leonardo Da Vinci, exploring the mathematical characteristics of the ‘golden ratio’ (also referred to as the ‘divine proportion’) which included a consideration of the properties of the five platonic solids circumscribed within the sphere and the eminent role of the ‘golden ratio’ in the construction of two of them (the icosahedron and dodecahedron). It is likely that his time studying with Pacioli influenced Da Vinci’s later thinking regarding spherical geometry; evidenced in 1515 by his derivation of the octahedral analysis of the volume of a sphere with various forms of segmentation [15]. This work is suggested to have led to the development of the Reuleaux triangular formulation of the world map (or mappamundi), attributed to Da Vinci [16], and may be considered a precursor to differential calculus formally developed by Newton and Leibniz nearly two centuries later.

In the 1940’s a similar approach was used by R. Buckminster Fuller in the development of the Dymaxion map of the world [17] – a physical model of the Earth mapped onto the planar faces of a polyhedron (first presented as a cuboctahedron [18] and then later as an icosahedron [19]). The aim of the Dymaxion map was to depict the spherical world as a flat surface with true scale, true direction and correct configuration all at the same time. Although a physical model of the Earth, and not strictly a DGGS, it inspired later researchers to produce digital Earth models; which in turn has led to the development of DGGS.

Formal development of DGGS began in the 1950s with the promising value of global analysis coinciding with the increased use of geographic information systems and the availability of global mapping data and positioning systems.  Perhaps the first published instance of formalized discrete global grids with application to numerical analysis was described by Vestine et. al. [20] in 1955, where they define and use an equal-area grid based on the mapping of a spherical icosahedron onto the surface of the Earth as a framework to conduct areal based integral and spherical-harmonic analyses of the geomagnetic field. This grid was later used (and re-described) by Sadourny et. al. [21] in 1968 to model equations of atmospheric motion without distortion across the entire globe. Another style of discrete global grid, and perhaps the first application of hierarchical indexing schemas as an analytic cell referencing tool was implemented by Geoffrey Dutton in 1984 [22- 24] at the Laboratory for Computer Graphics and Spatial Analysis at Harvard Graduate School of Design.  Dutton’s first global grid was designed for assembling and managing global terrain data on a triangular global grid.  His global geodesic elevation model (GEM) [22-25] started with a cuboctahedron connected into a rhombic dodecahedron (which is its dual polyhedron where the vertices of one corresponds to the center of the faces of the other) and recursively divided the initial 12 triangular faces into refinements of 9 partially nested equilateral triangles.  Dutton refined GEM to use only an octahedral basis in the Quaternary Triangular Mesh (QTM) DGGS [22- 24, 26]. QTM is a fourfold hierarchical decomposition of facets of an octahedron into triangles whose edges follow small circles. Elevations were assigned to the centroids of child triangles and to the vertices that coincided with them.  Waldo Tobler and Zi-tan Chen [27] imagined the primary purpose for a formal discrete global grid standard would be information exchange and storage.  Tobler argued that as a generalized information medium “…coverage must be uniform and that every element of area must have an equal probability of entering the system. This suggests that the world should be partitioned into chunks of equal size” [27].  Tobler’s global grid started with a cube as a base unit polyhedron and divided into rectilinear quad-trees to create successive subdivisions with unlimited resolution.  Dennis White, Scott Overton, and Jon Kimerling, driven by a need for a statistically valid sampling to integrate aquatic and terrestrial monitoring for the US-EPA, designed a global grid in 1989 using closely packed hexagonal cells that started with a truncated icosahedron as the base unit polyhedron [28].

B.3 Global Grid Taxonomy

There have been numerous methods proposed for achieving a tessellation of the Earth, each with varying degrees of area and/or shape distortion [29]. These tessellations can be organized into a limited set of categories that describe a hierarchical taxonomy of global grids (Figure 12) [29, 30]. In order for a global grid tessellation to be able to operate as a DGGS it must be able to produce equal area cells on the surface of the Earth [27]. Only two groups of classes of global grid achieve this [29]: those based on equal area mapping of a base unit polyhedron (such as the Icosahedral Snyder Equal Area [ISEA] projection [31]) and those based on direct surface tessellations using Small Circle Subdivision (e.g. [32, 33]).

B.4 Criteria

There are many possible DGGS, each with their own advantages and disadvantages.  Criterion for a discrete global grid are well developed by both Michael F. Goodchild [9] and Jon Kimerling [29]; the foremost requirements being a tessellation of cells that exhaustively cover the globe with each cell having equal area and representing a single point.  The points and cells of the various resolution grids which constitute the grid system form a hierarchy which displays a high degree of regularity [45]. Choices for an appropriate tessellation include properties of shape, adjacency, connectivity, orientation, self-similarity, decomposability, and packing properties.  Cell choices generally are taken from the three shapes that uniformly tile a plane – rectilinear, triangular, and hexagonal cells.

While it is possible to map any polyhedral solid to the surface of the earth, the Platonic solids (tetrahedron, cube, octahedron, dodecahedron and icosahedron – see Figure 13) are the only polyhedral solids that perfectly partition the surface of a sphere into regular, equal area cells [46]. As a result, the Platonic solids are used in the construction of most equal area DGGS, often via a mapping of the polyhedral faces to the surface model of the Earth (some examples are shown in Figure 14). This method of mapping the faces of a base unit polyhedron to the surface model of the Earth creates a coordinate reference system that is based on a curved geometric framework. GIS and image analysis packages that assume flat earth geometries will need to adapt to support this new construct that more closely represents the earth.

Any tessellation of the Earth does not necessarily produce a DGGS.  Single resolution computational grids are not sufficient to constitute a DGGS.  Spatial data structures used to organize map tiles or optimize rapid spatial search cannot be considered to qualify as a DGGS in and of themselves; although DGGS often utilize hierarchical indices to identify a cell, the primary feature of the DGGS is the cell geometry not the optimization of a spatial query.  Further, DGGS have data independent geometry – their geometry is not formed to optimize a balanced search like R-Trees or maximal spacing of data as generated by Voronoi diagrams.  

B.5 A Digital Spatial Reference System

One way to understand the important difference between a DGGS and a conventional spatial reference system is to consider that a DGGS provides a digital framework for geospatial information.  Geospatial information is essentially a signal – that is some variable (e.g. measurement of phenomena) which changes subject to some other independent variable (e.g. spatial location, time, some physical interaction etc.…).  Conventional geospatial data are analog signals as they reference to a continuous space – geographic coordinates on an ellipsoidal datum.  Even the discrete pixels of a satellite Earth observation image reference this continuous analog model of Earth; however, these pixels do not observe precisely the same locational area for successive observations. Spatial reference by geographic identifier is described in ISO 19112. An OGC DGGS provides this globally in a structured form which is analogous to the ellipsoidal coordinate system described in ISO 19111 - spatial referencing by coordinates, but cell-based rather than continuous.

Sampling and quantization are necessary for a signal to be considered digital.  As the name implies the DGGS provides the regular discrete intervals or cell partitioning to which location information (e.g. signal values) are sampled.  A well-designed quantization strategy is also an important component of a DGGS that should maintain the fidelity of the original information in the values assigned to each cell.  The discrete data values can be sampled from any geospatial data source independent of the original spatial reference, scale, format, type, frequency, or time.  A DGGS is a discrete “digital” model of the Earth.

B.6 Application

As each cell in a DGGS is fixed in location, and the location provides an explicit area representation, basic geospatial enquiries, such as – “Where is it?”, “What is here?”, and “How has it changed?” – are simplified into set theory operations.  As any data values referenced to a particular DGGS are, by the nature of the grid, aligned, the high costs of integrating data in traditional systems are dramatically reduced. 

A DGGS can even be designed for lossless encoding of vector geometry such that cells, and their integer addressing, predictably converge to the Real number coordinate pairs of each observation with each successive refinement – an essential property of a conventional coordinate system.

DGGS are designed to eliminate requirements for complex data fusion processes.  Reducing the reliance on an intermediary integrator or analyst is a key requirement for distributed participatory digital-Earth information systems.  “[Digital-Earth] can clearly benefit from developments in discrete global grid, which can provide the georeferencing, the indexing, and the discretization needed for geospatial data sets. They have properties, in particular hierarchical structure, uniqueness, explicit representation of spatial resolution, and consistency, that make them superior to any single alternative.” [9]. 

A DGGS provides a uniform environment to integrate, aggregate and visualize both vector/point cloud geometries and raster-based geospatial data sources in much the same way that information within a computer graphics pipeline becomes the pixels on a computer screen. Efficiencies are gained through implementing the Dimensionally Extended nine-Intersection Model (DE‑9IM) set of fundamental spatial operations [5-8] directly on the DGGS cell structure. This allows for higher order algebraic algorithms (via bindings to external analytic libraries) to be created on the DGGS structure itself, independent of the data sources.

Annex : Revision history

Annex : Bibliography

[1] Mahdavi-Amiri, A., Samavati, F. F., Peterson, P., 2015, “Categorization and conversions for indexing methods of discrete global grid systems”, ISPRS International Journal of Geo-Information, 4(1), pp 320–336. DOI:10.3390/ijgi4010320

[2] Mahdavi-Amiri, A., Alderson, T., & Samavati, F., 2015, “A Survey of Digital Earth Representation and Visualization”, Computers & Graphics, Elsevier Ltd., pp. 95-117. uri: http://hdl.handle.net/1880/50407

[3] Dictionary of Computing, Forth Edition, Oxford University Press, 1996

[4] Goodchild, M. F., 1992, “Geographical information science”, International Journal of Geographical Information Systems, 6(1): pp 31–45. DOI:10.1080/02693799208901893

[5] Clementini, E., Di Felice, P., van Oosterom, P., 1993. “A small set of formal topological relationships suitable for end-user interaction”. In Abel, David; Ooi, Beng Chin. Advances in Spatial Databases: Third International Symposium, SSD ’93 Singapore, June 23–25, 1993 Proceedings. Lecture Notes in Computer Science. 692/1993. Springer. pp 277–295. DOI:10.1007/3-540-56869-7_16.

[6] Clementini, E., Sharma, J., Egenhofer, M. J., 1994, “Modelling topological spatial relations: Strategies for query processing”. Computers & Graphics 18 (6), pp 815–822. DOI:10.1016/0097-8493(94)90007-8.

[7] Clementini, E., and Di Felice P. A., 1996, “A Model for Representing Topological Relationships between Complex Geometric Features in Spatial Databases.” Information Sciences, 90(1), pp 121-136. DOI:10.1016/0020-0255(95)00289-8

[8] Egenhofer, M.J.; Herring, J.R., 1990, “A Mathematical Framework for the Definition of Topological Relationships”. Fourth International Symposium on Spatial Data Handling Zürich, Switzerland, pp 803-813. http://www.spatial.maine.edu/~max/MJEJRH-SDH1990.pdf

[9] Goodchild, M. F., 2000, “Discrete global grids for digital earth”, International Conference on Discrete Global Grids.Santa Barbara. http://www.ncgia.ucsb.edu/globalgrids/papers/goodchild.pdf  

[10] Peterson, P. R., 2017, “Discrete Global Grid Systems.” In The International Encyclopedia of Geography, edited by Douglas Richardson. Malden, Oxford: John Wiley and Sons, Ltd. DOI: 10.1002/9781118786352.wbieg1050

[11] Sahr, K., White, D., Kimerling, A. J., 2003, “Geodesic discrete global grid systems”, Cartography and Geographic Information Science, 30 (2), pp 121–134. DOI:10.1559/152304003100011090

[12] Postel, J., 1981, “RFC 791: Internet protocol”, Darpa Internet Protocol Specification (September 1981). - https://tools.ietf.org/html/rfc791

[13] Vincenty, T., 1975, “Direct and Inverse Solutions of Geodesics on the Ellipsoid with Application of Nested Equations”, Survey Review, 23(176), pp88-93.

[14] Pacioli, L., 1509, “De Davina Proportione” (Illustrated by Leonardo Da Vinci), Venice.

[15] da Vinci, L, 1514, “Manuscript E, 24v-25r (1513-14)”. Pen and ink on paper, 150 x 99 mm. Bibliothèque de l’Institut de France, Paris.

[16] da Vinci, L, 1478-1518, “Codex Atlanticus”. Pen and ink on paper, 61 x 44 cm. (collated by Pompeo Leoni). Biblioteca Ambrosiana, Milan, Italy.

[18] Fuller, R. B., 1946, Cartography. U.S. Patent 2,393,676. https://www.google.com/patents/US2393676

[19] Fuller, R. B. and Sadao, S., 1954, “Dymaxion Airocean World: The Raleigh Edition of Fuller Projection”. Student Publications of the School of Design, North Carolina State College, Raleigh, North Carolina, USA. (http://www.genekeyes.com/FULLER/BF-5-1954.html)

[20] E. H. Vestine, W. L. Sibley, J. W. Kern, and J. L. Carlstedt, “Integral and Spherical-Harmonic Analyses of the Geomagnetic Field for 1955.0, Part 2,” Journal of Geomagnetism and Geoelectricity, vol. 15, No. 2, Aug. 1963, pp. 73-89.

[21] Sadourny, R.; Arakawa, A.; Mintz, Y. (1968). “Integration of the nondivergent barotropic vorticity equation with an icosahedral-hexagonal grid for the sphere”. Monthly Weather Review 96 (6): 351–356.

[22] Dutton, G., 1989, “Modelling location uncertainty via hierarchical tessellation”. In: Accuracy of Spatial Databases, Goodchild, M. and Gopal, S. (eds.), London: Taylor & Francis, pp 125-140.

[23] Dutton, G., 1999, “A hierarchical coordinate system for geoprocessing and cartography”. Lecture Notes in Earth Science 79. Berlin: Springer-Verlag. XIX + 231 pp. 97 figs. 12 plates, 16 tabs. ISSN 0930-0317, ISBN 3-540-64980-8.

[24] Dutton, G., 1984, “Part 4: Mathematical, Algorithmic and Data Structure Issues: Geodesic Modelling Of Planetary Relief”, Cartographica: The International Journal for Geographic Information and Geovisualization, 21(2-3), pp 188-207. DOI:10.3138/R613-191U-7255-082N

[25] Dutton, G., 1996, “Encoding and handling geospatial data with hierarchical triangular meshes”, In Proceeding of 7th International symposium on spatial data handling, 43, Netherlands: Talor & Francis. DOI:10.1.1.461.5603

[26] Dutton, G., 1999, “Scale, Sinuosity, and Point Selection in Digital Line Generalization”, Cartography and Geographic Information Science, 26(1), pp 33-54. DOI: 10.1559/152304099782424929.

[27] Tobler, W., & Chen, Z.-t., 1986, “A Quadtree for Global Information Storage”, Geographical Analysis, 18(4), pp 360-371. DOI:10.1111/j.1538-4632.1986.tb00108.x

[28] White, D., Kimerling, J., & Overton, W. S., 1992, “Cartographic and geometric components of a global sampling design for environmental monitoring”, Cartography and Geographic Information Systems, 19(1), pp 5-22. DOI:10.1559/152304092783786636

 [29] Kimerling, A. J., Sahr, K., White, D., & Song, L., 1999, “Comparing Geometrical Properties of Global Grids“, Cartography and Geographic Information Systems vol. 26, no. 4, pp 271-88. DOI:10.1559/152304099782294186

[30] Dutton, G., 1994, “Geographical grid models for environmental monitoring and analysis across the globe (panel session)”. In: Proceedings of GIS/US’94 Conference, Phoenix, Arizona.

[31] Snyder, J. P., 1992, “An equal-area map projection for polyhedral globes”. Cartographica, 29(1), pp 10-21.

[32] Song, L., 1997, “Small circle subdivision method for development of global sampling grid”, Unpublished Masters Thesis, Oregon State University, 176pp.

[33] Song, L., Kimerling, A. J., and Sahr, K., 2002, “Developing an Equal Area Global Grid by Small Circle Subdivision”. In M. Goodchild and A. J. Kimerling (Eds.), Discrete Global Grids. Santa Barbara, CA, USA: National Center for Geographic Information & Analysis. (http://www.geo.upm.es/postgrado/CarlosLopez/materiales/cursos/www.ncgia.ucsb.edu/globalgrids-book/song-kimmerling-sahr/) 

[34] Lukatela, H., 1987, “Hipparchus geopositioning model: An overview”, In: Proceedings of Auto Carto 8 Symposium, Baltimore, Maryland. pp 87-96.

[35] Fekete, G., Treinish, L., 1990, “Sphere quadtree: A new data structure to support the visualization of spherically distributed data”.SPIE: Extracting Meaning from complex data: Processing, display, interaction. 1259, pp 242-253.

[36] Bjorke, J. T., Grytten, J. K., Haeger, M., Nilsen, S., 2003, “A Global Grid Model Based on ‘Constant Area’ Quadrilaterals”, ScanGIS, 3, pp 238-250. DOI: 10.1.1.105.2253

[37] Amante, C. and Eakins, B. W., 2009, “ETOPO1 1 Arc-Minute Global Relief Model: Procedures, Data Sources and Analysis”, NOAA Technical Memorandum NESDIS NGDC-24, 19 pp.

[38] Rees, T., 2002, “ ‘C-Squares’ – a new metadata element for improved spatial querying and representation of spatial dataset coverage in metadata records”, in EOGEO 2002 Proceedings, Ispra, Italy.

[39] Loveland, T. R., Merchant, J. W., Ohlen, D., O., Brown, J. F., 1991, “Development of a land-cover characteristics database for the counterminous”. U.S. Photogrammetric Engineering and Remote Sensing, 57(11), pp 1453-1463

[40] Snyder J. P., 1993, “Flattening the Earth: Two Thousand Years of Map Projections”, pp5-8. ISBN 0-226-76747-7)

 [41] Gibb, R.G., 2016, “The rHealPIX Discrete Global Grid System” Proceedings of the 9^th Symposium of the International Society for Digital Earth (ISDE), Halifax, Nova Scotia, Canada. IOP Conf. Series: Earth and Environmental Science, 34, 012012. DOI: 10.1088/1755-1315/34/1/012012

[42] Ma, T., Zhou, C., Xie, Y., Qin, B., Ou, Y., 2009, “A discrete square global grid system based on the parallels plane projection”. International Journal of Geographical Information Science. 23(10), pp 1297-1313. DOI: 10.1080/13658810802344150

[43] Fisher, I., 1943, “A World Map on a Regular Icosahedron by Gnomonic Projection”, Geographical Review, 33(4), pp 605-619, DOI: 10.2307/209914

[44] Fuller, R. B., 1982, “Synergetics”, New York.

[45] Clarke, K. C., 2000, “Criteria and Measures for the Comparison of Global Geocoding Systems”, International Conference on Discrete Global Grids. Santa Barbara: University of California, Santa Barbara. http://ncgia.ucsb.edu/globalgrids-book/comparison/

[46] Fitzpatrick, R., 2008. Euclid’s Elements of Geometry. Richard Fitzpatrick. ISBN 978-0-6151-7984-1

[47] Schmidt, R., Grimm, C., Wyvill, B., 2006, Interactive decal compositing with discrete exponential maps, ACM Transactions on Graphics, 25 (3), pp 605–613.

[1] www.opengeospatial.org/compliance_cite

[2] The OGC Abstract Specifications are available from http://www.opengeospatial.org/docs/as

[3] Elaboration of this and other “Best Practices” in the construction of conformant DGGS implementations will be included in a forthcoming “Best Practice” document to be published by the DGGS SWG following adoption of this Standard.

[4] Specific DGGS interoperability Interface Protocols will be elaborated in a series OGC Extension Standard documents to this standard.