Talk:Ramer–Douglas–Peucker algorithm

	This article is within the scope of WikiProject Computer graphics, a collaborative effort to improve the coverage of computer graphics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer graphicsWikipedia:WikiProject Computer graphicsTemplate:WikiProject Computer graphicscomputer graphics articles
Low	This article has been rated as Low-importance on the project's importance scale.

I am in the process of converting [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.--GreatTurtle (talk) 19:23, 24 June 2008 (UTC)[reply]

I added the picture for you. Good luck with the translation! -- Jitse Niesen (talk) 12:10, 26 June 2008 (UTC)[reply]

That sounds like a terrible idea. 141.219.95.119 (talk) 16:24, 30 June 2008 (UTC)[reply]

I'm familiar with the algorithm, and know enough German to translate (with assistance from a dictionary for technical jargon). —Preceding unsigned comment added by 152.23.48.85 (talk) 20:00, 24 July 2008 (UTC)[reply]

My mother tongue is German, but I know enough English to notice that the translation is terrible. —Preceding unsigned comment added by 193.142.125.1 (talk) 17:20, 10 September 2008 (UTC)[reply]

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, it should be obvious.

Algorithm

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: perpendicularDistance(PointList[i], Line(PointList[1], PointList[end])).
An alternative is (shortest) distance from a point to a line segment (see also 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. Petkond (talk) 12:24, 25 March 2024 (UTC)[reply]

Visvalingam’s algorithm

There's a blog here explaining Visvalingam’s algorithm, a different (and purportedly more effective) line simplification algorithm. Diego (talk) 10:21, 28 September 2012 (UTC)[reply]

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. — Preceding unsigned comment added by 86.0.255.208 (talk) 20:02, 5 November 2013 (UTC)[reply]

...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. — Preceding unsigned comment added by 86.0.255.208 (talk) 20:50, 5 November 2013 (UTC)[reply]

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 [[1]], and have emailed the author to ask him to clean this one up. If he doesn't, I'll have a go myself. MikZ (talk) 00:08, 15 March 2014 (UTC)[reply]

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. — Preceding unsigned comment added by 91.232.232.180 (talk) 18:30, 7 December 2016 (UTC)[reply]

Analysis

I just corrected the analysis section. The recurrence $T(n)=2T(n/2)+O(n)$ doesn't describe the average the running time of the algorithm under any reasonable interpretation of average-case. That particular recurrence does resolve to $\Theta (n\log n)$ and the expected running-time of the algorithm is $\Theta (n\log n)$ under some interpretations of average-case, though. — Preceding unsigned comment added by Patmorin (talk • contribs) 19:07, 10 December 2019 (UTC)[reply]