Ramer–Douglas–Peucker algorithm: Difference between revisions

Revision as of 00:23, 27 May 2022

Latest revision as of 17:56, 8 June 2025

(27 intermediate revisions by 14 users not shown)

Line 1:

{{Short description|Curve simplification 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]].

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, given a [[Polygonal chain|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 ==

Line 9 ⟶ 8:

<!--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 farthest from the line segment with the first and last points as end points; this point is obviouslyalways farthest on the curve from the approximating line segment between the end points. If the point is closer than {{mvar|ε}} to the line segment, then any points not currently marked to be kept can be discarded without the simplified curve being worse than {{mvar|ε}}.

If the point farthest from the line segment is greater than {{mvar|ε}} 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.

Line 55 ⟶ 54:

== Application ==

The algorithm is used for the processing of [[vector graphics]] and [[cartographic generalization]]. It doesis notrecognized alwaysas preservethe one that delivers the propertybest perceptual representations of non-the original lines. But a self-intersection forcould curvesoccur whichif hasthe 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 widely used in robotics<ref>{{cite conferencejournal |doi = 10.1007/s10514-007-9034-y |title = A comparison of line extraction algorithms using 2D range data for indoor mobile robotics |year = 2007 |last1 = Nguyen |first1 = Viet |last2 = Gächter |first2 = Stefan |last3 = Martinelli |first3 = Agostino |last4 = Tomatis |first4 = Nicola |last5 = Siegwart |first5 = 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 known 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>

== Complexity ==

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 and this algorithm hasyields a running time of {{math|[[Big theta|''ΘO''(''n''²)]]}}. In the best case, {{math|''i'' {{=}} {{sfrac|''n''|2}}}} or {{math|''i'' {{=}} {{sfrac|''n'' ± 1|2}}}} at each recursive invocation inyields which case thea running time has the well-known solution (via the [[master theorem (analysis of algorithms)|master theorem for divide-and-conquer recurrences]]) of {{math|''O''Ω(''n'' log ''n'')}}.

Using (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 techreporttech report |last1 = Hershberger |first1 = John |first2 = Jack |last2 = Snoeyink |title = Speeding Up the Douglas-Peucker Line-Simplification Algorithm |date = 1992 | url = http://www.bowdoin.edu/~ltoma/teaching/cs350/spring06/Lecture-Handouts/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>

==Similar algorithms==

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>

==Similar algorithms==

[[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 algorithm|Reumann–Witkam]]

* [[Opheim simplification
* algorithm|OpheimLang simplification]]

* Zhao–Saalfeld

* [[Lang simplification algorithm|Lang simplification]]

* Imai-Iri

* [[Zhao–Saalfeld algorithm|Zhao–Saalfeld]]

== See also ==

Line 79 ⟶ 83:

== 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 |pagepages=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 CanadianInternational Journal for Geographic Information and CartographerGeovisualization |volume=10 |issue=2 |pagepages=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 |pagepages=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 techreporttech 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}}