Go to Paper
Return to GeoComputation 99 Index

The Use of Spatial Context Awareness in Feature Simplification

McKEOWN, David (dmm@maps.cs.cmu.edu), McMAHILL, Jeff, Carnegie Mellon University, Digital Mapping Laboratory, Pittsburgh, PA 15213; CALDWELL, Douglas (caldwell@tec.army.mil) U.S. Army Topographic Engineering Center, 7701 Telegraph Road, Alexandria, VA 22315

Key Words: simplification, generalization, topology

The automated generalization of spatial data has been an active topic of research in the geographic information system (GIS) community since the early 1970s, when Douglas and Peucker published their initial results on algorithms to simplify lines. Today, generalization is seen as a tool for decluttering cartographic presentations at smaller scales, reducing the information content of data representations regardless of scale, and compressing volumes of spatial data. The bulk of generalization research has focused on the problem of line simplification, primarily because it is more easily understandable and tractable than other generalization transformations. More complicated generalization transformations, such as aggregation, amalgamation, exaggeration, enhancement, and displacement, have received less attention, primarily because of the difficulties in defining and implementing computational solutions. While slow progress is being made with the more complicated generalization transformations, additional work is still needed in the area of simplification.

The focus in linear feature simplification has been on the development of algorithms to manipulate the coordinate information in a single feature. This focus does not fully address the simplification issue and has resulted in anomalies where the topological structure of an individual feature is altered and/or the topological relationships among features are changed. The presence of altered topological structure necessitates the development of additional algorithms to identify the errors and use of editing tools to correct the problems.

This paper addresses the issue of using spatial context in line simplification. It is the result of a research effort designed to produce high quality 3-D simulation databases, not a research effort on generalization. The simulation databases required low information density to support real-time, distributed rendering of the data. They were constructed from highly detailed source data, which contained linear features that needed to be carefully selected and simplified. The use of standard GIS tools for simplification created data with topological errors and unrealistic representations of features with regard to the underlying terrain. The errors resulted in longer simulation database production timelines and required operator intervention to locate and correct the problems. The solution to the data editing problem was the development of smarter algorithms that considered spatial context when performing simplification. Carnegie Mellon University approached the problem in two ways, with the development of topologically-aware and terrain-aware simplification algorithms. The topologically-aware simplification algorithm preserves the relationships of the source data in the generalized data. It supports a per-edge tolerance specification, prevents the insertion of new intersections, and performs proximity checks to keep features' user-specified distances apart in the generalized output. The terrain-aware simplification algorithms preserve relationships with features and the underlying terrain. They handle situations where a 2-D approach to generalization would produce undesirable results. For example, when a road runs around a spur, a 2-D approach to simplification could produce a road that runs through the spur. This creates significant problems in a 3-D simulation database where deep and unnatural cuts are created when the roads are automatically integrated with the terrain.

The Carnegie Mellon University research has not only reduced the time required for the production of simulation databases, it has contributed significantly to the advancement of generalization research by incorporating spatial context in the simplification process.