# Grid (spatial index)

﻿
Grid (spatial index)

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.

Types of grids

"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 [http://www.spatial-effects.com/SE-papers1.html 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 hexagonal and other grids (including diamond-shaped), the paper of Sahr "et al". (2003) [ [http://www.sou.edu/cs/sahr/dgg/pubs/gdggs03.pdf#search=%22hexagonal%20grid%20kimerling%22 Kevin Sahr, Denis White, and A. Jon Kimerling. 2003. Geodesic Discrete Global Grid Systems. Cartography and Geographic Information Science, 30(2), 121-134.] ] 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.

Quadtrees 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)) [Rigaux, P., Scholl, M., and Voisard, A. 2002. Spatial Databases - with application to GIS. Morgan Kaufmann, San Francisco, 410pp.] . 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-trees 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.

References

* [http://www.star.le.ac.uk/~cgp/ag/skyindex.html Indexing the Sky - Clive Page] - Grid indexes for astronomy

ee also

*Geodesic grid
*Spatial index
*Grid reference
*Geocode
*R-tree
*Hierarchical Triangular Mesh

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Spatial index — Spatial indexes are used by spatial databases to optimize spatial queries. Indexes used by non spatial databases cannot effectively handle features such as how far two points differ and whether points fall within a spatial area of interest.… …   Wikipedia

• Grid — Several fields use or develop the idea of a grid: Arrays of squares or rectangles * Grid plan, a city plan in which streets run at right angles to form a grid of city blocks * Grid view or datagrid, a graphical user interface element that… …   Wikipedia

• Grid illusion — A grid illusion is any kind of grid that deceives a person s vision. The two most common types of grid illusions are Hermann grid illusions and Scintillating grid illusions.Hermann grid illusionThe Hermann grid illusion is an optical illusion… …   Wikipedia

• Ordnance Survey National Grid — For the electricity network, see National Grid (Great Britain). Geodesy Fundamentals …   Wikipedia

• Fused Grid — The Fused Grid represents the synthesis of two traditional North American approaches to residential neighborhood planning: the traditional, nineteenth century grid plan, and the curvilinear pattern of looped streets and culs de sac of modern… …   Wikipedia

• C-squares — (acronym for the concise spatial query and representation system ) is a system of geocodes (actually a type of global grid) that provides a basis for simple spatial indexing of geographic features or data. It was devised by Tony Rees of CSIRO… …   Wikipedia

• World Meteorological Organization squares — or WMO squares is a system of geocodes that divides a chart of the world with latitude longitude gridlines (e.g. plate carrée projection, Mercator or other) into grid cells of 10° latitude by 10° longitude, each with a unique, 4 digit numeric… …   Wikipedia

• Digital Earth — Contents 1 Concept 1.1 Original Vision 1.2 An Emerging View 1.2 …   Wikipedia

• Finite-difference time-domain method — Finite difference time domain (FDTD) is a popular computational electrodynamics modeling technique. It is considered easy to understand and easy to implement in software. Since it is a time domain method, solutions can cover a wide frequency… …   Wikipedia

• Geographic information system — GIS redirects here. For other uses, see GIS (disambiguation). A geographic information system, geographical information science, or geospatial information studies is a system designed to capture, store, manipulate, analyze, manage, and present… …   Wikipedia