Grid (spatial index)
Encyclopedia
In the context of a spatial index, a grid (a.k.a. "mesh", also "global grid" if it covers the entire surface of the globe
) is a regular tessellation
of a manifold
or 2-D surface that divides it into a series of contiguous cells, which can then be assigned unique identifiers and used for spatial indexing purposes. A wide variety of such grids have been proposed or are currently in use, including grids based on "square" or "rectangular" cells, triangular grids or meshes, hexagonal grids, grids based on diamond-shaped cells, and possibly more. The range is broad and the possibilities are expanding.
_illustrated.png)
"Square" or "rectangular" grids are frequently the simplest in use, i.e. for translating spatial information expressed in Cartesian coordinates (latitude
and longitude
) into and out of the grid system. Such grids may or may not be aligned with the gridlines of latitude and longitude; for example, Marsden squares
, World Meteorological Organization squares
, c-squares
and others are aligned, while UTM
, and various national (=local) grid based systems such as the British national grid reference system
are not. In general, these grids fall into two classes, those that are "equal angle", that have cell sizes that are constant in degrees of latitude and longitude but are unequal in area (particularly with varying latitude), or those that are "equal area", that have cell sizes that are constant in distance on the ground (e.g. 100 km, 10 km) but not in degrees of longitude, in particular.
The most influential triangular grid is that entitled "Quaternary Triangular Mesh" or QTM that was developed by Geoffrey Dutton in the early 1980s. It eventually resulted in a thesis entitled "A Hierarchical Coordinate System for Geoprocessing and Cartography" that was published in 1999 (see publications list on Dutton's Spatial Effects website). This grid was also employed as the basis of the rotatable globe that forms part of the Microsoft Encarta
product.
For a discussion of Discrete Global Grid Systems featuring hexagonal and other grids (including diamond-shaped), the paper of Sahr et al. (2003) is recommended reading.
In general, triangular and hexagonal grids are constructed so as to better approach the goals of equal-area (or nearly so) plus more seamless coverage across the poles, which tends to be a problem area for square or rectangular grids since in these cases, the cell width diminishes to nothing at the pole and those cells adjacent to the pole then become 3- rather than 4-sided. Criteria for optimal discrete global gridding have been proposed by both Goodchild and Kimerling in which equal area cells are deemed of prime importance.
Quadtree
s are a specialised form of grid in which the resolution of the grid is varied according to the nature and/or complexity of the data to be fitted, across the 2-d space, and are considered separately under that heading.
s can be more efficient for data storage and speed at search execution time, though they are generally tied to the internal structure of a given data storage system.
The use of such spatial indexes is not limited to digital data; the "index" section of any global or street atlas commonly contains a list of named features (towns, streets, etc.) with associated grid square identifiers, and may be considered a perfectly acceptable example of a spatial index (in this case, typically organised by feature name, though the reverse is conceptually also possible).
In computer science, one often needs to find out all cells a ray is passing through in a grid (for raytracing or collision detection) and that is called Grid Traversal.
Globe
A globe is a three-dimensional scale model of Earth or other spheroid celestial body such as a planet, star, or moon...
) is a regular tessellation
Tessellation
A tessellation or tiling of the plane is a pattern of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of parts of the plane or of other surfaces. Generalizations to higher dimensions are also possible. Tessellations frequently appeared in the art...
of a manifold
Manifold
In mathematics , a manifold is a topological space that on a small enough scale resembles the Euclidean space of a specific dimension, called the dimension of the manifold....
or 2-D surface that divides it into a series of contiguous cells, which can then be assigned unique identifiers and used for spatial indexing purposes. A wide variety of such grids have been proposed or are currently in use, including grids based on "square" or "rectangular" cells, triangular grids or meshes, hexagonal grids, grids based on diamond-shaped cells, and possibly more. The range is broad and the possibilities are expanding.
Types of grids
Latitude
In geography, the latitude of a location on the Earth is the angular distance of that location south or north of the Equator. The latitude is an angle, and is usually measured in degrees . The equator has a latitude of 0°, the North pole has a latitude of 90° north , and the South pole has a...
and longitude
Longitude
Longitude is a geographic coordinate that specifies the east-west position of a point on the Earth's surface. It is an angular measurement, usually expressed in degrees, minutes and seconds, and denoted by the Greek letter lambda ....
) into and out of the grid system. Such grids may or may not be aligned with the gridlines of latitude and longitude; for example, Marsden squares
Marsden square
Marsden square mapping or Marsden squares is a system that divides a chart of the world with latitude-longitude gridlines between 80°N and 70°S latitudes into grid cells of 10° latitude by 10° longitude, each with a unique, numeric identifier...
, World Meteorological Organization squares
World Meteorological Organization squares
World Meteorological Organization squares or WMO squares is a system of geocodes that 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...
, c-squares
C-squares
C-squares is a system of geocodes that provides a basis for simple spatial indexing of geographic features or data. It was devised by Tony Rees of CSIRO Marine and Atmospheric Research in 2001-2, and described in the literature in 2003...
and others are aligned, while UTM
Universal Transverse Mercator coordinate system
The Universal Transverse Mercator geographic coordinate system uses a 2-dimensional Cartesian coordinate system to give locations on the surface of the Earth. It is a horizontal position representation, i.e...
, and various national (=local) grid based systems such as the British national grid reference system
British national grid reference system
The Ordnance Survey National Grid reference system is a system of geographic grid references used in Great Britain, different from using latitude and longitude....
are not. In general, these grids fall into two classes, those that are "equal angle", that have cell sizes that are constant in degrees of latitude and longitude but are unequal in area (particularly with varying latitude), or those that are "equal area", that have cell sizes that are constant in distance on the ground (e.g. 100 km, 10 km) but not in degrees of longitude, in particular.
The most influential triangular grid is that entitled "Quaternary Triangular Mesh" or QTM that was developed by Geoffrey Dutton in the early 1980s. It eventually resulted in a thesis entitled "A Hierarchical Coordinate System for Geoprocessing and Cartography" that was published in 1999 (see publications list on Dutton's Spatial Effects website). This grid was also employed as the basis of the rotatable globe that forms part of the Microsoft Encarta
Encarta
Microsoft Encarta was a digital multimedia encyclopedia published by Microsoft Corporation from 1993 to 2009. , the complete English version, Encarta Premium, consisted of more than 62,000 articles, numerous photos and illustrations, music clips, videos, interactive contents, timelines, maps and...
product.
For a discussion of Discrete Global Grid Systems featuring hexagonal and other grids (including diamond-shaped), the paper of Sahr et al. (2003) is recommended reading.
In general, triangular and hexagonal grids are constructed so as to better approach the goals of equal-area (or nearly so) plus more seamless coverage across the poles, which tends to be a problem area for square or rectangular grids since in these cases, the cell width diminishes to nothing at the pole and those cells adjacent to the pole then become 3- rather than 4-sided. Criteria for optimal discrete global gridding have been proposed by both Goodchild and Kimerling in which equal area cells are deemed of prime importance.
Quadtree
Quadtree
A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. This...
s are a specialised form of grid in which the resolution of the grid is varied according to the nature and/or complexity of the data to be fitted, across the 2-d space, and are considered separately under that heading.
Grid-based spatial indexing
In practice, construction of grid-based spatial indexes entails allocation of relevant objects to their position or positions in the grid, then creating an index of object identifiers vs. grid cell identifiers for rapid access. This is an example of a "space-driven" or data independent method, as opposed to "data-driven" or data dependent method, as discussed further in Rigaux et al. (2002)). A grid-based spatial index has the advantage that the structure of the index can be created first, and data added on an ongoing basis without requiring any change to the index structure; indeed, if a common grid is used by disparate data collecting and indexing activities, such indexes can easily be merged from a variety of sources. On the other hand, data driven structures such as R-treeR-tree
R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984 and has found significant use in both research and real-world applications...
s can be more efficient for data storage and speed at search execution time, though they are generally tied to the internal structure of a given data storage system.
The use of such spatial indexes is not limited to digital data; the "index" section of any global or street atlas commonly contains a list of named features (towns, streets, etc.) with associated grid square identifiers, and may be considered a perfectly acceptable example of a spatial index (in this case, typically organised by feature name, though the reverse is conceptually also possible).
Other uses
The individual cells of a grid system can also be useful as units of aggregation, for example as a precursor to data analysis, presentation, mapping, etc. For some applications (e.g., statistical analysis), equal-area cells may be preferred, although for others this may not be a prime consideration.In computer science, one often needs to find out all cells a ray is passing through in a grid (for raytracing or collision detection) and that is called Grid Traversal.
See also
- Geodesic gridGeodesic gridA geodesic grid is a technique used to model the surface of a sphere with a subdivided polyhedron, usually an icosahedron.-Introduction:...
- Spatial index
- Grid referenceGrid referenceGrid references define locations on maps using Cartesian coordinates. Grid lines on maps define the coordinate system, and are numbered to provide a unique reference to features....
- GeocodeGeocodeGEOCODE is a standardized all-natural number representation format specification for geospatial coordinate measurements that provide details of the exact location of geospatial point at, below, or above the surface of the earth at a specified moment of time.Geocode is patented under US Patents...
- QuadtreeQuadtreeA quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. This...
- R-treeR-treeR-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984 and has found significant use in both research and real-world applications...
- Alpha-numeric gridAlpha-numeric gridAn alphanumeric grid is a simple coordinate system on a grid in which each cell is identified by a combination of a letter and a number....