Grid (spatial index): Difference between revisions

Revision as of 10:18, 30 June 2016

Latest revision as of 20:59, 15 October 2023

(13 intermediate revisions by 8 users not shown)

Line 1:

{{Short description|Partition of a surface into contiguous cells}}

In the context of a [[spatial index]], a '''grid''' (a.k.a. "mesh", also "[[Discrete_Global_Grid|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 and grids based on diamond-shaped cells.

{{Refimprove|date=September 2018}}

In the context of a [[spatial index]], a '''grid''' (a.k.a.or "'''mesh",''' alsois "[[Discrete_Global_Grida regular{{fact|globalreason=What grid]]"about ifirregular itgrids?|date=October covers the entire surface of the [[globe]]) is a regular2023}} [[tessellation]] of a [[manifold]] or [[Surface (topology)|2-D surface]] that [[Space partitioning|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 tiling|square]]" or "rectangular" cells, [[Triangular tiling|triangular grids]] or meshes, [[Hexagonal tiling|hexagonal grids]], and grids based on diamond-shaped cells. A "[[discrete global grid|global grid]]" is a kind of grid that covers the entire surface of the [[globe]].

==Types of grids==

[[File:Geodesic Grid (ISEA3H) illustrated.png|right | 500px]]

"'''Square'''" or "'''rectangular'''" grids are frequently theused simplestfor inpurposes use,such i.e. foras 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 gridlinesgrid lines of latitude and longitude; for example, [[Marsden Square|Marsden squares]]s, [[World Meteorological Organization squares]], [[c-squares]] and others are aligned, while [[Universal Transverse Mercator coordinate system|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"''equal angle''" or "''[[equal-area map|equal area]]''". Grids 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 thoseGrids that are "''equal area''" ([[statistical grid]]s), 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 the "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 Discrete Global Grid Systems featuring '''hexagonal''' and other grids (including diamond-shaped), the paper of Sahr ''et al.'' (2003)<ref>Kevin Sahr, Denis White, and A. Jon Kimerling. 2003. Geodesic Discrete Global Grid Systems. Cartography and Geographic Information Science, 30(2), 121-134. {{doi|10.1559/152304003100011090}}</ref> is recommended reading.

TheA mostcommonly influentialused '''triangular''' grid is the "Quaternary Triangular Mesh" or (QTM), thatwhich 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.<ref>Geoffrey Dutton's [http://www.spatial-effects.com/SE-papers1.html Spatial&nbsp;Effects] website). This grid was also employed as the basis of the rotatable globe that forms part of the Microsoft [[Encarta]] product.

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<ref>[http://www.ncgia.ucsb.edu/globalgrids-book/comparison Criteria and Measures for the Comparison of Global Geocoding Systems, Keith C. Clarke, University of California]</ref> in which equal area cells are deemed of prime importance.

[http://www.spatial-effects.com/SE-papers1.html "Spatial Effects: Research Papers and Data"] {{Webarchive|url=https://web.archive.org/web/20070219054353/http://www.spatial-effects.com/SE-papers1.html |date=2007-02-19 }}.</ref>

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 (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<ref>[http://www.ncgia.ucsb.edu/globalgrids-book/comparison Criteria and Measures for the Comparison of Global Geocoding Systems, Keith C. Clarke, University of California] {{webarchive|url=https://web.archive.org/web/20100623002915/http://www.ncgia.ucsb.edu/globalgrids-book/comparison/ |date=2010-06-23 }}</ref> 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.

'''[[Quadtree]]s 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]]. In polar grids, intervalsusing circles of a prescribed radius (circles) that are divided into sectors of a certain angle. Coordinates are given as the radius and angle from the center of the grid (pole).

==Grid-based spatial indexing==

Line 23 ⟶ 24:

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 thatthis is called Grid"grid Traversaltraversal".

==See also==

*[[Discrete global grid]]

*[[Euclidean tilings by convex regular polygons]]

*[[Geodesic grid]]

*[[Spatial index]]

* [[Grid plan]]

*[[Grid reference]]

*[[Geocode]]

* [[hex map]]

*[[quadrilateralized spherical cube]]

*[[Quadtree]]

*[[R-tree]]

Line 41 ⟶ 47:

== External links ==

*[https://web.archive.org/web/20090724075851/http://www.gamerendering.com/2009/07/20/grid-traversal/ Grid Traversal implementation details and applet demonstration]

*[http://www.pyxisinnovation.com/pyxwiki/index.php?title=How_PYXIS_Works PYXIS Discrete Global Grid System using the ISEA3H Grid]