Reduce the number of points in a polygon with the Ramer-Douglas-Peucker algorithm

Some of you already saw the potential of using marching squares algorithm to trace the contour of an image, because once you have a the contour of an image, it’s easy to convert it in a Box2D shape.

The problem is the resulting shape has too much points, the logo rendered in the example counts 2,200 points, way too much.

We really need to reduce the number of points. That’s where Ramer-Douglas-Peucker algorithm comes to help us.

The purpose of the algorithm is, given a curve composed of line segments, to find a similar curve with fewer points. The algorithm defines ‘dissimilar’ based on the maximum distance between the original curve and the simplified curve. The simplified curve consists of a subset of the points that defined the original curve.

Marius Karthaus wrote a nice javascript example of the RDP algorithm I ported to AS3 adding it to previous example, see highlighted lines:

Everything is ruled by the second argument of RDP function, usually called epsilon, which in this case should run from 0.2 to 0.8.

Have a look at the final example, traced on the right of the stage, made with just 343 points with a 0.50 epsilon value:

No need to download anything, just copy-paste this code in the main class of the original example.

  • Hi,

    nice tutorial, like the idea very much. For reducing points I also like the
    Lang Simplification and McMaster’s Slide Averaging Algorithm
    http://www.motiondraw.com/blog/?p=50

    another approach is the Douglas Peuker Line Generalization
    http://lostinactionscript.com/2007/07/11/douglas-peuker-line-generalization/
    but the result is not so well in my opinion

    however very useful topic for game editors and other stuff :-)

  • Pingback: Understanding polygon clipping and introducing PolygonClipper AS3 class - Emanuele Feronato()

  • XELAD

    Just having a square, or figure with vertical or horizontal lines, you’ll see that optimised array lost verteces which constructed those lines, not depending on epsilon. Don’t know, why Marius Karthaus called that problem solved here http://karthaus.nl/rdp … Seem like there is a problem in his finding perpendicular’s distance.

  • jackwild

    I’m not sure that this is a good use of RDP. The algorithm would make more sense to be run twice between the start point and the furthest vertex away (x) and then again between the end point and x+1. Joining these two results together should give an RDP simplification of a closed loop without the arbitrary grouping.