In the context of a spatial index, a grid or mesh 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 and grids based on diamond-shaped cells.also "global grid" if it covers the entire surface of the globe)
Types of grids
Square or rectangular grids are frequently used for purposes such as translating spatial information expressed in Cartesian coordinates into and out of the grid system. Such grids may or may not be aligned with the grid lines of latitude and longitude; for example, Marsden Squares, World Meteorological Organization squares, c-squares and others are aligned, while Universal Transverse Mercator coordinate system and various national 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, or those that are "equal area", that have cell sizes that are constant in distance on the ground but not in degrees of longitude, in particular. A commonly used triangular grid is the "Quaternary Triangular Mesh", which 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. This grid was also employed as the basis of the rotatable globe that forms part of the Microsoft Encarta product. Hexagonal grids may also be used. In general, triangular and hexagonal grids are constructed so as to better approach the goals of equal-area 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. Quadtrees are a specialised form of grid in which the resolution of the grid is varied according to the nature and complexity of the data to be fitted, across the 2-d space. Polar grids utilize the polar coordinate system, using circles of a prescribed radius that are divided into sectors of a certain angle. Coordinates are given as the radius and angle from the center of the grid.
Grid-based spatial indexing
In practice, construction of grid-based spatial indices 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. ). 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 indices 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 indices is not limited to digital data; the "index" section of any global or street atlas commonly contains a list of named features with associated grid square identifiers, and may be considered a perfectly acceptable example of a spatial index.
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, 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 ; this is called "grid traversal".
