Ramer–Douglas–Peucker algorithm: Difference between revisions

Revision as of 22:37, 22 March 2023

Revision as of 09:51, 14 May 2023

Line 58:

The algorithm is used for the processing of [[vector graphics]] and [[cartographic generalization]]. It does not always preserve the property of non-self-intersection for curves which has 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 |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 ==

Line 80:

== 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=The Canadian Cartographer |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

* {{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 techreport |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}}