A Robust Strategy for Handling Linear Features in
Topologically Consistent Polyline Simplification
da Silva, Adler C. G.
Wu, Shin-Ting
{acardoso,ting}@dca.fee.unicamp.br
Department of Computer Engineering and Industrial Automation (DCA)
School of Electrical and Computer Engineering (FEEC)
State University of Campinas (UNICAMP)
November 20
GEOINFO 2006
1/25
Topics









Motivation
Polyline Simplification
Consistent Simplification
Problem
Objective
Solution
Results
Concluding Remarks
Future Work
November 20
GEOINFO 2006
2/25
Motivation

Create a topologically consistent
simplification algorithm that
•
•
•
•
Handles all map features together
Generates better visual results
Achieves efficient processing
Produces scale independent maps
November 20
GEOINFO 2006
3/25
Polyline Simplification
Original Map
Simplified Map
50,000 points
2,000 points
Source: Digital Chart of the World Server (www.maproom.psu.edu/dcw)
November 20
GEOINFO 2006
4/25
Polyline Simplification

Common problem in most algorithms
• Loss of “Topological Consistency”

Cause: they take the polyline in isolation,
without considering the features in its vicinity
November 20
GEOINFO 2006
5/25
Example: RDP Algorithm


Maximum tolerable distance ()
It adds the farthest vertex from line segment

November 20
GEOINFO 2006
6/25
Example: RDP Algorithm

Problem with big tolerance

November 20
GEOINFO 2006
7/25
Consistent Simplification

A topologically consistent polyline
simplification algorithm must
• Keep features in the correct side
• Avoid intersections between features
• Avoid self-intersections

The algorithm may
• Simplify one polyline considering the features
in its vicinity (simplification in context)
• Simplify the complete collection of polylines
together (global simplification)
November 20
GEOINFO 2006
8/25
State of the Art

de Berg et al., 1998
• Simplification is viewed as an optimization problem
• A single polyline is simplified in context
• It handles only polylines that are part of a polygon

Saalfeld, 1999
•
•
•
•

It is a improvement of RDP for recovering topology
A single polyline is simplified in context
It also handles polylines that are not part of a polygon
Inconsistency is removed by inserting more vertices
van der Poorten and Jones, 1999 / 2001
•
•
•
•
The polylines of the map are simplified together
Based on Constrained Delaunay Triangulation
Topology is implicitly preserved
Relatively slow (10min for 30,000 vertices)
November 20
GEOINFO 2006
9/25
Problem

de Berg et al. and Saalfeld handle a
linear feature as a point feature
• When handling a line segment, they consider
that intersections can be avoided if the side
of its vertices is preserved
Problem with polygons
November 20
GEOINFO 2006
Problem with polylines
10/25
de Berg et al.’s Strategy

A polyline is part of a polygon
• They formalize consistency of a
point with respect to a polygon

de Berg et al.’s algorithm adds
other restrictions that avoid
the problematic cases
November 20
GEOINFO 2006
11/25
Saalfeld’s Strategy

He generalizes the consistency of
polygons to polylines
• Compute sidedness: count the
number of crossings of a ray from
the point with P and P’
• Odd = wrong side
• Even = correct side

Triangle Inversion Property
• The insertion of a vertex changes
only the sidedness of the points
inside the triangle
• Used to update sidedness of points
November 20
GEOINFO 2006
12/25
Saalfeld’s Algorithm
1st step: RDP algorithm until  condition is satisfied
2nd Step: further insertions until sidedness and 
conditions are satisfied
November 20
GEOINFO 2006
13/25
Objective

General context
• Develop a topologically consistent simplification algorithm using Saalfeld’s strategy
• Remove locally inconsistencies

Contribution of this work
• Theoretical solution
• Study on consistency to avoid (self-) intersections by
taking into consideration only vertices of polylines
• Practical solution
• Replace the triangle inversion test by a robust test
November 20
GEOINFO 2006
14/25
Theoretical Analysis

An inconsistency occurs whenever a
subpolyline intersects the simplifying
segment of another subpolyline
• Example: Pkj intersects vivk, which is the
simplifying segment of Pik
Region with
problem
November 20
GEOINFO 2006
15/25
Theoretical Solution

Consider each subpolyline and its
simplifying segment separately
• Example: Sidedness of p1 is evaluated with
respect to (Pik, vivk) and (Pkj, vkvj).
November 20
GEOINFO 2006
16/25
Practical Solution

Pre-processed array of crossings with Pij
• Number of crossings is very small



begin points to the first element
end points to the element after the last one
Number of crossings =
(begin-end)+(crossing with segment vivj)
November 20
GEOINFO 2006
17/25
Practical Solution

When inserting a vertex
• Just update pointers begin and end (O(log n))
• Store a reference to original array
November 20
GEOINFO 2006
18/25
Results: Synthetic Data

Intersections
Original Data
Triangle Inversion
Array of Crossings
Polylines
Polygons
November 20
GEOINFO 2006
19/25
Results: Synthetic Data

Self-intersections
Original Data
Triangle Inversion
Array of Crossings
Polylines
Polygons
November 20
GEOINFO 2006
20/25
Results: Processing Time
Source: Digital Chart of the World Server (www.maproom.psu.edu/dcw)
November 20
GEOINFO 2006
21/25
Results: Processing Time


Equivalent processing time
Insert a few more vertices for correcting inconsistencies
November 20
GEOINFO 2006
22/25
Concluding Remarks

Mistake in consistent simplification algorithms
• Handle linear features as point features

Theoretical solution
• Handle separately each subpolyline and its
simplifying line segment

Practical solution (for Saalfeld’s algorithm)
•
•
•
•
Pre-processed array of crossings
Complete elimination of inconsistencies
Equivalent processing time
A few more vertices are inserted to recover topology
November 20
GEOINFO 2006
23/25
Future Work

The consistent simplification algorithm
• Handles polylines in a global simplification
• Considers only vertices that are currently in simplified
polylines
• Inserts less vertices  better visual results
• Achieves faster processing
• Can be used with many isolated algorithms
• Produce scale independent maps

November 20
GEOINFO 2006
24/25
The End
Thank You!
November 20
GEOINFO 2006
25/25