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.→ Continue reading