Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or its Caricature

David H. Douglas and Thomas K. Peucker

Summary

The authors sought a method to reduce the number of points needed to record a digitized stroke. They proposed a corner finding algorithm to address this issue. The Douglas-Peucker algorithm uses a floating and anchor point. Initially, the floating point is the last point, and the anchor point is the first point. The points on a stroke in between the anchor and floating points are examined to find the point with the greatest perpendicular distance. If the distance is less than a threshold value, the line is determined to be a straight line segment. If the distance is greater than the threshold, the line has a curve in it, and the floating point is moved to that point. The algorithm recursively continues until it finds a straight line segment. Once a straight line is found, the floating point becomes the anchor point, and the floating point returns to the last point. The new anchor point is marked as a corner. The algorithm repeats until no more corners are found.

Discussion

The algorithm is affective for finding corners in polyline strokes. However, the algorithm struggles with finding corners with highly obtuse angles. These corners appear as straight lines to the algorithm. As well, the algorithm recursively iterates over points in the stroke extra times, which can cause longer performance times. It seems that a sawtooth line with spread out teeth would take a lengthy amount of time for this algorithm.