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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
public static List DouglasPeucker(List points, int startIndex, int lastIndex, float epsilon) { float dmax = 0f; int index = startIndex; for (int i = index + 1; i < lastIndex; ++i) { float d = PointLineDistance(points[i], points[startIndex], points[lastIndex]); if (d > dmax) { index = i; dmax = d; } } if (dmax > epsilon) { var res1 = DouglasPeucker(points, startIndex, index, epsilon); var res2 = DouglasPeucker(points, index, lastIndex, epsilon); var finalRes = new List(); for (int i = 0; i < res1.Count-1; ++i) { finalRes.Add(res1[i]); } for (int i = 0; i < res2.Count; ++i) { finalRes.Add(res2[i]); } return finalRes; } else { return new List(new Vector2[] { points[startIndex], points[lastIndex] }); } } public static float PointLineDistance(Vector2 point, Vector2 start, Vector2 end) { if (start == end) { return Vector2.Distance(point, start); } float n = Mathf.Abs((end.x - start.x) * (start.y - point.y) - (start.x - point.x) * (end.y - start.y)); float d = Mathf.Sqrt((end.x - start.x) * (end.x - start.x) + (end.y - start.y) * (end.y - start.y)); return n / d; } |

## 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
/// <summary> /// Ramer-Douglas-Peucker algorithm which reduces a series of points /// to a simplified version that loses detail, /// but maintains the general shape of the series. /// </summary> public static BitArray DouglasPeucker(List points, int startIndex, int lastIndex, float epsilon) { var stk = new Stack<KeyValuePair<int, int>>(); stk.Push(new KeyValuePair<int, int>(startIndex, lastIndex)); int globalStartIndex = startIndex; var bitArray = new BitArray(lastIndex-startIndex+1, true); while (stk.Count > 0) { startIndex = stk.Peek().Key; lastIndex = stk.Peek().Value; stk.Pop(); float dmax = 0f; int index = startIndex; for (int i = index + 1; i < lastIndex; ++i) { if (bitArray[i - globalStartIndex]) { float d = PointLineDistance(points[i], points[startIndex], points[lastIndex]); if (d > dmax) { index = i; dmax = d; } } } if (dmax > epsilon) { stk.Push(new KeyValuePair<int, int>(startIndex, index)); stk.Push(new KeyValuePair<int, int>(index, lastIndex)); } else { for (int i = startIndex + 1; i < lastIndex; ++i) { bitArray[i - globalStartIndex] = false; } } } return bitArray; } public static List DouglasPeucker(List points, float epsilon) { var bitArray = DouglasPeucker(points, 0, points.Count - 1, epsilon); var resList = new List(); for (int i = 0, n = points.Count; i < n; ++i) { if (bitArray[i]) { resList.Add(points[i]); } } return resList; } |

This is how I have used it:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
if (_vertexCountBefoureDouglas > verticesNeededToStartLineSimplify) { // 1. find points that need to be removed int n = _points.Count; int startIndex = Math.Max(0, n - _vertexCountBefoureDouglas); int lastIndex = n - 1; BitArray acceptedPointsIndices = MathUtils.DouglasPeucker(_points, startIndex, lastIndex, pointReductionTubeWidth); // 2. remove points not accepted by Ramer, Douglas and Peucker int pointsRemovedCount = 0; for (int i = startIndex; i <= lastIndex; ++i) { if (!acceptedPointsIndices[i - startIndex]) { _points.RemoveAt(i - pointsRemovedCount); ++pointsRemovedCount; } } //Debug.Log("Douglas has removed points: " + pointsRemovedCount); _vertexCountBefoureDouglas = 0; } |

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:

- Converting Recursion to Iteration - article based on quicksort
- How to replace recursive functions using stack and while-loop to avoid the stack-overflow

More resources about the algorithm:

- Speeding Up the Douglas-Peucker Line-Simplification Algorithm - a different approach to the algorithm optimization
- http://mappinghacks.com/code/PolyLineReduction/ - already implemented iterative version of this algorithm but made little differently
- https://github.com/sebleier/RDP/blob/master/__init__.py - super simple Python implementation of the algorithm
- https://github.com/LukaszWiktor/series-reducer - implementation made in Java. Also source of image put in article