A discrete global grid (DGG) is a
mosaic
A mosaic is a pattern or image made of small regular or irregular pieces of colored stone, glass or ceramic, held in place by plaster/mortar, and covering a surface. Mosaics are often used as floor and wall decoration, and were particularly pop ...
that covers the entire Earth's surface.
Mathematically it is a
space partitioning
In geometry, space partitioning is the process of dividing a space (usually a Euclidean space) into two or more disjoint subsets (see also partition of a set). In other words, space partitioning divides a space into non-overlapping regions. Any ...
: it consists of a set of non-empty regions that form a
partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
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
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
partition, resulting in a "series of discrete global grids with progressively finer resolution",
forming a hierarchical grid, it is called a hierarchical DGG (sometimes "global hierarchical tessellation"
or "DGG system").
Discrete global grids are used as the geometric basis for the building of geospatial
data structure
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
s. 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.
The most usual grids are for
horizontal position representation
A position representation is the parameters used to express a position relative to a reference. When representing positions relative to the Earth, it is often most convenient to represent ''vertical position'' (height or depth) separately, and to ...
, using a standard
datum
In the pursuit of knowledge, data (; ) is a collection of discrete values that convey information, describing quantity, quality, fact, statistics, other basic units of meaning, or simply sequences of symbols that may be further interpreted. ...
, like
WGS84
The World Geodetic System (WGS) is a standard used in cartography, geodesy, and satellite navigation including GPS. The current version, WGS 84, defines an Earth-centered, Earth-fixed coordinate system and a geodetic datum, and also descr ...
. 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 spatial database is a general-purpose database (usually a relational database) that has been enhanced to include spatial data that represents objects defined in a geometric space, along with tools for querying and analyzing such data. Most sp ...
, a DGG can assign unique identifiers to each grid cell, using it for spatial indexing purposes, in
geodatabases or for
geocoding
Address geocoding, or simply geocoding, is the process of taking a text-based description of a location, such as an address or the name of a place, and returning geographic coordinates, frequently latitude/longitude pair, to identify a locatio ...
.
Reference model of the globe
The "globe", in the DGG concept, has no strict semantics, but in geodesy a so-called "
grid reference
A projected coordinate system, also known as a projected coordinate reference system, a planar coordinate system, or grid reference system, is a type of spatial reference system that represents locations on the Earth using cartesian coordin ...
system" is a grid that divides space with precise positions relative to a
datum
In the pursuit of knowledge, data (; ) is a collection of discrete values that convey information, describing quantity, quality, fact, statistics, other basic units of meaning, or simply sequences of symbols that may be further interpreted. ...
, that is an approximated a "standard model of the
Geoid
The geoid () is the shape that the ocean surface would take under the influence of the gravity of Earth, including gravitational attraction and Earth's rotation, if other influences such as winds and tides were absent. This surface is extended ...
". So, in the role of Geoid, the "globe" covered by a DGG can be any of the following objects:
* The
''topographical surface'' of the Earth, when each cell of the grid has its surface-position coordinates and the elevation in relation to the
standard Geoid. Example: grid with coordinates (''φ'',''λ'',''z'') where ''z'' is the elevation.
* A
standard ''Geoid surface''. The z coordinate is zero for all grid, thus can be omitted, (''φ'',''λ'').
Ancient standards, before 1687 (the Newton's Principia publication), used a "reference sphere"; in nowadays the Geoid is mathematically abstracted as
reference ellipsoid
An Earth ellipsoid or Earth spheroid is a mathematical figure approximating the Earth's form, used as a reference frame for computations in geodesy, astronomy, and the geosciences. Various different ellipsoids have been used as approximations ...
.
** A ''simplified Geoid'': sometimes an old geodesic standard (e.g.
SAD69) or a non-geodesic surface (e. g. perfectly spherical surface) must be adopted, and will be covered by the grid. In this case, cells must be labeled with non-ambiguous way, ''(φ',λ')'', and the transformation (''φ'',''λ'') ⟾ (''φ''′,''λ''′) must be known.
* A
''projection surface''. Typically the geographic coordinates (''φ'',''λ'') are projected (
with some distortion) onto the 2D mapping plane with 2D Cartesian coordinates (''x'', ''y'').
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
A regular polyhedron is a polyhedron whose symmetry group acts transitively on its flags. A regular polyhedron is highly symmetrical, being all of edge-transitive, vertex-transitive and face-transitive. In classical contexts, many different equival ...
and other topological equivalents of sphere led to the most promising known options to be covered by DGGs,
because "spherical projections preserve the ''correct topology'' of the Earth – there are no singularities or discontinuities to deal with".
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:
* The recovered object: the object type in the role of globe. If there is no projection, the object covered by the grid is the Geoid, the Earth or a sphere; else is the geometry class of the projection surface (e.g. a cylinder, a cube or a cone).
* Projection type: absent (no projection) or present. When present, its characterization can be summarized by the
projection's goal property (e.g. equal-area, conformal, etc.) and the class of the corrective function (e.g. trigonometric, linear, quadratic, etc.).
NOTE: when the DGG is covering a projection surface, in a context of
data provenance
Data lineage includes the data origin, what happens to it, and where it moves over time. Data lineage gives visibility while greatly simplifying the ability to trace errors back to the root cause in a data analytics process.
It also enables repl ...
, the metadata about reference-Geoid is also important — typically informing its
ISO 19111's CRS value, with no confusion with the projection surface.
Types and examples
The main distinguishing feature to classify or compare DGGs is the use or not of hierarchical grid structures:
* In hierarchical reference systems each cell is a "box reference" to a subset of cells, and cell identifiers can express this hierarchy in its numbering logic or structure.
* In non-hierarchical reference systems each cell have a distinct identifier and represents a fixed-scale region of the space. The discretization of the
Latitude/Longitude system is the most popular, and the standard reference for conversions.
Other usual criteria to classify a DGG are tile-shape and granularity (''grid resolution''):
* Tile regularity and shape: there are regular, semi-regular or
irregular grid
An unstructured grid or irregular grid is a tessellation of a part of the Euclidean plane or Euclidean space by simple shapes, such as triangles or tetrahedra, in an irregular pattern. Grids of this type may be used in finite element analysis w ...
. As in generic
tilings by regular polygons, is possible to tiling with regular face (like wall tiles can be rectangular, triangular, hexagonal, etc.), or with same face type but changing its size or angles, resulting in semi-regular shapes.
Uniformity of shape and regularity of metrics provide better grid-indexing algorithms. Although it has less practical use, totally irregular grids are possible, such in a
Voronoi coverage.
* Fine or coarse granulation (cell size): modern DGGs are parametrizable in its grid resolution, so, it is a characteristic of the final DGG instance, but not useful to classify DGGs, except when the DGG-type must use a specific resolution or have a discretization limit. A "fine" granulation grid is non-limited and "coarse" refers to drastic limitation. Historically the main limitations are related to digital/analogic media, the compression/expanded representations of the grid in a database, and the memory limitations to store the grid. When a quantitative characterization is necessary, the average area of the grid cells or average distance between cell centers can be adopted.
Non-hierarchical grids
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
![Great Britain Box-hiearchy](https://upload.wikimedia.org/wikipedia/commons/b/b0/Great_Britain_Box-hiearchy.png)
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 (grid-level-1), 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 is a class of hierarchical DGG's named by the
Open Geospatial Consortium
The Open Geospatial Consortium (OGC), an international voluntary consensus standards organization for geospatial content and location-based services, sensor web and Internet of Things, GIS data processing and data sharing. It originated in 199 ...
(OGC) as "discrete global grid systems" (DGGS), 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"''.
[Open Geospatial Consortium (2017), "Topic 21: Discrete Global Grid Systems Abstract Specification"]
Document 15-104r5 version 1.0
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
A regular polyhedron is a polyhedron whose symmetry group acts transitively on its flags. A regular polyhedron is highly symmetrical, being all of edge-transitive, vertex-transitive and face-transitive. In classical contexts, many different equival ...
...
Database modeling
520px, In all DGG databases the grid is a Class diagram#Composition, composition of its cells. The region and centralPoint are illustrated as typical properties or subclasses. The cell identifier (cell ID) is also an important property, used as internal index and/or as public label of the cell (instead the point-coordinates) in
geocoding
Address geocoding, or simply geocoding, is the process of taking a text-based description of a location, such as an address or the name of a place, and returning geographic coordinates, frequently latitude/longitude pair, to identify a locatio ...
applications. Sometimes, as in the MGRS grid, the coordinates make the role of ID.
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 (that geometrically is the triangular region), 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 (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
A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four ...
or
k-d tree), but is also possible to transform ID into a human-readable label for
geocoding
Address geocoding, or simply geocoding, is the process of taking a text-based description of a location, such as an address or the name of a place, and returning geographic coordinates, frequently latitude/longitude pair, to identify a locatio ...
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.
The DGGS framework
The standard defines the requirements of a 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"''.
: ''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.'' Main concepts of the DGGS Core Conceptual Data Model:
# reference frame elements, and,
# functional algorithm elements; comprising:
## quantization operations,
## algebraic operations, and
## interoperability operations.
History
Discrete global grids with cell regions defined by parallels and meridians of
latitude
In geography, latitude is a coordinate that specifies the north– south position of a point on the surface of the Earth or another celestial body. Latitude is given as an angle that ranges from –90° at the south pole to 90° at the north pol ...
/
longitude
Longitude (, ) is a geographic coordinate that specifies the east–west position of a point on the surface of the Earth, or another celestial body. It is an angular measurement, usually expressed in degrees and denoted by the Greek letter l ...
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 finer granulated cell identification for
geocoding
Address geocoding, or simply geocoding, is the process of taking a text-based description of a location, such as an address or the name of a place, and returning geographic coordinates, frequently latitude/longitude pair, to identify a locatio ...
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 expensive 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 (
climatic
Climate is the long-term weather pattern in an area, typically averaged over 30 years. More rigorously, it is the mean and variability of meteorological variables over a time spanning from months to millions of years. Some of the meteorologic ...
and
oceanographic
Oceanography (), also known as oceanology and ocean science, is the scientific study of the oceans. It is an Earth science, which covers a wide range of topics, including ecosystem dynamics; ocean currents, waves, and geophysical fluid dynamics ...
) 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
In geometry, an icosahedron ( or ) is a polyhedron with 20 faces. The name comes and . The plural can be either "icosahedra" () or "icosahedrons".
There are infinitely many non- similar shapes of icosahedra, some of them being more symmetrica ...
.
The spatial hierarchical grids were subject to more intensive studies in the 1980s, when main structures, as
Quadtree
A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four ...
, were adapted in image indexing and databases.
While specific instances of these grids have been in use for decades, the term ''discrete global grids'' was coined by researchers at
Oregon State University
Oregon State University (OSU) is a public land-grant, research university in Corvallis, Oregon. OSU offers more than 200 undergraduate-degree programs along with a variety of graduate and doctoral degrees. It has the 10th largest engineering co ...
in 1997
to describe the class of all such entities.
... OGC standardization in 2017...
Comparison and evolution
![Comparing-Geoash-Hilbert2](https://upload.wikimedia.org/wikipedia/commons/c/c2/Comparing-Geoash-Hilbert2.png)
The evaluation discrete global grid consists of many aspects, including area, shape, compactness, etc.
Evaluation methods for
map projection
In cartography, map projection is the term used to describe a broad set of transformations employed to represent the two-dimensional curved surface of a globe on a plane. In a map projection, coordinates, often expressed as latitude and longitud ...
, such as
Tissot's indicatrix
In cartography, a Tissot's indicatrix (Tissot indicatrix, Tissot's ellipse, Tissot ellipse, ellipse of distortion) (plural: "Tissot's indicatrices") is a mathematical contrivance presented by French mathematician Nicolas Auguste Tissot in 1859 ...
, are also suitable for evaluating map projection-based discrete global grid.
In addition, averaged ratio between complementary profiles (AveRaComp) 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 (a ''naive algorithm'' based in digits-interlacing), 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 (or unique symbolic label) 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
A geocode is a code that represents a geographic entity (location or object). It is a unique identifier of the entity, to distinguish it from others in a finite set of geographic entities. In general the ''geocode'' is a human-readable and ...
.
Some popular "
global place codes" as
ISO 3166-1 alpha-2
ISO 3166-1 alpha-2 codes are two-letter country codes defined in ISO 3166-1, part of the ISO 3166 standard published by the International Organization for Standardization (ISO), to represent countries, dependent territories, and special areas of ...
for administrative regions or
Longhurst code
Longhurst code refers to a set of geospatial four-letter geocodes for referencing geographic regions in oceanography.
The set of 56 geocodes represent biogeochemical provinces that partition the pelagic environment. It is assumed that each pr ...
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 (''cell-ID'') of a grid: structured or monolithic, binary or not, human-readable or not. Supposing a map feature, like the
Singapore's Merlion fountaine (~5m scale feature), represented by its
minimum bounding cell or a center-point-cell, the ''cell ID'' will be:
All these geocodes represents the same position in the globe, with similar precision, but differ in
string-length, separators-use and alphabet (non-separator 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.
Alphanumeric global grids
DGGs and its variants, with
human-readable
A human-readable medium or human-readable format is any encoding of data or information that can be naturally read by humans.
In computing, ''human-readable'' data is often encoded as ASCII or Unicode text, rather than as binary data. In most c ...
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 convention 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
.
Other documented systems:
See also
*
Grid reference
A projected coordinate system, also known as a projected coordinate reference system, a planar coordinate system, or grid reference system, is a type of spatial reference system that represents locations on the Earth using cartesian coordin ...
*
Geodesic grid
A geodesic grid is a spatial grid based on a geodesic polyhedron or Goldberg polyhedron.
Construction
A geodesic grid is a global Earth reference that uses triangular tiles based on the subdivision of a polyhedron (usually the icosahedron, a ...
*
List of geocoding systems
*
References
External links
OGC DGGSStandards Working Group
Discrete Global Gridspage at the Computer Science department at Southern Oregon University
BUGS climate model{{Webarchive, url=https://web.archive.org/web/20061215105237/http://kiwi.atmos.colostate.edu/BUGS/geodesic/ , date=2006-12-15 page on geodesic grids
Research Institute for World Grid squarespage on World Grid Squares
Cubic Postcodea valid protocol for an international postcode system using a grid of cubic metres
Earth grid models for exhibition use 3D-printable models of some Earth grids.
Geographic coordinate systems