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: