Curve-fitting with piecewise parametric cubics
Parametric piecewise-cubic functions are used throughout the computer graphics industry to represent curved shapes. For many applications, it would be useful to be able to reliably derive this representation from a closely spaced set of points that approximate the desired curve, such as the input from a digitizing tablet or a scanner. This paper presents a solution to the problem of automatically generating efficient piecewise parametric cubic polynomial approximations to shapes from sampled data. We have developed an algorithm that takes a set of sample points, plus optional endpoint and tangent vector specifications, and iteratively derives a single parametric cubic polynomial that lies close to the data points as defined by an error metric based on least-squares. Combining this algorithm with dynamic programming techniques to determine the knot placement gives good results over a range of shapes and applications.
Plass, M. F.; Stone, M. Curve-fitting with piecewise parametric cubics. Proceedings of the 10th Annual Conference on Computer Graphics and Interactive Techniques; 1983 July 25-29; Detroit, MI. NY: ACM; 1983; 229-239.