Ebook: Mapping and Spatial Modelling for Navigation

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.

---

This volume presents the proceedings of a NATO Advanced Research Workshop (ARW) held in Denmark in August 1989. It results from the activities of the NATO Special Programme on Sensory Systems for Robotic Control, running since 1983 under the auspices of the NATO Science Committee. The volume collects up-to-date interdisciplinary research findings of high practical value, about spatial- data structures, mapping systems, cartographic feature extraction from imagery, mobile robot navigation, and operational and research needs in mapping. As the demand for mapping products and services is growing very rapidly, but the transition to digital map production is still slow, the emphasis in this volume is on specific techniques for map production and their use in various navigation tasks. The key disciplines offering new contributions here are image processing, computational geometry, artificial intelligence, hypermedia, geography, sensor fusion, route planning, and computational environments.

---

This volume presents the proceedings of a NATO Advanced Research Workshop (ARW) held in Denmark in August 1989. It results from the activities of the NATO Special Programme on Sensory Systems for Robotic Control, running since 1983 under the auspices of the NATO Science Committee. The volume collects up-to-date interdisciplinary research findings of high practical value, about spatial- data structures, mapping systems, cartographic feature extraction from imagery, mobile robot navigation, and operational and research needs in mapping. As the demand for mapping products and services is growing very rapidly, but the transition to digital map production is still slow, the emphasis in this volume is on specific techniques for map production and their use in various navigation tasks. The key disciplines offering new contributions here are image processing, computational geometry, artificial intelligence, hypermedia, geography, sensor fusion, route planning, and computational environments.
Content:
Front Matter....Pages I-VIII
Mapping and Spatial Modelling for Navigation: A Survey....Pages 1-9
Spatial Data Structures — The Extension from One to Two Dimensions....Pages 11-39
Hierarchical Data Structures for Spatial Reasoning....Pages 41-58
A Spherical Model for Navigation and Spatial Reasoning....Pages 59-72
Tools for Geometric Data Acquisition and Maintenance....Pages 73-93
MARIS: Map Recognition Input System....Pages 95-116
Pattern Classification from Raster Data Using Vector Lenses, Neural Networks and Expert Systems....Pages 117-147
Toward Automatic Cartographic Feature Extraction....Pages 149-180
ICARE an Expert System for Automatic Mapping from Satellite Imagery....Pages 181-192
Understanding Images by Reasoning in Levels....Pages 193-202
Generation and Processing of Geomorphic Models....Pages 203-226
Local perception and navigation for mobile robots....Pages 227-243
Geometric Models for Navigation....Pages 245-258
Distributed Control for Collision Avoidance between Autonomous Vehicles....Pages 259-267
Improved navigation, spatial mapping, and obstacle avoidance capabilities for mobile robots and AGV’s....Pages 269-286
Approaches to Route Planning and Guidance in the United Kingdom....Pages 287-310
The Cause and Effect of the Demand for Digital Geographic Products....Pages 311-332
Spatial Modeling in a National Charting Agency....Pages 333-355
Research Interests at the Defense Mapping Agency....Pages 357-357
Back Matter....Pages 359-361

---

This volume presents the proceedings of a NATO Advanced Research Workshop (ARW) held in Denmark in August 1989. It results from the activities of the NATO Special Programme on Sensory Systems for Robotic Control, running since 1983 under the auspices of the NATO Science Committee. The volume collects up-to-date interdisciplinary research findings of high practical value, about spatial- data structures, mapping systems, cartographic feature extraction from imagery, mobile robot navigation, and operational and research needs in mapping. As the demand for mapping products and services is growing very rapidly, but the transition to digital map production is still slow, the emphasis in this volume is on specific techniques for map production and their use in various navigation tasks. The key disciplines offering new contributions here are image processing, computational geometry, artificial intelligence, hypermedia, geography, sensor fusion, route planning, and computational environments.
Content:
Front Matter....Pages I-VIII
Mapping and Spatial Modelling for Navigation: A Survey....Pages 1-9
Spatial Data Structures — The Extension from One to Two Dimensions....Pages 11-39
Hierarchical Data Structures for Spatial Reasoning....Pages 41-58
A Spherical Model for Navigation and Spatial Reasoning....Pages 59-72
Tools for Geometric Data Acquisition and Maintenance....Pages 73-93
MARIS: Map Recognition Input System....Pages 95-116
Pattern Classification from Raster Data Using Vector Lenses, Neural Networks and Expert Systems....Pages 117-147
Toward Automatic Cartographic Feature Extraction....Pages 149-180
ICARE an Expert System for Automatic Mapping from Satellite Imagery....Pages 181-192
Understanding Images by Reasoning in Levels....Pages 193-202
Generation and Processing of Geomorphic Models....Pages 203-226
Local perception and navigation for mobile robots....Pages 227-243
Geometric Models for Navigation....Pages 245-258
Distributed Control for Collision Avoidance between Autonomous Vehicles....Pages 259-267
Improved navigation, spatial mapping, and obstacle avoidance capabilities for mobile robots and AGV’s....Pages 269-286
Approaches to Route Planning and Guidance in the United Kingdom....Pages 287-310
The Cause and Effect of the Demand for Digital Geographic Products....Pages 311-332
Spatial Modeling in a National Charting Agency....Pages 333-355
Research Interests at the Defense Mapping Agency....Pages 357-357
Back Matter....Pages 359-361
....