Discrete global grid


A Discrete Global Grid is a mosaic which covers the entire Earth's surface.
Mathematically it is a space partitioning: it consists of a set of non-empty regions that form a partition of the Earth's surface. In a usual grid-modeling strategy, to simplify position calculations, each region is represented by a point, abstracting the grid as a set of region-points. Each region or region-point in the grid is called a cell.
When each cell of a grid is subject to a recursive partition, resulting in a "series of discrete global grids with progressively finer resolution", forming a hierarchical grid, it is named Hierarchical DGG.
Discrete Global Grids are used as the geometric basis for the building of geospatial data structures. Each cell is related with data objects or values, or may be associated with other cells. DGGs have been proposed for use in a wide range of geospatial applications, including vector and raster location representation, data fusion, and spatial databases.
The most usual grids are for horizontal position representation, using a standard datum, like WGS84. In this context, it is common also to use a specific DGG as foundation for geocoding standardization.
In the context of a spatial index, a DGG can assign unique identifiers to each grid cell, using it for spatial indexing purposes, in geodatabases or for geocoding.

Types and examples

The main distinguishing feature to classify or compare DGGs is the use or not of hierarchical grid structures:
Other usual criteria to classify a DGG are tile-shape and granularity :
The most common class of Discrete Global Grids are those that place cell center points on longitude/latitude meridians and parallels, or which use the longitude/latitude meridians and parallels to form the boundaries of rectangular cells. Examples of such grids, all based on Latitude/Longitude:

Hierarchical grids

The right aside illustration show 3 boundary maps of the coast of Great Britain. The first map was covered by a grid-level-0 with 150 km size cells. Only a grey cell in the center, with no need of zoom for detail, remains level-0; all other cells of the second map was partitioned into four-cells-grid, each with 75 km. In the third map 12 cells level-1 remains as grey, all other was partitioned again, each level-1-cell transformed into a level-2-grid.
Examples of DGGs that use such recursive process, generating hierarchical grids, include:

Standard equal-area hierarchical grids

There are a class of hierarchical DGG's named by the Open Geospatial Consortium as "Discrete Global Grid Systems", that must to satisfy 18 requirements. Among them, what best distinguishes this class from other hierarchical DGGs, is the Requirement-8, "For each successive level of grid refinement, and for each cell geometry, Cells that are equal area within the specified level of precision".
A 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. The DGGS standard include in its requirements a set of functions and operations that the framework must to offer.
All DGGS's level-0 cells are equal area faces of a Regular polyhedra...

Database modeling

There are many DGGs because there are many representational, optimization and modeling alternatives. All DGG grid is a composition of its cells, and, in the Hierarchical DGG each cell uses a new grid over its local region.
The illustration is not adequate to TIN DEM cases and similar "raw data" structures, where the database not use the cell concept, but nodes and edges: each node is an elevation and each edge is the distance between two nodes.
In general, each cell of the DGG is identified by the coordinates of its region-point. It is also possible, with loss of functionality, to use a "free identifier", that is, any unique number or unique symbolic label per cell, the cell ID. The ID is usually used as spatial index, but is also possible to transform ID into a human-readable label for geocoding applications.
Modern databases use also multiple representations for the same data, offering both, a grid based in the Geoid and a grid-based in the projection.

The DGGS framework

The standard defines the requirements of an hierarchical DGG, including how to operate the grid. Any DGG that satisfies these requirements can be named DGGS. "A DGGS specification SHALL include a DGGS Reference Frame and the associated Functional Algorithms as defined by the DGGS Core Conceptual Data Model".
  1. reference frame elements, and,
  2. functional algorithm elements; comprising:
  3. # quantization operations,
  4. # algebraic operations, and
  5. # interoperability operations.

    History

Discrete Global Grids with cell regions defined by parallels and meridians of latitude/longitude have been used since the earliest days of global geospatial computing. Before it, the discretization of continuous coordinates for practical purposes, with paper maps, occurred only with low granularity. Perhaps the most representative and main example of DGG of this pre-digital era was the 1940s military UTM DGGs, with finner granulaed cell identification for geocoding purposes. Similarly some hierarchical grid exists before geospatial computing, but only in coarse granulation.
A global surface is not required for use on daily geographical maps, and the memory was very expansive before the 2000s, to put all planetary data into the same computer. The first digital global grids were used for data processing of the satellite images and global fluid dynamics modeling.
The first published references to Hierarchical Geodesic DGG systems are to systems developed for atmospheric modeling and published in 1968. These systems have hexagonal cell regions created on the surface of a spherical icosahedron.
The spatial hierarchical grids were subject to more intensive studies in the 1980s, when main structures, as Quadtree, were adapted in image indexing and databases.
While specific instances of these grids have been in use for decades, the term Discrete Global Grids were coined by researchers at Oregon State University in 1997 to describe the class of all such entities.
... OGC standardization in 2017...

Comparison and evolution

The evaluation Discrete Global Grid consists of many aspects, including area, shape, compactness, etc.
Evaluation methods for map projection, such as Tissot's indicatrix, are also suitable for evaluating map projection based Discrete Global Grid.
In addition, averaged ratio between complementary profiles gives a good evaluation of shape distortions for quadrilateral-shaped Discrete Global Grid.
Database development-choices and adaptations are oriented by practical demands for greater performance, reliability or precision. The best choices are being selected and adapted to necessities, propitiating the evolution of the DGG architectures. Examples of this evolution process: from non-hierarchical to hierarchical DGGs; from the use of Z-curve indexes, used by Geohash, to Hilbert-curve indexes, used in modern optimizations, like S2.

Geocode variants

In general each cell of the grid is identified by the coordinates of its region-point, but it is also possible to simplify the coordinate syntax and semantics, to obtain an identifier, as in a classic alphanumeric grids — and find the coordinates of a region-point from its identifier.
Small and fast coordinate representations is a goal in the cell-ID implementations, for any DGG solutions.
There is no loss of functionality when using a "free identifier" instead of a coordinate, that is, any unique number per region-point, the cell ID. So, to transform a coordinate into a human-readable label, and/or compressing the length of the label, is an additional step in the grid representation. This representation is named geocode.
Some popular "global place codes" as ISO 3166-1 alpha-2 for administrative regions or Longhurst code for ecological regions of the globe, are partial in globe's coverage. By other hand, any set of cell-identifiers of a specific DGG can be used as "full-coverage place codes". Each different set of IDs, when used as a standard for data interchange purposes, are named "geocoding system".
There are many ways to represent the value of a cell identifier of a grid: structured or monolithic, binary or not, human-readable or not. Supposing a map feature, like the , represented by its minimum bounding cell or a center-point-cell, the cell ID will be:
Cell IDDGG variant name and parametersID structure; grid resolution
ISO 6709/D in Degrees, CRS=WGS84lat long;
seconds with 2 fractionary places
ISO 6709/F in decimal and CRS=WGS84; 6 fractionary places
ISO 6709/F in decimal in base36 and CRS=WGS84; 4 fractionary places
w21z76281Geohash, base32, WGS84monolithic; 9 characters
6PH57VP3+PRPlusCode, base20, WGS84monolithic; 10 characters
48N 372579 142283UTM, standard decimal, WGS84zone lat long; 3 + 6 + 6 digits
48N 7ZHF 31SBUTM, coordinates base36, WGS84zone lat long; 3 + 4 + 4 digits

All these geocodes represents the same position in the globe, with similar precision, but differ in string-length, separators-use and alphabet.
In some cases the "original DGG" representation can be used. The variants are minor changes, affecting only final representation, for example the base of the numeric representation, or interlacing parts of the structured into only one number or code representation. The most popular variants are used for geocoding applications.

Alphanumeric global grids

DGGs and its variants, with human-readable cell-identifiers, has been used as de facto standard for alphanumeric grids. It is not limited to alphanumeric symbols, but "alphanumeric" is the most usual term.
Geocodes are notations for locations, and in a DGG context, notations to express grid cell IDs. There are a continuous evolution in digital standards and DGGs, so a continuous change in the popularity of each geocoding covention in the last years. Broader adoption also depends on country's government adoption, use in popular mapping platforms, and many other factors.
Examples used in the following list are about "minor grid cell" containing the, 38° 53′ 22.11″ N, 77° 2′ 6.88″ W.
DGG name/varInception and licenseSummary of variantDescription and example
UTM zones/non-overlaped1940s - CC0original without overlapingDivides the Earth into sixty polygonal strips. Example: 18S
Discrete UTM1940s - CC0original UTM integersDivides the Earth into sixty zones, each being a six-degree band of longitude, and uses a secant transverse Mercator projection in each zone. No information about first digital use and conventions. Supposed that standardizations were later ISO's. Example: 18S 323483 4306480
ISO 67091983 - CC0original degree representationThe grid resolutions is a function of the number of digits — with leading zeroes filled when necessary, and fractional part with an appropriate number of digits to represent the required precision of the grid. Example: 38° 53′ 22.11″ N, 77° 2′ 6.88″ W.
ISO 67091983 - CC07 decimal digits representationVariant based in the XML representation where the data structure is a "tuple consisting of latitude and longitude represents 2-dimensional geographic position", and each number in the tuple is a real number discretized with 7 decimal places. Example: 38.889475, -77.035244.
Mapcode2001 - patentedoriginalThe first to adopt a mix code, in conjunction with ISO 3166's codes. In 2001 the algorithms were licensed Apache2, but all system remain patented.
Geohash2008 - CC0originalIs like a bit-enterlaced latLong, and the result is represented with base20.
Geohash2011 - CC0Base36, also named Geohash-36Only changes the base32 to base36, resulting in a little bit compressed code than original Geohash.
What3words2013 patentedoriginal converts 3x3 meter squares into 3 English-dictionary words.
PlusCode2014 - Apache2originalAlso named "Open Location Code". Codes are base20 numbers, and can use city-names, reducing code by the size of the city's bounding box code. Example: 87C4VXQ7+QV.
S2 Cell ID/Base322015 - Apache2original 64-bit integer expressed as base32Hierarchical and very effective database indexing, but no standard representation for base32 and city-prefixes, as PlusCode.
What3words/otherLang2016... 2017 - patentedother languagessame as English, but using other dictionary as reference for words.
Portuguese example, and 10x14m cell: tenaz.fatual.davam.

Other documented variants, but supposed not in use, or to be "never popular":
DGG nameInception - licenseSummaryDescription
C-squares2003 - "no restriction"Latlong interlacedDecimal-interlacing of ISO LatLong-degree representation. It is a "Naive" algorithm when compared with binary-interlacing or Geohash.
GEOREF~1990 - CC0Based on the ISO LatLong, but uses a simpler and more concise notation"World Geographic Reference System", a military / air navigation coordinate system for point and area identification.
Geotude???
GARS2007 - restrictedUSA/NGAReference system developed by the National Geospatial-Intelligence Agency. "the standardized battlespace area reference system across DoD which will impact the entire spectrum of battlespace deconfliction"
WMO squares2001.. - CC0?specializedNOAA's image download cells.... divides a chart of the world with latitude-longitude gridlines into grid cells of 10° latitude by 10° longitude, each with a unique, 4-digit numeric identifier. 36x18 rectangular cells.