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

June 28, 2014

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:

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.

/// <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:

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

csharp, gamedev, unity3d