Ramer Douglas Peucker
The Ramer-Douglas–Peucker algorithm is an algorithm for reducing the number of points in a curve that is approximated by a series of points. It does so by "thinking" of a line between the first and last point in a set of points that form the curve. It checks which point in between is farthest away from this line. If the point (and as follows, all other in-between points) is closer than a given distance 'epsilon', it removes all these in-between points. If on the other hand this 'outlier point' is farther away from our imaginary line than epsilon, the curve is split in two parts:
- From the first point up to and including the outlier
- The outlier and the remaining points.
The function is recursively called on both resulting curves, and the two reduced forms of the curve are put back together.
Bad implementations on the web
On the web I found many Ramer Douglas Peucker implementations, but most of the top results on google contained bugs. Even the original example on Wikipedia was making mistakes.
The bugs were ranging from bad calculation of the perpendicular distance of a point to a line (often they contained a devide by zero error for vertical lines), to discarding points that should not be removed at all. To see this in action, just try running the algorithm on it's own result with the same epsilon, many implementations will keep on reducing more and more points until there is no spline left. A correct implementation of RDP will remove *all* points that it can remove given a certain epsilon in the first run.
I hope that by looking at the source code for my Ramer Douglas Peucker implementation you will be able to get a correct reduction of your dataset.
