The Ramer–Douglas–Peucker algorithm, also known as the Douglas–Peucker algorithm and iterative end-point fit algorithm, is an algorithm that decimates a curve composed of line segments to a similar curve with fewer points. It was one of the earliest successful algorithms developed for

cartographic generalization Cartographic generalization, or map generalization, includes all changes in a map that are made when one derives a smaller-scale map from a larger-scale map or map data. It is a core part of cartographic design. Whether done manually by a cartog ...

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 In mathematics, the Hausdorff distance, or Hausdorff metric, also called Pompeiu–Hausdorff distance, measures how far two subsets of a metric space are from each other. It turns the set of non-empty compact subsets of a metric space into a me ...

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 . The algorithm

recursively Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...

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 farthest from the line segment with the first and last points as end points; this point is obviously farthest 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 farthest 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 farthest point and then with the farthest point and the last point, which includes the farthest 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. RDP, varying epsilon

Non-parametric Ramer–Douglas–Peucker

The choice of is usually user-defined. Like most line fitting, polygonal approximation or dominant point detection methods, it can be made non-parametric by using the error bound due to digitization and quantization as a termination condition.

Pseudocode

Assuming the input is a one-based array: # source: https://karthaus.nl/rdp/ function DouglasPeucker(PointList[], epsilon) # Find the point with the maximum distance dmax = 0 index = 0 end = length(PointList) for i = 2 to (end - 1) ResultList[] = empty; # If max distance is greater than epsilon, recursively simplify if (dmax > epsilon) else # Return the result return ResultList[]

Application

The algorithm is used for the processing of vector graphics and

. It does not always preserve the property of non-self-intersection for curves which has led to the development of variant algorithms. 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 ) (Polish, Ukrainian Carpathians) *Diple (Dalmatian Coast) *Tulum (Turkish and Pontic) *Tsambouna (Dodecanese and Cyclades) *Askambandoura (Crete) *Gajdy (Polish/Czech/Slovak) *Gaita ( Galician) *Surle (Serbian/Croatian) *Mezoued/Zukra (Northern A ...

and

Hart Hart often refers to: * Hart (deer) Hart may also refer to: Organizations * Hart Racing Engines, a former Formula One engine manufacturer * Hart Skis, US ski manufacturer * Hart Stores, a Canadian chain of department stores * Hart's Reptile Wo ...

Complexity

The running time of this algorithm when run on a polyline consisting of segments and vertices is given by the recurrence where is the value of index in the pseudocode. In the worst case, or at each recursive invocation and this algorithm has a running time of . In the best case or at each recursive invocation in which case the running time has the well-known solution (via the master theorem for divide-and-conquer recurrences) of . Using (fully or semi-)

dynamic convex hull The dynamic convex hull problem is a class of dynamic problems in computational geometry. The problem consists in the maintenance, i.e., keeping track, of the convex hull for input data undergoing a sequence of discrete changes, i.e., when input ...

data structures, the simplification performed by the algorithm can be accomplished in time.

Similar algorithms

Alternative algorithms for line simplification include: * Visvalingam–Whyatt * Reumann–Witkam * Opheim simplification * Lang simplification * Zhao–Saalfeld

References

External links

Boost.Geometry support Douglas–Peucker simplification algorithm

Implementation of Ramer–Douglas–Peucker and many other simplification algorithms with open source licence in C++

XSLT implementation of the algorithm for use with KML data.

* ttp://karthaus.nl/rdp/ Interactive visualization of the algorithm
Implementation in F#

Ruby gem implementation

JTS, Java Topology Suite
contains Java implementation of many algorithms, including th

Rosetta Code (Implementations in many languages)
{{DEFAULTSORT:Ramer-Douglas-Peucker algorithm Computer graphics algorithms Geometric algorithms Digital signal processing Articles with example pseudocode