Издательство Springer, 1997, -297 pp.
This volume aims to bring together the two lines of research whose interaction promises to have significant practical impact in the near future: the application-oriented discipline of Geographic Information Systems (GIS) and the technical discipline of geometric computation, or in particular, geometric algorithms and spatial data structures. GIS are complex systems consisting of a database part and a spatial data handling part. Spatial data handling in current GIS is less well-developed than the database aspects, and it is in relation to the spatial aspects that geometric algorithms and modeling can stimulate progress in GIS. GIS include many geometry-related problems such as spatial data storage and retrieval, visualization of spatial data, overlay of maps, spatial interpolation, and generalization.
Geometric Algorithms and GIS
Algorithms research has been an integral part of computer science since its beginnings. The goal is to design well-defined procedures that solve well-defined problems, and analyze their efficiency. Numerical algorithms were studied most thoroughly in the first phase of automated computation, and data management algorithms for sorting and searching became prominent in the 1960s. In the second half of the 1970s the systematic study of geometric algorithms gave birth to the discipline known today as computational geometry. The motivation for studying geometric algorithms comes from areas like robotics, computer graphics, automated manufacturing, VLSI design, and GIS.
The collaboration of GIS research and computational geometry has intensified in recent years, for several reasons. Firstly, the availability of geographic data in digital form is increasing rapidly. The acquisition of geographic data and the digitizing of maps are laborious, time-consuming tasks, and without appropriate digital data, GIS cannot operate effectively. Secondly, improved hardware now makes it possible to store and process large amounts of geographic data and to produce high-quality maps on computers. Thirdly, the research community in computational geometry, after having laid the conceptual and technical foundation, has recently shifted its attention toward more practical and more applied solutions.
Collaboration of GIS and Computational Geometry
The time is right for further development of the spatial components of GIS, as a result of joint efforts from computational geometry and GIS. What should such a collaboration look like? Many standard geometric problems and solutions, even those without any explicit reference to geography, are useful to GIS. Storing polygonal subdivisions on primary or background storage for efficient windowing queries is one example. Implementation and testing of data structures and query algorithms reveals their usefulness to GIS. Most of the basic algorithms developed in computational geometry, however, are not directly applicable to GIS. This is because standard geometric problems are often simplified to such an extent that they neglect important requirements of GIS. In addition, many problems arising in GIS have not yet been formalized in sufficient detail for the design of efficient algorithms.
As an example, consider generalization of maps. When the scale of a map is reduced, less information can be shown on the map, so it is necessary to remove or simplify certain objects on the map. However, it is far from clear which objects to remove or simplify. Different cartographers would produce different maps, if they were to generalize a map manually. A first step towards an automated map generalization method is the modeling of what should be generalized, when this is necessary, and how. These modeling questions cannot be answered by someone without cartographic knowledge. On the other hand, computational geometers are trained to abstract a problem into a form that is well defined. The joint knowledge of a cartographer and a geometer can result in a good model, a specification, for automated map generalization. Given such a specification, algorithms can be designed and implemented to compute the desired output.
There are several standard geometric structures and algorithms useful in GIS, with or without some modifications. These include topological data structures like the doubly-connected edge list or quad edge structure, spatial data structures like the quadtree and R-tree, the Voronoi diagram, the Delaunay triangulation., map overlay and buffer computation, and visualization algorithms. Most of these structures and algorithms are also used in other fields like computer graphics and robotics. They are well documented in textbooks or other standard texts.
Introduction to Geometric Computing: From Algorithms to Software
Voronoi Methods in GIS
Digital Elevation Models and TIN Algorithms
Visualization of TINs
Generalization of Spatial Data: Principles and Selected Algorithms
Spatial Data Structures : Concepts and Design Choices
Space Filling Curves versus Random Walks
Exteal-Memory Algorithms with Applications in GIS
Precision and Robustness in Geometric Computations
This volume aims to bring together the two lines of research whose interaction promises to have significant practical impact in the near future: the application-oriented discipline of Geographic Information Systems (GIS) and the technical discipline of geometric computation, or in particular, geometric algorithms and spatial data structures. GIS are complex systems consisting of a database part and a spatial data handling part. Spatial data handling in current GIS is less well-developed than the database aspects, and it is in relation to the spatial aspects that geometric algorithms and modeling can stimulate progress in GIS. GIS include many geometry-related problems such as spatial data storage and retrieval, visualization of spatial data, overlay of maps, spatial interpolation, and generalization.
Geometric Algorithms and GIS
Algorithms research has been an integral part of computer science since its beginnings. The goal is to design well-defined procedures that solve well-defined problems, and analyze their efficiency. Numerical algorithms were studied most thoroughly in the first phase of automated computation, and data management algorithms for sorting and searching became prominent in the 1960s. In the second half of the 1970s the systematic study of geometric algorithms gave birth to the discipline known today as computational geometry. The motivation for studying geometric algorithms comes from areas like robotics, computer graphics, automated manufacturing, VLSI design, and GIS.
The collaboration of GIS research and computational geometry has intensified in recent years, for several reasons. Firstly, the availability of geographic data in digital form is increasing rapidly. The acquisition of geographic data and the digitizing of maps are laborious, time-consuming tasks, and without appropriate digital data, GIS cannot operate effectively. Secondly, improved hardware now makes it possible to store and process large amounts of geographic data and to produce high-quality maps on computers. Thirdly, the research community in computational geometry, after having laid the conceptual and technical foundation, has recently shifted its attention toward more practical and more applied solutions.
Collaboration of GIS and Computational Geometry
The time is right for further development of the spatial components of GIS, as a result of joint efforts from computational geometry and GIS. What should such a collaboration look like? Many standard geometric problems and solutions, even those without any explicit reference to geography, are useful to GIS. Storing polygonal subdivisions on primary or background storage for efficient windowing queries is one example. Implementation and testing of data structures and query algorithms reveals their usefulness to GIS. Most of the basic algorithms developed in computational geometry, however, are not directly applicable to GIS. This is because standard geometric problems are often simplified to such an extent that they neglect important requirements of GIS. In addition, many problems arising in GIS have not yet been formalized in sufficient detail for the design of efficient algorithms.
As an example, consider generalization of maps. When the scale of a map is reduced, less information can be shown on the map, so it is necessary to remove or simplify certain objects on the map. However, it is far from clear which objects to remove or simplify. Different cartographers would produce different maps, if they were to generalize a map manually. A first step towards an automated map generalization method is the modeling of what should be generalized, when this is necessary, and how. These modeling questions cannot be answered by someone without cartographic knowledge. On the other hand, computational geometers are trained to abstract a problem into a form that is well defined. The joint knowledge of a cartographer and a geometer can result in a good model, a specification, for automated map generalization. Given such a specification, algorithms can be designed and implemented to compute the desired output.
There are several standard geometric structures and algorithms useful in GIS, with or without some modifications. These include topological data structures like the doubly-connected edge list or quad edge structure, spatial data structures like the quadtree and R-tree, the Voronoi diagram, the Delaunay triangulation., map overlay and buffer computation, and visualization algorithms. Most of these structures and algorithms are also used in other fields like computer graphics and robotics. They are well documented in textbooks or other standard texts.
Introduction to Geometric Computing: From Algorithms to Software
Voronoi Methods in GIS
Digital Elevation Models and TIN Algorithms
Visualization of TINs
Generalization of Spatial Data: Principles and Selected Algorithms
Spatial Data Structures : Concepts and Design Choices
Space Filling Curves versus Random Walks
Exteal-Memory Algorithms with Applications in GIS
Precision and Robustness in Geometric Computations