Academic journal article Cartography & Geographic Information Systems

Topologically Correct Subdivision Simplification Using the Bandwidth Criterion

Academic journal article Cartography & Geographic Information Systems

Topologically Correct Subdivision Simplification Using the Bandwidth Criterion

Article excerpt

ABSTRACT: The line simplification problem is an old and well studied problem in cartography. Although there are several algorithms to compute a simplification there seem to be no algorithms that perform line simplification in the context of other geographical objects. This paper presents a nearly quadratic time algorithm for the following line simplification problem: Given a polygonal line, a set of extra points, and a real [Epsilon] [is greater than] 0, compute a simplification that guarantees (i) a maximum error [Epsilon]; (ii) that the extra points remain on the same side of the simplified chain as of the original chain; and (iii) that the simplified chain has no self-intersections. The algorithm is applied as the main subroutine for subdivision simplification and guarantees that the resulting subdivision is topologically correct.

KEYWORDS: Line simplification, subdivision simplification, geometric algorithms, computer cartography, bandwidth criterion.


The line simplification problem is a thoroughly studied problem in various disciplines, including digital image analysis (Asano and Katoh 1993; Dunham 1986; Hobby 1993; Kurozumi and Davis 1982), computational geometry (Chan and Chin 1992; Eu and Toussaint 1994; Guibas et al. 1993; Imai and Iri 1988; Melkman and O'Rourke 1988), and especially geographic information systems (Buttenfield 1985; Campell and Cromley 1991; Cromley 1988, 1990; Douglas and Peucker 1973; Li and Openshaw 1992; McMaster 1987; many more references can be found in Muller et al. 1995 and Weibel 1997b). Often the input is a polygonal chain and a maximum allowed error [Epsilon], and methods are described to obtain another polygonal chain with fewer vertices that lies at a distance of most [Epsilon] from the original polygonal chain.

Some methods yield chains of which all vertices are also vertices of the input chain, other methods yield chains where other points can be vertices as well. Another source of variation on the basic problem is the error measure that is used.

Well known criteria are the bandwidth or parallel strip error criterion, Hausdorff distance, Frechet distance, areal displacement, and vector displacement. Besides geometric error criteria, in geographic information systems one can also use criteria based on the geographic knowledge, or on perception (Mark 1989; Plazanet 1995; Weibel 1997a).

The motivation for studying line simplification problems is twofold. Firstly, polygonal lines at a high level of detail consume much storage space. In many situations, a high level of detail is unnecessary or even unwanted. Secondly, when objects are described at a high level of detail, operations performed on them tend to be slow. This problem can be severe in animation, for example.

We have been motivated to study the line simplification problem by the need to reduce the storage space needed to represent a map in a geographic information system. In this paper, we assume the map is modeled as a subdivision of the plane or a rectangular region. Our main consideration is the reduction of the complexity of the subdivision. The processing time may be higher than needed in interactive situations. The description size of the subdivision is a permanent cost in a geographic information system, whereas the processing time is spent only once in many applications.

One of the most important requirements of subdivisions for maps is that they be simple. No two edges of the subdivision may intersect, except at the endpoints. This poses two extra conditions on the line simplification method. Firstly, when a polygonal chain is reduced in complexity, the output polygonal chain must be a simple polygonal chain. Several of the line simplification methods described before do not satisfy this constraint (Chan and Chin 1992; Cromley 1988; Douglas and Peucker 1973; Eu and Toussaint 1994; Imai and Iri 1988; Li and Openshaw 1992; Melkman and O'Rourke 1988). …

Search by... Author
Show... All Results Primary Sources Peer-reviewed


An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.