Ramer–Douglas–Peucker algorithm

Idea

The purpose of the algorithm is, given a curve composed of line segments (which is also called a Polyline in some contexts), to find a similar curve with fewer points. The algorithm defines 'dissimilar' based on the maximum distance between the original curve and the simplified curve (i.e., the Hausdorff distance between the curves). The simplified curve consists of a subset of the points that defined the original curve.

Algorithm

The starting curve is an ordered set of points or lines and the distance dimension ε > 0.

The algorithm recursively divides the line. Initially it is given all the points between the first and last point. It automatically marks the first and last point to be kept. It then finds the point that is furthest from the line segment with the first and last points as end points; this point is obviously furthest on the curve from the approximating line segment between the end points. If the point is closer than ε to the line segment, then any points not currently marked to be kept can be discarded without the simplified curve being worse than ε.

If the point furthest from the line segment is greater than ε from the approximation then that point must be kept. The algorithm recursively calls itself with the first point and the furthest point and then with the furthest point and the last point, which includes the furthest point being marked as kept.

When the recursion is completed a new output curve can be generated consisting of all and only those points that have been marked as kept.

Non-parametric Ramer-Douglas-Peucker

The choice of ε is usually user-defined. Like most line fitting / polygonal approximation / dominant point detection methods, it can be made non-parametric by using the error bound due to digitization / quantization as a termination condition. MATLAB code for such a non-parametric RDP algorithm is available here.

Pseudocode

(Assumes the input is a one-based array)

function DouglasPeucker(PointList[], epsilon) // Find the point with the maximum distance dmax = 0 index = 0 end = length(PointList) for i = 2 to ( end - 1) { d = perpendicularDistance(PointList[i], Line(PointList[1], PointList[end])) if ( d > dmax ) { index = i dmax = d } } // If max distance is greater than epsilon, recursively simplify if ( dmax > epsilon ) { // Recursive call recResults1[] = DouglasPeucker(PointList[1...index], epsilon) recResults2[] = DouglasPeucker(PointList[index...end], epsilon) // Build the result list ResultList[] = {recResults1[1...length(recResults1)-1], recResults2[1...length(recResults2)]} } else { ResultList[] = {PointList[1], PointList[end]} } // Return the result return ResultList[] end

Application

The algorithm is used for the processing of vector graphics and cartographic generalization.

The algorithm is widely used in robotics to perform simplification and denoising of range data acquired by a rotating range scanner; in this field it is known as the split-and-merge algorithm and is attributed to Duda and Hart.

Complexity

The expected complexity of this algorithm can be described by the linear recurrence T(n) = 2T( ⁿ⁄₂) + O(n), which has the well-known solution (via the master theorem) of T(n) ∈ Θ(n log n). However, the worst-case complexity is Θ(n²).

Other line simplification algorithms

Alternative algorithms for line simplification include:

Visvalingam–Whyatt

Reumann–Witkam

Opheim simplification

Lang simplification

Zhao-Saalfeld