This page uses content from Wikipedia and is licensed under CC BYSA.
Geodesy  

Fundamentals 

Concepts 

Standards (History)


A Discrete Global Grid (DGG) is a mosaic which covers the entire Earth's surface. Mathematically it is a space partitioning: it consists of a set of nonempty regions that form a partition of the Earth's surface.^{[1]} In a usual gridmodeling strategy, to simplify position calculations, each region is represented by a point, abstracting the grid as a set of regionpoints. Each region or regionpoint 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",^{[2]} forming a hierarchical grid, it is named Hierarchical DGG (sometimes "DGG system").
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 (in the hierarchical case) 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.^{[1]}
The most usual grids are for horizontal position representation, using a standard datum, like WGS84. In this context is commom 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.
The "globe", in the DGG concept, have no strict semantic; but in Geodesy a socalled "Grid Reference System" is a grid that divides space with precise positions relative to a datum, that is an approximated a "standard model of the Geoid". So, in the role of Geoid, the "globe" covered by a DGG can be any of the following objects:
As a global modeling process, modern DGGs, when including projection process, tend to avoid surfaces like cylinder or a conic solids that result in discontinuities and indexing problems. Regular polyhedra and other topological equivalents of sphere led to the most promising known options to be covered by DGGs,^{[1]} because "spherical projections preserve the correct topology of the Earth – there are no singularities or discontinuities to deal with".^{[3]}
When working with a DGG it is important to specify which of these options was adopted. So, the characterization of the reference model of the globe of a DGG can be summarized by:
NOTE: when the DGG is covering a projection surface, in a context of data provenance, the metadata about referenceGoid is also important — typical informing its ISO 19111's CRS value, with no confusion with the projection surface.
The main distinguishing feature to classify or compare DGGs is the use or not of an hierarchical grid structures:
Other usual criteria to classify a DGG are tileshape and granularity (grid resolution):
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:
UTM zones: Divides the Earth into sixty (strip) zones, each being a sixdegree band of longitude. In digital media removes overlapping zone. Use secant transverse Mercator projection in each zone. Define 60 secant cylinders, 1 per zone. The UTM zones was enhanced by Military Grid Reference System (MGRS), by addition of the Latitude bands.  
inception: 1940s  coverd object: cylinder (60 options)  projection: UTM or latlong  irregular tiles: polygonal strips  grabularity: coarse 
(modern) UTM  Universal Transverse Mercator: Is a discretization of the continuous UTM grid, with a kind of 2level hierarchy, where the first level (coarse grain) correspond to the "UTM zones with latitude bands" (the MGRS), use the same 60 cylinders as referenceprojection objects. Each finegrain cell is designated by an structured ID composed by "grid zone designator", "the 100,000meter square identifier" and "numerical location". The grid resolution is a direct function of the number of digits in the coordinates, that is also standarized. For instance the cell 17N 630084 4833438 is a ~10mx10m square.PS: this standard use 60 distinct cylinders for projections. There are also "Regional Transverse Mercator" (RTM or UTM Regional) and "Local Transverse Mercator" (LTM or UTM Local) standards, with more specific cylinders, for better fit and precision at the point of interest.  
inception: 1950s  coverd object: cylinder (60 options)  projection: UTM  rectangular tiles: equalangle (conformal)  grabularity: fine 
ISO 6709: Discretizes the traditional "graticule" representation and the modern numericcoordinate cellbased locations. The granularity is fixed by a simple convention of the numeric representation, e. g. onedegree graticule, .01 degree graticule, etc. and it results in nonequalarea cells over the grid. The shape of the cells are rectangular except in the poles, where they are triangular. The numeric representation is standardized by two main conventions: degrees (Annex D) and decimal (Annex F). The grid resolution is controlled by the number of digits (Annex H).  
inception: 1983  coverd object: Geoid (any ISO 19111's CRS)  projection: none  rectangular tiles: uniform spheroidal shape  grabularity: fine 
Primary DEM (TIN DEM): A vectorbased triangular irregular network (TIN) — the TIN DEM dataset is also referred to as a primary (measured) DEM. Many DEM are created on a grid of points placed at a regular angular increments of latitude and longitude. Examples include the Global 30 ArcSecond Elevation Dataset (GTOPO30).^{[4]} and the Global Multiresolution Terrain Elevation Data 2010 (GMTED2010).^{[5]} Triangulated irregular network is a representation of a continuous surface consisting entirely of triangular facets.  
inception: 1970s  coverd object: terrain  projection: none  triangular nonuniform tiles: parametrized (vectorial)  grabularity: fine 
Arakawa grids: Was used for Earth system models for meteorology and oceanography — for example, the Global Environmental Multiscale Model (GEM) uses Arakawa grids for Global Climate Modeling.^{[6]} The called "Agrid" the reference DGG, to be compared with other DGGs. Used in the 1980s with ~500x500 space resolutions.  
inception: 1977  coverd object: geoid  projection: ?  rectangular tiles: parametric, spacetime  grabularity: medium 
WMO squares: A specialiezed grid, used uniquely by NOAA, divides a chart of the world with latitudelongitude gridlines into grid cells of 10° latitude by 10° longitude, each with a unique, 4digit numeric identifier (the first digit identifies quadrants NE/SE/SW/NW).  
inception: 2001  coverd object: geoid  projection: none  Regular tiles: 36x18 rectangular cells  grabularity: coarse 
World Grid Squares: Are a compatible extension of Japanese Grid Squares standardized in Japan Industrial Standards (JIS X0410) to worldwide. The World Grid Square code can identify grid squares covering the world based on 6 layers. We can express a grid square by using from 6 to 13 digit sequence with accordance to its resolution.^{[7]}  
inception: ?  coverd object: geoid  projection: ?  ? tiles: ?  grabularity: ? 
The right aside illustration show 3 boundary maps of the coast of Great Britain. The first map was covered by a gridlevel0 with 150 km size cells. Only a grey cell in the center, with no need of zoom for detail, remains level0; all other cells of the second map was partitioned into fourcellsgrid (gridlevel1), each with 75 km. In the third map 12 cells level1 remains as grey, all other was partitioned again, each level1cell transformed into a level2grid.
Examples of DGGs that use such recursive process, generating hierarchical grids, include:
ISEA Discrete Global Grids (ISEA DGGs): Are a class of grids proposed by researchers at Oregon State University.^{[1]} The grid cells are created as regular polygons on the surface of an icosahedron, and then inversely projected using the Icosahedral Snyder Equal Area (ISEA) map projection^{[8]} to form equal area cells on the sphere. Cells may be hexagons, triangles, or quadrilaterals. Multiple resolutions are indicated by choosing an aperture, or ratio between cell areas at consecutive resolutions. Some applications of ISEA DGGs include data products generated by the European Space Agency's Soil Moisture and Ocean Salinity (SMOS) satellite, which uses an ISEA4H9 (aperture 4 Hexagonal DGGS resolution 9),^{[9]} and the commercial software Global Grid Systems Insight,^{[10]} which uses an ISEA3H (aperture 3 Hexagonal DGGS).  
inception: 1992..2004  coverd object: ?  projection: equalarea  parametrized (hexagons, triangles or quadrilaterals) tiles: equalarea  grabularity: fine 
COBE  Quadrilateralized Spherical cube: Cube:^{[11]} Similar decomposition of sphere tham HEALPix and S2. But does not use spacefilling curve, edges are not geodesics, and projection is more complicated.  
inception: 1975..1991  coverd object: cube  projection: Curvilinear perspective  quadrilateral tiles: uniform areapreserving  grabularity: fine 
Quaternary Triangular Mesh (QTM): QTM has triangularshaped cells created by the 4fold recursive subdivision of a spherical octahedron.^{[12]}  
inception: 1999 ... 2005  coverd object: octahedron (or other)  projection: Lambert's equalarea cylindrical  triangular tiles: uniform areapreserved  grabularity: fine 
Hierarchical Equal Area isoLatitude Pixelization (HEALPix): HEALPix has equal area quadrilateralshaped cells and was originally developed for use with fullsky astrophysical data sets.^{[13]} The usual projecttion is "H=4, K=3 HEALPix projection". Main advantage, comparing with others of same indexing niche as S2, "is suitable for calculations involving spherical harmonics".^{[14]}  
inception: 2006  coverd object: Geoid  projection: (K,H) parametrized HEALPix projection  qradrilater tiles: uniform areapreserved  grabularity: fine 
Hierarchical Triangular Mesh (HTM): Developed in 2003...2007, HTM "is a multi level, recursive decomposition of the sphere. It start with an octahedron, let this be level 0. As you project the edges of the octahedron onto the (unit) sphere creates 8 spherical triangles, 4 on the Northern and 4 on the Southern hemispheres".^{[15]} The first public operational version seems^{[16]} the HTMv2 in 2004.  
inception: 2004  coverd object: Geoid  projection: none  triangular tiles: spherical equilateres  grabularity: fine 
Geohash: Latitude and longitude are merged, enterlacing bits in the joined number. The binary result is represented with base32, offering a compact humanreadable code. When used as spatial index, corresponds to a Zorder curve. There are some variants like Geohash36.  
inception: 2008  coverd object: Geoid  projection: none  semiregular tiles: rectangular  grabularity: fine 
S2 / S2Region: The "S2 Grid System" is part of the "S2 Geometry Library"^{[17]} (the name is derived from the mathematical notation for the nsphere, S²). It implements an index system based on cube projection and the spacefilling Hilbert curve, developed at Google.^{[18]}^{[19]} The S2Region of S2 is the most general representation of its cells, where cellposition and metric (e.g. area) can be calculated. Each S2Region is a subgrid, resulting in a hierarchy limited to 31 levels. At level30 resolution is estimated^{[20]} in 1 cm², at level0 is 85011012 km². The cellidentifier of the hierarchical grid of a cube face (6 faces) have and ID of 60 bits (so "every cm² on Earth can be represented using a 64bit integer).  
inception: 2015  coverd object: cube  projection: spherical projections in each cube face using quadratic function  semiregular tiles: quadrilateral projections  grabularity: fine 
S2 / S2LatLng: The DGG supplied by S2LatLng representation, like an ISO 6709 grid, but hierarchical and with its specific cell shape.  
inception: 2015  coverd object: Geoid or sphere  projection: none  semiregular tiles: quadrilateral  grabularity: fine 
S2 / S2CellId: The DGG supplied by S2CellId representation. Each cellID is a 64bit unsigned integer unique identifier, for any hierarchy level.  
inception: 2015  coverd object: cube  projection: ?  semiregular tiles: quadrilateral  grabularity: fine 
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 use 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 (that geometrically is the triangular region), but nodes and edges: each node is an elevation and each edge is the distance between to nodes.
In general each cell of the DGG is identified by the coordinates of its regionpoint (illustrated as the centralPoint of a database representation). 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 (such as internal Quadtree or kd tree), but is also possible to transform ID into a humanreadable label for geocoding applications.
Modern databases (e.g. using S2 grid) use also multiple representations for the same data, offering both, a grid (or cell region) based in the Geoid and a grid based in the projection.
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 predigital 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 was used for data processing of the satellite images and global (climatic and oceanographic) 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. ^{[21]} ^{[22]}
The spatial hierarchical grids was subject to more intensive studies in the 1980s,^{[23]} when main structures, as Quadtree, was 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^{[2]} to describe the class of all such entities.
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 (AveRaComp) ^{[24]} gives a good evaluation of shape distortions for quadrilateralshaped Discrete Global Grid.
Database developmentchoices 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 nonhierarchical to hierarchical DGGs; from the use of Zcurve indexes (a naive algorithm based in digitsinterlacing), used by Geohash, to Hilbertcurve indexes, used in modern optimizations, like S2.
In general each cell of the grid is identified by the coordinates of its regionpoint, 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 regionpoint from its identifier. Small and fast coordinate representations is a goal in the cellID implementations, for any DGG solutions.
There are no loss of functionality when using a "free identifier" instead a coodinate, that is, any unique number or unique symbolic label per regionpoint, the cell ID. So, to transform a coordinate into a humanreadable label, and/or compressing the length of the label, is an additional step in the grid representation.
Some popular "global place codes" as ISO 31661 alpha2 for administrative regions or Longhurst code for ecological regions of the globe, are partial in globe's coverage. By other hand, any set of cellidentifiers of a specific DGG can be used as "fullcoverage 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 (cellID) of a grid: structured or monolithic, binary or not, humanreadable or not. Supposing a map feature, like the Singapore's Merlion fountaine (~5m scale feature), represented by its minimum bounding cell or a centerpointcell, the cell ID will be:
Cell ID  DGG variant name and parameters  ID structure; grid resolution 

(1° 17′ 13.28″ N, 103° 51′ 16.88″ E)  ISO 6709/D in Degrees (Annex ), CRS=WGS84  lat(deg min sec dir ) long(deg min sec dir ); seconds with 2 fractionary places 
(1.286795, 103.854511)  ISO 6709/F in decimal and CRS=WGS84  (lat,long) ; 6 fractionary places

(1.65AJ, 2V.IBCF)  ISO 6709/F in decimal in base36 (nonISO) and CRS=WGS84  (lat,long) ; 4 fractionary places

w21z76281  Geohash, base32, WGS84  monolithic; 9 characteres 
6PH57VP3+PR  PlusCode, base20, WGS84  monolithic; 10 characteres 
48N 372579 142283  UTM, satandard decimal, WGS84  zone lat long ; 3 + 6 + 6 digits

48N 7ZHF 31SB  UTM, coordinates base36, WGS84  zone lat long ; 3 + 4 + 4 digits

All these geocodes represents the same position in the globe, with similar precision, but differ in stringlength, separatorsuse and alphabet (nonseparator characters). 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.
DGGs and its variants, with humanreadable cellidentifiers, 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 Washington obelisk, 38° 53′ 22.11″ N, 77° 2′ 6.88″ W
.
DGG name/var  Inception and license  Summary of variant  Description and example 

UTM zones/nonoverlaped  1940s  CC0  original without overlaping  Divides the Earth into sixty polygonal strips. Example: 18S

Discrete UTM  1940s  CC0  original UTM integers  Divides the Earth into sixty zones, each being a sixdegree band of longitude, and uses a secant transverse Mercator projection in each zone. No information about first digital use and conentions. Supposed that standardizations was later ISO's (1980s). Example: 18S 323483 4306480

ISO 6709  1983  CC0  original degree representation  The grid resolutions is a function of the number of digits — with leading zeroes filled when necessary, and fractional part with appropriate number of digits to represent the required precision of the grid. Example: 38° 53′ 22.11″ N, 77° 2′ 6.88″ W .

ISO 6709  1983  CC0  7 decimal digits representation  Variant based in the XML representation where the data structure is a "tuple consisting of latitude and longitude represents 2dimensional geographic position", and each number in the tuple is a real number discretized with 7 decimal places. Example: 38.889475, 77.035244 .

Mapcode  2001  patented  original  The first to adopt a mix code, in conjunction with ISO 3166's codes (country or city). In 2001 the algorithms was licensed Apache2, but all system remains patented. 
Geohash  2008  CC0  original  Is like a bitenterlaced latLong, and the result is represented with base20. 
Geohash  2011  CC0  Base36, also named Geohash36  Only changes the base32 to base36, resulting in a little bit compressed code tham original Geohash. 
What3words  2013 patented  original (English)  converts 3x3 meter squares into 3 Englishdictionary words.^{[25]} 
PlusCode  2014  Apache2^{[26]}  original  Also named "Open Location Code". Codes are base20 numbers, and can use citynames, reducing code by the size of the city's bounding box code (like Mapcode strategy). Example: 87C4VXQ7+QV .

S2 Cell ID/Base32  2015  Apache2^{[27]}  original 64bit integer expressed as base32  Hierarchical and very effective database indexing, but no standard representation for base32 and cityprefixes, as PlusCode. 
What3words/otherLang  2016 ... 2017  patented  other languages  same 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 name  Inception  license  Summary  Description 

Csquares  2003  "no restriction"  Latlong interlaced  Decimalinterlacing of ISO LatLongdegree representation. It is a "Naive" algorithm when compared with binaryinterlacing or Geohash. 
GEOREF  ~1990  CC0  Based 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  ?  ?  ? 
GARS  2007  restricted  USA/NGA  Reference system developed by the National GeospatialIntelligence Agency (NGA). "the standardized battlespace area reference system across DoD which will impact the entire spectrum of battlespace deconfliction" 
WMO squares  2001..  CC0?  specialiezed  NOAA's image download cells. ... divides a chart of the world with latitudelongitude gridlines into grid cells of 10° latitude by 10° longitude, each with a unique, 4digit numeric identifier. 36x18 rectangular cells (labeled by four digits, the first digit identify quadrants NE/SE/SW/NW). 