Iterative version of Ramer-Douglas-Peucker line-simplification algorithm

In one of our games we needed to beautify user mouse or touch input. Actually it isn’t simple task since there can be found many criteria due to point reduce. I have tried several solutions like discovering big angle change between segments (built of last given input points), big distance discovering, Catmul-Rom curve approximation and even joining all of those methods.

Later on I have found Ramer-Douglas-Peucker algorithm which helped to reduce unneeded points in a more visually proper way. In the end I’ve been reducing points by small distance and little angle between segments to put less points into the algorithm. Since it had to be done in realtime that wasn’t enough of optimizations. Next optimization was to make the iterative version of Douglas-Peucker algorithm.

Ramer-Douglas-Peucker algorithm

Picture is worth thousand words. Following image presents the algorithm output:

Most implementations are presented in recursive version since it’s best to read and understand:

Optimize that algorithm!

To achieve some little more performance I have written iterative version but instead of instantiating collections (which will have to be garbaged anyway!) I just return BitArray representing which indices of given input list should be thrown away. It is up to function user to remove points or create other list.

This is how I have used it:

Reduction algorithm is being called for every  verticesNeededToStartLineSimplify of new points.

Resources

If you want to learn how to generally compete with transforming recursive functions into iterative versions, there are good articles on it:

More resources about the algorithm:

  • Qing

    It helped me. rdp is a great algorithm.

  • Jesús Álvarez

    where is placed this code? i dont know how to use your algorithm

    if (_vertexCountBefoureDouglas > verticesNeededToStartLineSimplify) {

    can you help me with full example of how to use your algothim?

    stack call

    • This condition you copied is useful for games, where you simplify your path multiple times per second, while drawing a line. If you’re not drawing a line but simply want to reduce a data for chart, then simply omit the “_vertexCountBefoureDouglas” part.

      • Jesús Álvarez

        thank you very much

  • adolf sean

    was hoping to find a program that generates random lines using Douglas Peucker simplification.how can i get any help.

  • Hein Rutjes

    Awesome, thank you so much for this algorithm, excellent work!
    I wrote a version optimised for geo coordinates, if anyone is interested:
    https://gist.github.com/IjzerenHein/8db810ec6e30bf2dbfe1a7d99bde88ba

    • Wow, great contribution to the topic! Thanks!

  • Pelle Liljendal

    Did you ever profile your optimization?

    I tried reducing the number of points on the same data-set using your implementation, and the implementation from this library: https://github.com/burningmime/curves

    Your implementation takes approx. 64% longer than the other one (12.68 seconds vs. 7.71 seconds on the same data-set with, 100.000 iterations). I’m not pointing any fingers at your implementation, but just wanted to give you a heads up.

    • Thanks for the benchmark! The main problem here was how to change the algorithm. I remember profiling it at some bit, however I don’t even remember if that’s the final code. The clou here is iterative vs recursive. This alone optimization seemed to be enough for me back then, however I don’t remember any details about it.