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

Comments

Summary

This paper proposes an algorithm for the poly line simplification. This can be useful in situations where your graphical application must draw many poly lines and time becomes an issue, like cartographic applications. Although this is a line simplification algorithm but it can be usefull in finding the corner in a particular sketch.

The algorithm works by first finding the two end points of sketch, which is the starting and and ending point of the sketch. Then it tries to find the point which is most distant in terms of the euclidean distance from the two points. If the euclidean distance is above the threshold value the algorithm assumes that this is not a line and there are possible corners on the line. The farthest point away becomes the corner and also the ending point for the starting points and starting point for the ending point.

The process is repeated recursively until no points can be found above the threshold. The algorithm works well and finds corners with good accuracy on polygons. While working with curves the algorithm sometimes calculate two points for a single point.

Discussion

The algorithm is the well defined and seems to work well for polygons. It's a very basic algorithm and several improvements can be made on it to produce better results with curves and arcs.