Content deleted Content added
m Dating maintenance tags: {{Linkrot}} |
PinkDucky91 (talk | contribs) Filled in 1 bare reference(s) with reFill 2 |
||
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]].
Line 67:
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>
==Similar algorithms==
Line 85:
* {{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 }}
| |||