Douglas-Peucker algorithm

The Douglas–Peucker algorithm, also known as Ramer–Douglas–Peucker algorithm or iterative end-point fit algorithm is an algorithm to smooth polylines (lines that are composed of linear line segments) by reducing the number of points. The simplified curve should preserve the rough shape of the original curve but consist only of a subset of the points that defined the original curve.
The degree of coarsening is controlled by a single parameter ε, which defines the maximum distance between the original points and the simplified curve.
The algorithm was developed independently by Urs Ramer in 1972 and by David Douglas and Thomas Peucker in 1973.

Algorithm

Given is the starting curve \( C \) as an ordered set of \( n \) points \[ C = (P_1, P_2, P_3, \cdots, P_n) \] and the distance dimension \( \varepsilon \) with \[ \varepsilon > 0 .\]

ε

The first approximation of \( C \) is the line segment \( \overline{P_1P_n} \). The algorithm marks the first and last point to be kept.
Now all \( n-2 \) inner points are looked at, to find the point \( P_m \) that is furthest from that line segment with \[ d_{max} = \underset{i=2 \cdots n-1}{\max} d(P_i, \overline{P_1P_n}). \] If \( d_{max} \) is within the tolerance \[ d_{max} \leq \varepsilon \] then the simplification is finished and all inner points can be discarded without the simplified curve being worse than \( \varepsilon \).

ε dmax

Else, \( P_m \) must be kept and the algorithm recursivly processes the new parts \[ C_1 = (P_1, \cdots, P_m) \] and \[ C_2 = (P_m, \cdots, P_n) .\]

Those parts are then again processed recursivly.

When the recursion is complete, the output curve is the set of all kept points.

Hands-On

Drag the Slider to change the value of ε and simplify the drawn curve. Click in the grid to draw new points. You can clear the curve by clicking on the Clear Button or you can restore a default path by choosing one from the Reset Button. The original line is displayed in dashed gray and the simplified line is displayed in solid blue.
Douglas-Peucker algorithm
Tolerance ε 0
Number of Points reduced from 0 to 0 (%)
0 50 100 150 50 100

References