Algorithms for reduction of the number of points required to represent a stroke

-Douglas, Peucker

COMMENTS

SUMMARY

Most digitizers record far more points than are required to represent basic strokes. This paper concerns with reducing this number. In the past some algorithms which do this concentrate on deleting points, whereas others select points. The methods proposed in this paper belong to the latter category. A point between two end points is selected if it is at a greater perpendicular distance than a threshold, otherwise the two end-points are considered to be enough to represent the stroke between them. This idea was implemented in two different ways and tested. The first point is defined as the anchor and the last point as the floater. The intervening points along the stroke are examined to find the one with greatest perpendicular distance from the line formed by the anchor and floater. If this distance is less than a threshold then only the end-points are selected and the rest of the points are discarded. Otherwise, the point having the maximum distance from the line is made the new floater. This cycle continues and once the minimum distance requirement is met, the anchor is moved to floater and the last point on the stroke is re-assigned as the floating point. The second method is different only in one way-the points that have been floaters are stacked in a vector. When the anchor moves to the floater, the new floater is then selected from the top of this stack. Thus, this avoids re-examining all points between the floater and the end point. The algorithm was tested with many data sets and was found to be suitable for simple reduction and abstractions.

DISCUSSION

The algorithm is very simple and I believe can be implemented with a simple recursive procedure. Since the algorithm uses an 'selection of points' approach instead of deletion, so its very efficient in case of strokes which are more abstract and can be represented with few number of feature points.