Content deleted Content added
Citation bot (talk | contribs) Alter: template type, page. Add: bibcode, pages. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Abductive | Category:Geometric algorithms | #UCB_Category 80/82 |
Citation bot (talk | contribs) Add: s2cid. | Use this bot. Report bugs. | #UCB_CommandLine |
||
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 journal |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 |s2cid = 35663952 |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 64:
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 has a running time of {{math|[[Big theta|''Θ''(''n''<sup>2</sup>)]]}}. In the best case {{math|''i'' {{=}} {{sfrac|''n''|2}}}} or {{math|''i'' {{=}} {{sfrac|''n'' ± 1|2}}}} at each recursive invocation in which case the 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
==Similar algorithms==
Line 84:
* {{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
* {{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
{{refend}}
| |||