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

Revision as of 18:31, 7 December 2016

Latest revision as of 14:55, 14 March 2025

(16 intermediate revisions by 5 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 12 ⟶ 17:

::Perhaps it's just there to signify the orthogonal distance, it should be 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 ==

Line 32 ⟶ 41:

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-->