Content deleted Content added
Kenneth Kho (talk | contribs) Removed idea section, it is unsourced since "big copy edit" revision in 2008, it is inaccurate as the algorithm does not use Hausdorff distance, in the algorithm the simplified curve is treated as a curve but the original curve is only treated using its vertices and the farthest point is always selected from the original curve, even if the idea section is correct it is still unnecessarily abstract and more confusing than the algorithm itself, feel free to discuss at my talk page |
→Similar algorithms: Added Imai-Iri (after Hiroshi Imai and Masao Iri) |
||
| (3 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=
== Algorithm ==
Line 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 yields a running time of {{math|''O''(''n''<sup>2</sup>)}}. 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|
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>
Line 66:
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''<sup>3</sup>)}}, 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=
==Similar algorithms==
Line 72:
Alternative algorithms for line simplification include:
* [[Visvalingam–Whyatt algorithm|Visvalingam–Whyatt]]
*
*
* * Zhao–Saalfeld
* Imai-Iri
== See also ==
| |||