# 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 \).

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

*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.

## References

- Wikipedia:
*Ramer–Douglas–Peucker algorithm*, February 2018 - Urs Ramer:
*An iterative procedure for the polygonal approximation of plane curves. In Computer Graphics and Image Processing. Volume 1, Issue 3, Pages 244-256*, 1972 - David Douglas, Thomas Peucker:
*Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. In Cartographica: The International Journal for Geographic Information and Geovisualization. Volume 10, Issue 2, Pages 112–122*, 1973 - Vladimir Agafonkin:
*Simplify.js*, 2017