PiecewiseFitDoc.tioga
Bier, July 22, 1987 11:48:11 am PDT
Maureen Stone, September 25, 1987 5:47:00 pm PDT
Piecewise Fit
CEDAR 7.0 — FOR INTERNAL XEROX USE ONLY
Piecewise Fit
Curve Fitting with Piecewise Parametric Cubics
Maureen Stone
© Copyright 1987 Xerox Corporation. All rights reserved.
Abstract: This package implements the algorithm published by Michael Plass and Maureen Stone in the 1983 Siggraph Proceedings that uses an iterative technique to fit parametric cubic spline curves to sampled data represented as a sequence of points.
Created by: Maureen Stone and Michael Plass
Maintained by: <Stone.pa>
Keywords: curve, fitting, parametric, cubics, fit
XEROX   Xerox Corporation
    Palo Alto Research Center
    3333 Coyote Hill Road
    Palo Alto, California 94304

For Internal Xerox Use Only
1. Parametric Cubic Curve Fitting
This package implements the algorithm published in the 1983 Siggraph Proceedings that uses an iterative technique to fit parametric cubic spline curves to sampled data represented as a sequence of points.
The inner loop of the algorithm takes a sequence of samples and tries to fit a single parametric cubic piece to them. A parametric cubic is defined by two polynomial functions, X and Y, of a parameter, here called t. The input data is a sequence of sample points, (x,y). To fit a curve to these points, we assign a value of the parameter t for each point and use classic least-squares curve fitting to generate the coefficients of the polynomial functions X and Y. This curve is compared to the sample points and the values of t are reassigned to improve the fit. We then iterate until a satisfactory solution is achieved.
Complicated curve shapes are represented as a sequence of cubic pieces, often called a cubic spline. The position of the joints between the pieces, and the tangents at these points must be determined to generate a smooth approximation to a shape to complicated to fit with a single cubic piece. This package implements several algorithms for selecting the joints. Most of these algorithms assume that some other process has been used to select a subset of the sample positions as potential joints, and that the tangents have already been computed for all those potential joints.
2. Implementation
LSPieceImpl implements the iterative fitting algorithm for a single parametric cubic piece. Most clients will not call LSPieceImpl directly, but will use PiecewiseFit.
PiecewiseFitImpl implements a number of algorithms for selecting joints from a list of potential joints. Most clients are satisfied with GrowSpline. Use DynSpline if the data is noisy. your choice of potential joints is poor, or your are looking for the minimum number of cubic pieces for your curve.
Cubic2Proc: TYPE = PROC[bezier: Cubic2.Bezier, sumErr, maxDev: REAL, iterations: INT] RETURNS[quit: BOOLEAN ← FALSE];
The output curve and the metrics for its fit. The sum of the squares of the distances from the points to the curve are returned in sumErr, and the largest deviation is returned in maxDev.
FitSpline: PROC [data: Data, metrics: Metrics, outputCubic2: Cubic2Proc];
Makes every node a joint.
GrowSpline: PROC [data: Data, metrics: Metrics, outputCubic2: Cubic2Proc, hilight: Cubic2Proc ← NIL];
Finds joints by "growing" a cubic curve until the maximum deviation exceeds metrics.maxDev. Guarantees a fit within the maximum deviation Cheaper than DynSpline, but not as good results on noisy data.
DynSpline: PROC [data: Data, metrics: Metrics, penalty: REAL, trim: BOOLEAN ← TRUE, outputCubic2: Cubic2Proc, hilight: Cubic2Proc ← NIL];
Finds joints by dynamic programming. Penalty is the "cost" for making a joint. A larger penaltly will give you fewer joints. Trim turns on a heuristic to prune the dynamic programming tree. Use highlight if you want to display the intermediate cubics as the dynamic programming proceeds.
FitPiece: PROC [data: Data, from, thru: NAT, initFree, finalFree: BOOLEAN ← TRUE, metrics: Metrics, outputCubic2: Cubic2Proc];
Fits a single cubic piece in the range samples[from]..samples[thru]. If the curve is closed, thru can be smaller than from and the piece will "wrap around". initFree, finalFree ← TRUE force the curve through the end samples (default for all the above fitting procedures). Tangents should be set in the nodes and tangents sequences as above. This is here principally for client experimentation. Serious clients should use LSPiece.FitPiece for efficiency.
There is one algorithm that doesn't expect a preliminary selection of joints. This algorithm is under developement. Check with Maureen Stone before using it.
AdaptiveFit: PROC [data: Data, from, thru: NAT, initFree, finalFree: BOOLEAN ← TRUE, metrics: Metrics, outputCubic2: Cubic2Proc, tangent: TangentProc];
Ignores joint information and adaptively subdivides the samples, placing joints at the points of maximum deviation. The callback proc "tangent" will be called to get a tangent for the initial points and for each joint. Return [0,0] if tangent continuity is not desired.
2. Potential Joint Selection and Setting Tangents
There are routines in Fit.df that can be used for this purpose. See especially PotentialKnots.mesa