179:
266:
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 indices can easily be merged from a variety of sources. On the other hand, data driven structures such as
25:
273:
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 (towns, streets, etc.) with associated grid square identifiers, and may be considered a perfectly acceptable example of a spatial index (in this
282:
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.
246:
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
265:
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
238:
A commonly used triangular grid is the "Quaternary
Triangular Mesh" (QTM), 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
247:
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.
149:
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
253:
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
286:
In computer science, one often needs to find out all cells a ray is passing through in a grid (for raytracing or collision detection); this is called "grid traversal".
270:
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.
257:, 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.
206:
300:
227:" have cell sizes that are constant in degrees of latitude and longitude but are unequal in area (particularly with varying latitude). Grids that are "
198:
235:), 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.
462:
210:
42:
185:
Square or rectangular grids are frequently used for purposes such as translating spatial information expressed in
Cartesian coordinates (
467:
437:
402:
193:) 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,
108:
417:
Rigaux, P., Scholl, M., and
Voisard, A. 2002. Spatial Databases - with application to GIS. Morgan Kaufmann, San Francisco, 410pp.
335:
89:
61:
46:
383:
68:
75:
35:
400:
Criteria and
Measures for the Comparison of Global Geocoding Systems, Keith C. Clarke, University of California
57:
254:
442:
178:
295:
163:
350:
146:
142:
82:
457:
274:
case, typically organised by feature name, though the reverse is conceptually also possible).
155:
232:
159:
406:
387:
399:
320:
219:
194:
451:
310:
305:
151:
122:
355:
134:
424:
380:
24:
239:
employed as the basis of the rotatable globe that forms part of the
Microsoft
315:
202:
190:
340:
250:
186:
138:
361:
330:
325:
240:
345:
267:
167:
438:
Grid
Traversal implementation details and applet demonstration
18:
177:
166:" is a kind of grid that covers the entire surface of the
213:
are not. In general, these grids fall into two classes, "
443:
PYXIS Discrete Global Grid System using the ISEA3H Grid
49:. Unsourced material may be challenged and removed.
209:and various local grid based systems such as the
207:Universal Transverse Mercator coordinate system
162:, and grids based on diamond-shaped cells. A "
8:
301:Euclidean tilings by convex regular polygons
16:Partition of a surface into contiguous cells
381:"Spatial Effects: Research Papers and Data"
199:World Meteorological Organization squares
109:Learn how and when to remove this message
372:
211:British national grid reference system
356:Utility pole#Coordinates on pole tags
7:
47:adding citations to reliable sources
14:
358:(some based on rectangular grids)
336:quadrilateralized spherical cube
23:
34:needs additional citations for
205:and others are aligned, while
1:
463:Geographic coordinate systems
425:Indexing the Sky - Clive Page
427:- Grid indices for astronomy
261:Grid-based spatial indexing
484:
154:" or "rectangular" cells,
468:Database index techniques
58:"Grid" spatial index
255:polar coordinate system
182:
181:
296:Discrete global grid
121:In the context of a
43:improve this article
223:". Grids that are "
405:2010-06-23 at the
386:2007-02-19 at the
351:Alpha-numeric grid
183:
379:Geoffrey Dutton.
233:statistical grids
119:
118:
111:
93:
475:
418:
415:
409:
397:
391:
377:
156:triangular grids
114:
107:
103:
100:
94:
92:
51:
27:
19:
483:
482:
478:
477:
476:
474:
473:
472:
448:
447:
434:
421:
416:
412:
407:Wayback Machine
398:
394:
388:Wayback Machine
378:
374:
370:
292:
280:
263:
195:Marsden Squares
176:
160:hexagonal grids
115:
104:
98:
95:
52:
50:
40:
28:
17:
12:
11:
5:
481:
479:
471:
470:
465:
460:
450:
449:
446:
445:
440:
433:
432:External links
430:
429:
428:
420:
419:
410:
392:
371:
369:
366:
365:
364:
359:
353:
348:
343:
338:
333:
328:
323:
321:Grid reference
318:
313:
308:
303:
298:
291:
288:
279:
276:
262:
259:
175:
174:Types of grids
172:
117:
116:
99:September 2018
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
480:
469:
466:
464:
461:
459:
456:
455:
453:
444:
441:
439:
436:
435:
431:
426:
423:
422:
414:
411:
408:
404:
401:
396:
393:
389:
385:
382:
376:
373:
367:
363:
360:
357:
354:
352:
349:
347:
344:
342:
339:
337:
334:
332:
329:
327:
324:
322:
319:
317:
314:
312:
311:Spatial index
309:
307:
306:Geodesic grid
304:
302:
299:
297:
294:
293:
289:
287:
284:
277:
275:
271:
269:
260:
258:
256:
252:
248:
244:
242:
236:
234:
230:
226:
222:
221:
216:
212:
208:
204:
200:
196:
192:
188:
180:
173:
171:
169:
165:
161:
157:
153:
148:
144:
140:
136:
133:is a regular
132:
128:
124:
123:spatial index
113:
110:
102:
91:
88:
84:
81:
77:
74:
70:
67:
63:
60: –
59:
55:
54:Find sources:
48:
44:
38:
37:
32:This article
30:
26:
21:
20:
413:
395:
375:
285:
281:
272:
264:
249:
245:
237:
228:
224:
218:
214:
184:
135:tessellation
130:
126:
120:
105:
96:
86:
79:
72:
65:
53:
41:Please help
36:verification
33:
225:equal angle
215:equal angle
164:global grid
158:or meshes,
143:2-D surface
452:Categories
368:References
278:Other uses
229:equal area
220:equal area
147:divides it
69:newspapers
316:Grid plan
251:Quadtrees
243:product.
203:c-squares
191:longitude
458:Geocodes
403:Archived
384:Archived
341:Quadtree
290:See also
187:latitude
139:manifold
362:HEALPix
331:hex map
326:Geocode
268:R-trees
241:Encarta
83:scholar
346:R-tree
217:" or "
152:square
85:
78:
71:
64:
56:
168:globe
145:that
137:of a
90:JSTOR
76:books
189:and
131:mesh
127:grid
125:, a
62:news
231:" (
141:or
129:or
45:by
454::
201:,
197:,
170:.
390:.
150:"
112:)
106:(
101:)
97:(
87:·
80:·
73:·
66:·
39:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
