"Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line Or Its Caricature"

by Davis H Douglas and Thomas K Peucker

Summary

Finding representative points of lines helps to reduce the storage space needed and computational time of other computings which is proportional to the number of points in a caricature. One way to do this is by training computers with human decitions, but there are too many possible ways to represent a single class of feature. Another way is to approximate the points along a line with mathematical functions (ends of segments are averages of fixed number of points along the line), this misses important information in high curvature parts, while keeping too much information in the smoother part. Some algorithms focus on which points to be deleted (points closer than a threshold to neighbors are dropped, dropping points if line direction doesn't change much, deleting all but every Nth point), while others focus on which to be maintaained. 

The method provided by A.E.G which was discribed by T. Lang in 1969 is similar to the algorithm created by the authors. But the result is unsatisfying where sharp angles are numerous. This algorithm concentrates on selecting points.

An intuitive way to decide whether a series of points form a line is to find the furthest point from the line segments between end points, see whether the distance from the furthest point to the line connecting end points exceeds some threshold. The authors used 2 methods:

Method 1: 1) assign start point of curve as "anchor", the last point as "floater". 2) find the point with greatest perpendicular distance to the line segment between anchor and floater, assgin it to floater, repeat this step until furthest distance satisfy threshold. 3) move anchor to floater and assign the last point as floater, iterate from step 2.

Method 2: same as method 1, except keeping floaters of each iteration in a stack. The next iteration only chooses floaters from the stack built in the previous iteration. This method saves time by avoiding re-examining points.

For Lang's algorithm, it does line test on points in the order of (1, 2, 3), (1, 2, 4), (1, 3, 4), (1, 2, 5)...anchor moves to the point before the first point that does not allow all intervening points to satisfy the tolerance. Two modificiaitons on this algorithm is given by the authors. Modification 1 has the anchor move to the furthest point from the segment instead of the point before the floater. Modification 2 avoiding unnecessary repeated calculations of distance by testing if the accumulated total (sigma(Distance(Pn, P0Pn+1))) is greater than the tolerance.

Comparison on AEG (Lang's algorithm), AEG+Mod1, AEG+Mod2, AEG+Mod1+Mod2, Method1, Method2 shows that Method2 outperforms the other algorithms.

Discussion

This algorithm is like recursively doing line tests on the curve. But in terms of "corner" finding, it gives much more points that are just not in a line but are not corners, for example, points on a smooth arc, points in middle of the bottom line in "|__|".