4 Progressive Techniques
71
4.4 Approaches Based on Geometric Operators
Much of the work on map generalization and multiple map representations for progressive transmission rely on the application of line simplification algorithms. This
is due to the availability of successful algorithms and to the fact that the majority of
features in a map are represented by polylines. Line simplification is a generalization
operator that generates an approximated (simplified) representation of a polyline by
eliminating a subset of its vertices.
The classical Ramer–Douglas–Peucker (RDP) algorithm [18, 40] is the most
commonly used line simplification algorithm in both GIS research and commercial
applications. The basic idea of the algorithm is as follows: in order to simplify a
polyline with respect to a pre-defined tolerance value, it selects the vertex v with
maximum distance from the segment connecting the endpoints of the polyline and
compares such a distance with the tolerance value; if the distance is greater, then the
polyline is subdivided into two polylines incident at v and the process is recursively
applied to them; otherwise the polyline is approximated by the segment itself (see
Fig. 4.2 for an example). The algorithm is very simple and easy to implement. In
addition it provides good visual results as it preserves the overall shape of polylines.
Notwithstanding its popularity, such an algorithm presents a major drawback,
which prevents its completely automated application. Indeed, it treats each polyline
as an isolated feature and simplifies it individually. As a consequence, inconsistencies may be introduced into the simplified map, including unwanted intersections
with other polylines and topologically incorrect positioning of features
(e.g. an island jumps inland after simplification). A posteriori checks are required
to rectify these. Examples are shown in Fig. 4.3.
Several efforts have been made to improve such an algorithm to preserve topological consistency. In particular, Saalfeld [44] proposed a topologically consistent
line simplification method by adding further checks to the terminating condition
in the classical RDP algorithm. His improvement is based on the fact that, while
d
p i
p j
v
p i
p j
v
i
j
e
Fig. 4.2. A polyline l with five vertices (left) is reduced to a polyline with three vertices (right)
when the RDP algorithm with tolerance e is applied. First l is split at v into two subpolylines,
each of which is then replaced by the segment connecting its endpoints during the subsequent
application of the algorithm
71
4.4 Approaches Based on Geometric Operators
Much of the work on map generalization and multiple map representations for progressive transmission rely on the application of line simplification algorithms. This
is due to the availability of successful algorithms and to the fact that the majority of
features in a map are represented by polylines. Line simplification is a generalization
operator that generates an approximated (simplified) representation of a polyline by
eliminating a subset of its vertices.
The classical Ramer–Douglas–Peucker (RDP) algorithm [18, 40] is the most
commonly used line simplification algorithm in both GIS research and commercial
applications. The basic idea of the algorithm is as follows: in order to simplify a
polyline with respect to a pre-defined tolerance value, it selects the vertex v with
maximum distance from the segment connecting the endpoints of the polyline and
compares such a distance with the tolerance value; if the distance is greater, then the
polyline is subdivided into two polylines incident at v and the process is recursively
applied to them; otherwise the polyline is approximated by the segment itself (see
Fig. 4.2 for an example). The algorithm is very simple and easy to implement. In
addition it provides good visual results as it preserves the overall shape of polylines.
Notwithstanding its popularity, such an algorithm presents a major drawback,
which prevents its completely automated application. Indeed, it treats each polyline
as an isolated feature and simplifies it individually. As a consequence, inconsistencies may be introduced into the simplified map, including unwanted intersections
with other polylines and topologically incorrect positioning of features
(e.g. an island jumps inland after simplification). A posteriori checks are required
to rectify these. Examples are shown in Fig. 4.3.
Several efforts have been made to improve such an algorithm to preserve topological consistency. In particular, Saalfeld [44] proposed a topologically consistent
line simplification method by adding further checks to the terminating condition
in the classical RDP algorithm. His improvement is based on the fact that, while
d
p i
p j
v
p i
p j
v
i
j
e
Fig. 4.2. A polyline l with five vertices (left) is reduced to a polyline with three vertices (right)
when the RDP algorithm with tolerance e is applied. First l is split at v into two subpolylines,
each of which is then replaced by the segment connecting its endpoints during the subsequent
application of the algorithm