An implementation of a fast split and merge algorithm for the linear approximation of a planar curve

A honeycomb core replication system is used as an example of how a modified implementation of the split and merge algorithm for the linear segmentation of planar curves can be used to quickly thin data and to extract features from vision data. In particular the author pre sents a filter and three modifications to the standard split and merge algorithms found in the literature. These modifications decrease the computation time required to determine the breakpoints in a set of data. Specifically, these three improvements are (1) the error predicate used for split and merge is taken as the sum of the absolute value of the greatest positive and negative normal deviations from the approximating line to the data points in the segment, (2) split can trisect a segment, and (3) the breakpoints are labeled during the split and merge process so that the resulting breakpoints can be syntactically analyzed. The filter presented removes spikes from the data base and performs a second function of finding candidate breakpoints for the split and merge algorithm.