Ramer–Douglas–Peucker algorithm: Difference between revisions

Revision as of 19:29, 17 December 2009

Latest revision as of 17:56, 8 June 2025

(170 intermediate revisions by more than 100 users not shown)

Line 1:

{{Short description|Curve simplification algorithm}}

The '''Douglas-Peucker algorithm''' is an [[algorithm]] for reducing the number of points in a curve that is approximated by a series of points. The initial form of the algorithm was independently suggested in 1972 by Urs Ramer and 1973 by David Douglas and Thomas Peucker. (See the References for more details.)

This algorithm is also known under the following names: the Ramer-Douglas-Peucker algorithm, the iterative end-point fit algorithm or the split-and-merge algorithm.

The '''Ramer–Douglas–Peucker algorithm''', also known as the '''Douglas–Peucker algorithm''' and '''iterative end-point fit algorithm''', is an algorithm that [[Decimation (signal processing)|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]]. It produces the most accurate generalization, but it is also more time-consuming.<ref>{{cite journal |last1=Shi |first1=Wenzhong |last2=Cheung |first2=ChuiKwan |title=Performance Evaluation of Line Simplification Algorithms for Vector Generalization |journal=The Cartographic Journal |date=2006 |volume=43 |issue=1 |pages=27–44 |doi=10.1179/000870406x93490}}</ref>

== Idea ==

The purpose of the algorithm is that given a 'curve' composed of line segments, find a similar curve with fewer points. The algorithm defines 'dissimilar' based on the maximum distance between the original curve and the simplified curve. The simplified curve consists of a subset of the points that defined the original curve.

== Algorithm ==

[[Image:Douglas_PeuckerDouglas-Peucker animated.pnggif|thumb|right|SmoothingSimplifying a piecewise linear curve with the Douglas-PeuckerDouglas–Peucker algorithm.]]

The starting curve is an ordered set of points or lines and the distance dimension {{math|''&epsilon;ε''&nbsp; >&nbsp;0. The original (unsmoothed) curve is shown in 0 and the final output curve is shown in blue on row 4}}.

<!--different implementation: The algorithm uses an array of boolean flags, initially set to not-kept, one for each point.-->

The algorithm [[recursion|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 furthestfarthest from the line segment with the first and last points as end points; (this point is obviouslyalways furthestfarthest on the curve from the approximating line segment between the end points). If the point is closer than ''&epsilon;''{{mvar|ε}} to the line segment, then any points not currently marked to keepbe kept can be discarded without the smoothedsimplified curve being worse than ''&epsilon;''{{mvar|ε}}.

If the point furthestfarthest from the line segment is greater than ''&epsilon;''{{mvar|ε}} from the approximation then that point must be kept. The algorithm recursively calls itself with the first point and the worstfarthest point and then with the worstfarthest point and the last point, (which includes marking the worstfarthest 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.

[[File:RDP, varying epsilon.gif|thumb|The effect of varying epsilon in a parametric implementation of RDP]]

=== Non-parametric Ramer–Douglas–Peucker ===

The choice of {{mvar|ε}} 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.<ref>{{cite journal |last1 = Prasad |first1 = Dilip K. |first2 = Maylor K.H. |last2 = Leung |first3 = Chai |last3 = Quek |first4 = Siu-Yeung |last4 = Cho |title = A novel framework for making dominant point detection methods non-parametric |journal = Image and Vision Computing |year = 2012 |volume = 30 |issue = 11 |pages = 843–859 |doi = 10.1016/j.imavis.2012.06.010 }}</ref>

=== Pseudocode ===

Assuming the input is a one-based array:

function DouglasPeucker(PointList[], epsilon)

<syntaxhighlight lang="python">

//Find the point with the maximum distance

# source: https://karthaus.nl/rdp/

dmax = 0

function DouglasPeucker(PointList[], epsilon)

index = 0

# Find the point with the maximum distance

for i = 2 to (length(PointList) - 1)

dmax = 0

d = OrthogonalDistance(PointList[i], Line(PointList[1], PointList[end]))

if dindex >= dmax0

indexend = ilength(PointList)

dmaxfor i = d2 to (end - 1) {

d = perpendicularDistance(PointList[i], Line(PointList[1], PointList[end]))

end

if (d > dmax) {

end

index = i

dmax = d

//If max distance is greater than epsilon, recursively simplify

if dmax >= epsilon }

//Recursive call}

recResults1[] = DouglasPeucker(PointList[1...index], epsilon)

ResultList[] = empty;

recResults2[] = DouglasPeucker(PointList[index...end], epsilon)

# If max distance is greater than epsilon, recursively simplify

// Build the result list

if (dmax > epsilon) {

ResultList[] = {recResults1[1...end-1] recResults2[1...end]}

# Recursive call

else

ResultList recResults1[] = {DouglasPeucker(PointList[1...index], PointList[end]}epsilon)

recResults2[] = DouglasPeucker(PointList[index...end], epsilon)

end

//Return # Build the result list

ResultList[] = {recResults1[1...length(recResults1) - 1], recResults2[1...length(recResults2)]}

return ResultList[]

} else {

end

ResultList[] = {PointList[1], PointList[end]}

}

# Return the result

return ResultList[]

</syntaxhighlight>

== Application ==

The algorithm is used for the processing of [[vector graphics]] and [[cartographic generalization]]. It is recognized as the one that delivers the best perceptual representations of the original lines. But a self-intersection could occur if the accepted approximation is not sufficiently fine which led to the development of variant algorithms.<ref>{{cite book |doi = 10.1109/SIBGRA.2003.1240992 |chapter = A non-self-intersection Douglas-Peucker algorithm |year = 2003 |last1 = Wu |first1 = Shin-Ting |title = 16th Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI 2003) |last2 = Marquez |first2 = Mercedes |pages = 60–66 |place = Sao Carlos, Brazil |publisher= IEEE|isbn = 978-0-7695-2032-2 |citeseerx = 10.1.1.73.5773 |s2cid = 10163908 }}</ref>

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

The algorithm is widely used in robotics<ref>{{cite webjournal |urldoi =http://asl 10.epfl.ch1007/aslInternalWeb/ASL/publications/uploadedFiles/nguyen_2005_a_comparison_of.pdfs10514-007-9034-y |title = A Comparisoncomparison of Lineline Extractionextraction Algorithmsalgorithms using 2D Laserrange Rangefinderdata for Indoorindoor Mobilemobile robotics Robotics|authoryear = 2007 |last1 = Nguyen and|first1 = Viet |last2 = Gächter |first2 = Stefan |last3 = Martinelli and|first3 = Agostino |last4 = Tomatis |first4 = Nicola |last5 = Siegwart |datefirst5 =2005 Roland |journal = Autonomous Robots |volume = 23 |issue = 2 |pages = 97–111 | url = http://doc.rero.ch/record/320492/files/10514_2007_Article_9034.pdf |hdl = 20.500.11850/9089 |s2cid = 35663952 |hdl-access = free }}</ref> to perform simplification and denoising of range data acquired by a rotating [[laser rangefinder|range scanner]],; in this field it is calledknown as the split-and-merge algorithm and is attributed to [[Richard O. Duda|Duda]] and [[Peter E. Hart|Hart]].<ref>{{cite book |first1=Richard O. |last1=Duda |authorlink1=Richard O. Duda |first2=Peter E. |last2=Hart |authorlink2=Peter E. Hart |title=Pattern classification and scene analysis |url=https://archive.org/details/patternclassific0000duda |url-access=registration |publisher=Wiley |___location=New York |year=1973 |isbn=0-471-22361-1}}</ref>

==References Complexity ==

*Urs Ramer, "An iterative procedure for the polygonal approximation of plane curves", Computer Graphics and Image Processing, 1(2), 244-256 (1972)

The running time of this algorithm when run on a polyline consisting of {{math|''n'' – 1}} segments and {{mvar|n}} vertices is given by the recurrence {{math|''T''(''n'') {{=}} ''T''(''i'' + 1) + ''T''(''n'' − ''i'') + [[Big O notation|''O''(''n'')]]}} where {{math|''i'' {{=}} 1, 2,..., ''n'' − 2}} is the value of <code>index</code> in the pseudocode. In the worst case, {{math|''i'' {{=}} 1}} or {{math|''i'' {{=}} ''n'' − 2}} at each recursive invocation yields a running time of {{math|''O''(''n''²)}}. In the best case, {{math|''i'' {{=}} {{sfrac|''n''|2}}}} or {{math|''i'' {{=}} {{sfrac|''n'' ± 1|2}}}} at each recursive invocation yields a running time of {{math|Ω(''n'' log ''n'')}}.

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

*JohnUsing (fully or semi-) [[dynamic convex hull]] data structures, the simplification performed by the algorithm can be accomplished in {{math|''O''(''n'' log ''n'')}} time.<ref>{{cite tech report |last1 = Hershberger &|first1 = John |first2 = Jack |last2 = Snoeyink, "|title = Speeding Up the Douglas-Peucker Line-Simplification Algorithm", Proc|date 5th= Symp on Data Handling, 134-143 (1992). UBC| Techurl Report TR-92-07 available at= http://www.csbowdoin.ubc.caedu/cgi-bin~ltoma/trteaching/1992cs350/TRspring06/Lecture-92-07Handouts/hershberger92speeding.pdf}}</ref>

Given specific conditions related to the bounding metric, it is possible to decrease the computational complexity to a range between {{math|''O''(''n'')}} and {{math|''O''(''2n'')}} through the application of an iterative method.<ref>{{Cite web|url=https://gist.github.com/stohrendorf/aea5464b1a242adca8822f2fe8da6612|title=ramer_douglas_peucker_funneling.py|website=Gist}}</ref>

* R.O. Duda and P.E. Hart, "Pattern classification and scene analysis", (1973), Wiley, New York (http://rii.ricoh.com/~stork/DHS.html)

The running time for [[digital elevation model]] generalization using the three-dimensional variant of the algorithm is {{math|''O''(''n''³)}}, but techniques have been developed to reduce the running time for larger data in practice.<ref>{{cite journal |last1=Fei |first1=Lifan |last2=He |first2=Jin |title=A three-dimensional Douglas–Peucker algorithm and its application to automated generalization of DEMs |journal=International Journal of Geographical Information Science |date=2009 |volume=23 |issue=6 |pages=703–718 |doi=10.1080/13658810701703001}}</ref>

== Notes ==

{{reflist}}

==ExternalSimilar linksalgorithms==

[[File:Douglas–Peucker and Visvalingam–Whyatt simplification algorithms.svg|thumb|Comparison with [[Visvalingam–Whyatt algorithm]]]]

Alternative algorithms for line simplification include:

* [[Visvalingam–Whyatt algorithm|Visvalingam–Whyatt]]

* Reumann–Witkam

* Opheim simplification

* Lang simplification

* Zhao–Saalfeld

* Imai-Iri

== See also ==

*[http://www.bdcc.co.uk/Gmaps/Services.htm You can see the algorithm applied to a GPS log from a bike ride at the bottom of this page]

* [[Curve fitting]]

== Further reading ==

{{refbegin}}

* {{cite journal|first=Urs |last=Ramer |title=An iterative procedure for the polygonal approximation of plane curves |journal=Computer Graphics and Image Processing |volume=1 |issue=3 |pages=244–256 |date=1972 |doi=10.1016/S0146-664X(72)80017-0}}

* {{cite journal|first1=David |last1=Douglas |first2=Thomas |last2=Peucker |title=Algorithms for the reduction of the number of points required to represent a digitized line or its caricature |journal=Cartographica: The International Journal for Geographic Information and Geovisualization |volume=10 |issue=2 |pages=112–122 |date=1973 |doi=10.3138/FM57-6770-U75U-7727}}

* {{cite conference|first1=John |last1=Hershberger |first2=Jack |last2=Snoeyink |title=Speeding Up the Douglas–Peucker Line-Simplification Algorithm |conference=Proceedings of the 5th Symposium on Data Handling |pages=134–143 |date=1992|page= }} UBC Tech Report TR-92-07 available at [http://www.cs.ubc.ca/cgi-bin/tr/1992/TR-92-07 Speeding Up the Douglas-Peucker Line-Simplification Algorithm | Computer Science at UBC]

* {{cite book|first1=R.O. |last1=Duda |first2=P.E. |last2=Hart |title=Pattern Classification and Scene Analysis |date=1973 |publisher=Wiley |___location=New York |bibcode=1973pcsa.book.....D |archive-url=https://web.archive.org/web/20110715184521/http://rii.ricoh.com/~stork/DHS.html |archive-date=2011-07-15 |url=http://rii.ricoh.com/~stork/DHS.html}}

* {{cite tech report |title = Line Generalisation by Repeated Elimination of the Smallest Area |series = Discussion Paper |number = 10 |first1 = M. |last1 = Visvalingam |first2 = J.D. |last2 = Whyatt |year = 1992 |institution = Cartographic Information Systems Research Group (CISRG), The University of Hull |url = https://hydra.hull.ac.uk/assets/hull:8338/content }}

{{refend}}

== References ==

[[Category:Computer graphics algorithms]]

{{reflist}}

==External links==

[[de:Douglas-Peucker-Algorithmus]]

* [https://www.boost.org/doc/libs/1_67_0/libs/geometry/doc/html/geometry/reference/algorithms/simplify/simplify_3.html Boost.Geometry support Douglas–Peucker simplification algorithm]

[[fr:Algorithme de Douglas-Peuker]]

* [http://www.codeproject.com/Articles/114797/Polyline-Simplification Implementation of Ramer–Douglas–Peucker and many other simplification algorithms with open source licence in C++]

* [http://idea.ed.ac.uk/data/kmz/ XSLT implementation of the algorithm for use with KML data.]

* [http://www.bdcc.co.uk/Gmaps/Services.htm You can see the algorithm applied to a GPS log from a bike ride at the bottom of this page]

* [http://karthaus.nl/rdp/ Interactive visualization of the algorithm]

* [http://fssnip.net/kY Implementation in F#]

* [https://github.com/odlp/simplify_rb Ruby gem implementation]

* [https://github.com/locationtech/jts JTS, Java Topology Suite], contains Java implementation of many algorithms, including the [https://locationtech.github.io/jts/javadoc/org/locationtech/jts/simplify/DouglasPeuckerSimplifier.html Douglas-Peucker algorithm]

* [https://rosettacode.org/wiki/Ramer-Douglas-Peucker_line_simplification Rosetta Code (Implementations in many languages)]

{{DEFAULTSORT:Ramer-Douglas-Peucker algorithm}}

[[Category:Computer graphics algorithms]]

[[Category:Geometric algorithms]]

[[Category:Digital signal processing]]

[[Category:Articles with example pseudocode]]