Talk:Ramer–Douglas–Peucker algorithm: Difference between revisions

Revision as of 20:25, 30 March 2010

Latest revision as of 14:55, 14 March 2025

(25 intermediate revisions by 10 users not shown)

Line 1:

{{WikiProject banner shell|class=

Start|1=

{{WikiProject Computer graphics |importance=Low}}

}}

I am in the process of converting [[http://de.wikipedia.org/wiki/Douglas-Peucker-Algorithmus The Germain Wikipedia Article]] from the original using google bablefish. I can't figure out how to copy the images out of the german text. I'll keep at it but please help if you know how. I'll be back online later tonight.--[[User:GreatTurtle|GreatTurtle]] ([[User talk:GreatTurtle|talk]]) 19:23, 24 June 2008 (UTC)

Line 10 ⟶ 15:

OrthogonalDistance should have an article, otherwise this is senseless - search google for orthogonal distance and you will catch it; there's no pseudocode function with that name ;) -- Tvali

::Perhaps it's just there to signify the orthogonal distance, youit dumbshould fuckbe obvious.

== Algorithm ==

{{Quote frame|It then finds the point that is farthest from the line segment...}}

In the '''Pseudocode''' section the distance measure used is the perpendicular distance from a point to a line: <code>perpendicularDistance(PointList[i], Line(PointList[1], PointList[end]))</code>.<br>

An alternative is (shortest) distance from a point to a line segment (see also [https://karthaus.nl/rdp/ this]). The latter differs from the former if the projection of the point on the line does not lie between the two points defining the line. In this case the distance of the point from the line segment is the distance of the point to whichever line endpoint is closest. [[User:Petkond|Petkond]] ([[User talk:Petkond|talk]]) 12:24, 25 March 2024 (UTC)

== Visvalingam’s algorithm ==

There's a blog [http://bost.ocks.org/mike/simplify/ here] explaining Visvalingam’s algorithm, a different (and purportedly more effective) line simplification algorithm. [[User:Diego Moya|Diego]] ([[User talk:Diego Moya|talk]]) 10:21, 28 September 2012 (UTC)

== Pseudocode ==

Is it just me or is the pseudocode wrong? In this line:

ResultList[] = {recResults1[1...end-1] recResults2[1...end]}

...you'd go off the end of the arrays which are shorter than the original array. <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/86.0.255.208|86.0.255.208]] ([[User talk:86.0.255.208|talk]]) 20:02, 5 November 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

...yeah looking at this further it appears that in copying from the German page, this line has been added:

end = length(PointList)

Well-meaning, but wrong. In the German pseudocode it appears that 'end' simply means the length of the array being talked about at that moment. <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/86.0.255.208|86.0.255.208]] ([[User talk:86.0.255.208|talk]]) 20:50, 5 November 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

Yep. I couldn't get the algorithm working at all using that pseudocode—the array indexes were just too confusing. I got it working quite well by looking [[http://karthaus.nl/rdp/|here]], and have emailed the author to ask him to clean this one up. If he doesn't, I'll have a go myself. [[User:Original mikz|MikZ]] ([[User talk:Original mikz|talk]]) 00:08, 15 March 2014 (UTC)

I just programmed that in AutoLisp and did not get any reduction until my head was wounded from scratching and I modified recResults2'''[1...end]''' to '''[2...end]''', which eliminates the point which is found with the index variable, similiar to the previously recResults1[1...end-1], which I think is the whole purpose of the recursive algorithm. Maybe a specialist can look into that. Please contact me, if this problem is solved or analyzed, my adress is abgang_at_ok.de. <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/91.232.232.180|91.232.232.180]] ([[User talk:91.232.232.180#top|talk]]) 18:30, 7 December 2016 (UTC)</small> <!--Autosigned by SineBot-->

== Analysis ==

I just corrected the analysis section. The recurrence <math>T(n)=2T(n/2)+ O(n)</math> doesn't describe the average the running time of the algorithm under any reasonable interpretation of average-case. That particular recurrence does resolve to <math>\Theta(n\log n)</math> and the expected running-time of the algorithm is <math>\Theta(n\log n)</math> under some interpretations of average-case, though. <!-- Template:Unsigned --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Patmorin|Patmorin]] ([[User talk:Patmorin#top|talk]] • [[Special:Contributions/Patmorin|contribs]]) 19:07, 10 December 2019 (UTC)</small> <!--Autosigned by SineBot-->