Fitting straight lines to point patterns

In many types of point patterns, linear features are of greatest interest. A very general algorithm is presented here which determines non-overlapping clusters of points which have large linearity. Given a set of points, the algorithm successively merges pairs of clusters or of points, encompassing in the merging criterion both contiguity and linearity. The algorithm is a generalization of the widely-used Ward's minimum variance hierarchical clustering method. The application of this algorithm is illustrated using examples from the literature in biometrics and in character recognition.