Ramer–Douglas–Peucker algorithm: Difference between revisions

Revision as of 12:30, 5 August 2024

Latest revision as of 17:56, 8 June 2025

(6 intermediate revisions by 3 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]]. 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-4427–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 63 ⟶ 60:

== 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 tech 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>

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==

Line 73 ⟶ 72:

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 ==