Line Generalisation Aglorithms - Simplification Overview

Line Simplification Algorithms

Line simplification algorithms have been developed over the years for the purpose of 'weeding out' redundant or unnecessary coordinate information from line features, whilst retaining the perceptual characteristics of the line. They generally work via the application of some geometric criterion to a line's coordinate pairs (such as distance between points or displacement from a centre-line). Figure 1 below shows a line before and after it has been simplified, with arrows representing the points eliminated during the process.

Figure 1. Line Simplification (Source: McMaster & Shea 1992)

There are a series of justifications for the simplification of digitised lines. These are summarised below:
1.	Reduced plotting time: simplification reduces the number of (x,y) coordinate pairs, increasing the plotting speed (a faster pen speed also improves the aesthetic qualities of the line).
2.	Reduced storage space: simplification can reduce a large data set by up to 70%, decreasing both the amount of storage space required for the data and the cost of storing it.
3.	Faster vector to raster conversion: a simplified coordinate set will enable faster conversion from vector to raster mode.
4.	Faster vector processing: the time needed for processing vectors, including translation, rotation, re-scaling, cartometric analysis and some symbol-generation is greatly reduced with a simplified data set.

Local Processing Routines

As a basic introduction to line simplification algorithms, Figure 2 illustrates two local processing routines. The perpendicular distance algorithm is displayed on the left (A) and works by sequential operations on a triad of coordinate pairs. Firstly, a perpendicular is constructed to the line connecting the first and third points (p1 and p3) of the triad, from the intermediate point (p2). If this distance is larger than the user-defined tolerance, the intermediate point is retained, however if it is shorter than the tolerance, the point is eliminated. The next three points (p2, p3 and p4) then form the new triad and the process is repeated. This is done until the end of the line is reached.

Figure 2. Local Processing Simplifiers (Source: McMaster & Shea 1992)

The angular tolerance algorithm is displayed on the right of the figure (B) and works via a similar process to that described above, only with an angular tolerance as measured between vectors connecting points p1 and p3, and p1 and p2.

The two algorithms presented in Figure 2 and described above form the basis of most other line simplification algorithms. The algorithm at the focus of the line simplification section of this module is known as the Lang Simplification Algorithm - an extended version of the perpendicular distance algorithm in Figure 2A. The Lang Simplification Algorithm is credited, among other things, with being able to maintain the original geometric characteristics of a line. There are links below (on the right) to two interactive lessons which will help you to visualise how Lang's algorithm is applied when simplifying a line. If you wish to read/revise any theory at this stage, follow the links on the left.

Background Theory Links:

Lang Simplification Algorithm
Interactive Lessons:

Digital Generalisation
Line Smoothing

Visualisation Exercise
Simple Interactive Example

Click here to download all theory presented in this module