Ramer-Douglas-Peucker algorithm

The Douglas-Peucker algorithm is an algorithm for smoothing curves. The initial form of the algorithm was established in 1973 by David Douglas and Thomas Peucker.

Idea

The purpose of the algorithm is that given a 'curve' cmposed of line segments to find a curve not too dissimilar but that has fewer points. The algorithm defines 'too dissimilar' based on the maximum distance between the original curve and the smoothed curve. The smoothed 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 original (unsmoothed) curve is shown in 0 and the final output curve is shown in blue on row 4.

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 keep can be discarded without the smoothed 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 worst point and then with the worst point and the last point (which includes marking the worst 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.

Pseudocode

function DouglasPeucker(PointList [] , epsilon) //Find the point with the maximum distance dmax = 0 index = 0 for i = 2 to (length(PointList) - 1) d = OrthogonalDistance(PointList [i] , Distance(PointList [1] , PointList [end] )) if d > dmax index = i dmax = d end end //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...end-1] recResults2 [1...end] } else ResultList [] = {PointList [1] , PointList [end] } end //Return the result return ResultList [] end

Application

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

References

*David Douglas & Thomas Peucker, "Algorithms for the reduction of the number of points required to represent a digitized line or its caricature", The Canadian Cartographer 10(2), 112-122 (1973)

*John Hershberger & Jack Snoeyink, "Speeding Up the Douglas-Peucker Line-Simplification Algorithm", Proc 5th Symp on Data Handling, 134-143 (1992). UBC Tech Report available online from NEC ResearchIndex.