Using an energy minimization technique for polygon generalization.

Introduction

Motivation

A Polygonal subdivision (i.e., polygon map or polygon mosaic) shows the variation of a single variable by a finite number of discrete, nominal categories, that is, the mapped area is covered by mutually exclusive and space-exhaustive polygons (Goodchild et al. 1992; Jaakkola 1998). Examples of polygonal subdivisions are a geological map representing geological units distributed in space or a map showing different types of land use. This data type is very common in many geographic information systems (GIS) applications, particularly in thematic maps. Recent developments in cartography and geographic information science suggest that increased research with respect to the cartographic generalization of polygonal subdivisions (polygon generalization) is required. For instance, map production in national mapping agencies is moving from traditional to digital technology (Bengtson 2001; Ruas 2001), and thematic maps are produced and used in ever increasing numbers.

Polygon generalization involves transformations of a polygonal subdivision at the semantic and the geometric level (McMaster and Shea 1992; Galanda and Weibel 2002a). On the semantic level, categories are aggregated to higher-level categories. In the example of a land-use map the categories "deciduous forest" and "coniferous forest" may be combined to a category "forest." On the geometric level, polygon geometries are adapted to the perceptual limits imposed by the new, smaller scale, as well as to the symbology and limits stated in the map specifications. Thus, tot instance, a polygon is enlarged or eliminated if its area falls below the minimum area of the target scale. An empirical analysis of thematic maps (Peter and Weibel 1999) showed that key generalization requirements at the geometric level pertain to conflicts resulting from the violation of metric constraints which exist if a polygonal object is too small (violation of the minimum size constraint), too narrow (minimum width constraint), or too close to another polygon (minimum separability constraint). A violation of the minimum size constraint is denoted as a size conflict, while a violation of the latter constraints represents a proximity conflict.

Existing approaches usually apply specific algorithms to every type of size or proximity conflict in turn, such as a displacement algorithm based on the principle of magnetism (Bader and Weibel 1997), an algorithm for widening narrow parts of a polygon based on a Delaunay triangulation (De Lucia and Black 1987; Bader and Weibel 1997), or a boundary-moving algorithm to enlarge a polygon (Jones et al. 1995). The solution of the numerous size and proximity conflic...

If you are already a vLex customer, Access Here