The successful implementation of applications in spatial reasoning requires paying attention to the representation of spatial data. In particular, an integrated and uniform treatment of different spatial features is necessary in order to enable the reasoning to proceed quickly. Currently, the most prevalent features are points, rectangles, lines, regions, surfaces, and volumes. As an example of a reasoning task consider a query of the form "find all cities with population in excess of 5,000 in wheat growing regions within 10 miles of the Mississippi River. " Note that this query is quite complex. It requires- processing a line map (for the river), creating a corridor or buffer (to find the area within 10 miles of the river), a region map (for the wheat), and a point map (for the cities). Spatial reasoning is eased by spatially sorting the data (i. e. , a spatial index). In this paper we show how hierarchical data structures can be used to facilitate this process. They are based on the principle of recursive decomposition (similar to divide and conquer methods). In essence, they are used primarily as devices to sort data of more than one dimension and different spatial types. The term quadtree is often used to describe this class of data structures. In this paper, we focus on recent developments in the use of quadtree methods. We concentrate primarily on region data. For a more extensive treatment of this subject, see [SameS4a, SameSSa, SameSSb, SameSSc, SameSga, SameSgbj.

Inhalt

1. Mapping and spatial modelling for navigation: a survey.- Spatial Data Structures.- 2. Spatial data structures: the extension from one to two dimensions.- 3. Hierarchical data structures for spatial reasoning.- 4. A spherical model for navigation and spatial reasoning.- Mapping Systems.- 5. Tools for geometric data acquisition and maintenance.- 6. MARIS: Map recognition input system.- 7. Pattern classification from raster data using vector lenses, neural networks and expert systems.- Cartographic Feature Extraction from Imagery.- 8. Toward automatic cartographic feature extraction.- 9. ICARE: an expert system for automatic mapping from satellite imagery.- 10. Understanding images by reasoning in levels.- 11. Generation and processing of geomorphic models.- Mobile Robot Navigation from Maps.- 12. Local perception and navigation for mobile robots.- 13. Geometric models for navigation.- 14. Distributed control for collision avoidance between autonomous vehicles.- 15. Improved navigation, spatial mapping, and obstacle avoidance capabilities for mobile robots and AGV's.- 16. Approaches to route planning and guidance in the UK.- Operational and Research Needs.- 17. The cause and effect of the demand for digital geographic products.- 18. Spatial modeling in a national charting agency.- 19. Research interests at the Defence Mapping Agency.