The Ramer-Douglas-Peucker polygon simplification algorithm
One of the important algorithms in vector graphics and robotics is the Ramer-Douglas-Peucker algorithm. It simplifies a polygon by reducing the number of points by some tolerance. It was invented independently by Urs Ramer in 1972 and by David Douglas & Thomas Peucker in 1973. In 1992 it was improved by John Hershberger & Jack Snoeyink at the cost of the algorithm only working with simple 2D planar polylines, and not in higher dimensions.
Here is how it roughly works:
- Start with a polyline and a distance tolerance.
- Connect its two endpoints as the initial approximation.
- Find the intermediate vertex farthest from that segment. If its distance exceeds the tolerance, retain it and split the polyline there.
- Repeat on both subsegments until every remaining deviation is within the tolerance.
The idea with the algorithm is that we can give it an input like the one to the left and get an output like the one to the right:
This gives us a lot of possibilities; it can reconstruct the original representation of a polygon and it can provide us with compression of the data. A large and complicated polygon can be simplified down to the bare essentials by reducing the details of the polygon.
I’ve added this algorithm to Farseer Physics Engine 3.0.