Visvalingam's Line Simplification Algorithm

26 Oct 2014

Line simplification is a common problem in cartography because it determines how detailed a map looks. Digital maps have only finite resolution: high resolution map gives more details, but the data is bigger and takes more time for the renderer to process; low resolution makes map processing faster, but details are no longer preserved and the map might look ugly.

There are two polular algorithms for line simplification: Douglas–Peucker and Visvalingam’s alogithm. Today, I am going to talk about Visvalingam’s area-based algorithm (short for VSA algorithm).

VSA algorithm is very easy to understand: it repeatedly removes points (non-terminal) with the least effective area.

Pseudo-algorithm:

REPEAT
- Compute the effective area of each point along a line.
- Delete the point with the smallest effective area.
- After removal, recompute the effective area of of neighboring 
  points of the deleted one.

UNTIL
- The original line consists of only 2 points, or, all the 
  remaining points have effective area larger than a predefined 
  threshhold.

The algorithm is effective at producing minimal simplified and yet characteristic shapes. But it also has its limitations: as with point-based algorithm, it can also produdces crossing lines from complex shapes; and it is only area-based and not context-awared (manual generalisation considers size, shape, and geometric and geographic context of features).

Reference

Note

Effective Area



Effective area is defined by an areal displacement which would occur is that point alone was omitted from the current line. In other words, it is area of triangles formed by successive triplets of points a long a line.