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.
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.
Note
Edward Lee pointed out that instead of using the "perpendicular distance" from a point to a line, the algorithm should use the 'Shortest Distance' from a point to a line segment. The graph will show a green line when the two differ. The 'diff' example shows the two differentiating in their outcome.
You can create your own dataset by clicking the 'create dataset button, adding points to the graph and storing the dataset.
