GIS toolglossary


line smoothing algorithms

Cartographers produce manuscript lines which have a smooth 'flowing' appearance. In comparison, digital lines tend to be angular and non-aesthetically pleasing (particularly at large scales) - this is due mostly to the constraints of the digitising grid. Unlike simplification, which endeavours to reduce detail, smoothing techniques shift the position of points making up a line, in order to remove small perturbations and capture only the most significant trends of the line. Hence, smoothing is used to improve the appearance of digitised lines or, more simply, for cosmetic modification. Figure 1 shows a line before and after it has been smoothed.

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

Line Smoothing

As Figure 1 illustrates, the aesthetic appearance of a line can be greatly improved by applying one of the many smoothing operators. There are various ways that smoothing algorithms can be classified, see Table 1 below for one such classification.


Table 1. Characteristics of smoothing algorithms (Source: Lewis 1990 in McMaster & Shea 1992)

Category
Description
Point averaging routines a)

Calculates an average based on the positions of existing coordinate pairs and neighbours.

b) Only the end points remain the same.
c) Maintains the same number of points as the original line.
d) Each algorithm easily adapted for different smoothing conditions by choosing different tolerance parameters.
e) All algorithms are local or extended local processors.
Mathematical curve fitting routines a)

Develops a mathematical function or series of functions that describe the geometrical nature of the line.

b) The number of retained points is variable and user-controlled.
c) Retention of end points and of points on the original line is dependent on choice of algorithm and tolerances.
d) Once algorithm chosen, there is little flexibility allowed in changing the final shape of the smoothed line.
e) Function parameters can be stored and used to later regenerate the line at the required point density.
f) There are local, extended local and global processing routines.
Tolerancing routines a)

Each algorithm uses some geometrical relationship between the points and a user defined tolerance to smooth the cartographic line.
  b) End points are retained, but the number of points generated for the smoothed line and the number of interior points retained from the original data is algorithm-dependent.
  c) Ability to change the curve's final appearance is algorithm-dependent.
  d) There are local, extended local and global processing routines.
There are several line smoothing algorithms, including McMaster's Distance Weighting Algorithm, Boyle's Forward-Looking Smoothing Algorithm and Chaiken's Smoothing Algorithm. The algorithm at the focus of the line smoothing section of the module, though, is known as McMaster's Slide Averaging Algorithm.There is a link below (on the right) to one interactive lesson which will help you to visualise how McMaster's Slide Averaging Algorithm is applied when smoothing a line. If you wish to read/revise any theory at this stage, follow the links on the left.
Background Theory Links:
McMaster's Slide Averaging Algorithm Interactive Lesson:
Digital Generalisation
Line Simplification
Visualisation Exercise

Click here to download all theory presented in this module
references