Ramer–Douglas–Peucker algorithm: Difference between revisions

Revision as of 15:37, 16 August 2024

Revision as of 13:58, 29 November 2024

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>

== Algorithm ==

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''³)}}, 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-718703–718 |doi=10.1080/13658810701703001}}</ref>

==Similar algorithms==