Posts

Showing posts from May, 2010

The Ramer-Douglas-Peucker Polygon Simplification Algorithm

Image
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 dimentions. Here is how it roughly works: 0. Start with a polygon. 1. Make a polyline between the two endpoints. This is the initial approximation to the simplified polygon. 2. Calculate the distance between the edge and the remaining vertices. If the vertex tested is further away that the user defined tolerance, then the vertex is added to the simplification. 3. Repeat step 2 until you have a complete approximation of the polygon like shown in step 4 in the picture.   The idea with the algorithm is that we can give it an input like the o