# 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 :-)