PiecewiseFit.mesa
Copyright © 1984, 1985 by Xerox Corporation. All rights reserved.
Written by Michael Plass and Maureen Stone
Last Edited by Maureen Stone September 13, 1984 2:52:59 pm PDT
Doug Wyatt, September 5, 1985 1:18:08 pm PDT
Public Interface to the piecewise cubic fitting routines
DIRECTORY
Seq USING [JointSequence, ComplexSequence],
Rope USING [ROPE],
LSPiece USING [Metrics],
Cubic USING [Bezier];
PiecewiseFit: CEDAR DEFINITIONS = {
Data: TYPE = REF DataRec;
DataRec:
TYPE =
RECORD [
samples: Seq.ComplexSequence,
closed: BOOLEAN,
joints: Seq.JointSequence, --[index: NAT, forced: BOOLEAN]
tangents: Seq.ComplexSequence --two per potentialKnot; tanIn, tanOut
];
Samples are a sequence of points. Closed indicates a closed shape (don't double endpoints)
The joints indicate the possible locations for joints in the curve. The index is an index into the sample sequence so, for example, samples[joints[0].index] is the sample value for the first possible joint in the curve. If forced=TRUE a joint will always occure at that point.
There must be at least one joint indicated for closed data and two (at the ends) for open data. The tangents sequence must be twice the length of the nodes sequence as there are two tangents per joint; tanIn and tanOut. To make a smooth joint tanIn must equal tanOut. The tangent value is a unit vector and [0,0] is a free (unset) tangent.
Default:
PROC [data: Data];
Pass this a data record with only the samples and closed fields filled in and this will default your joints and tangents values. Fitting routines should signal Error if the data is badly formed but they may just raise BoundsFault or AddressFault.
Error: SIGNAL [why: Rope.ROPE];
Metrics:
TYPE = LSPiece.Metrics;
Metrics: TYPE = REF MetricRec;
MetricRec: TYPE = RECORD [
maxItr: INT ← 500, -- limit on number of iterations
maxDev: REAL ← .00001, --stop iterating if the maximum deviation gets below this amount
sumErr: REAL ← .00001, -- stop iterating if the sum of squares gets below this amount
deltaT: REAL ← 0.000005 -- stop when the t values each change by less than this
];
The iteration is stopped when either (1) sum of squares <= data.sumErr, (2) sumErr has increased over the previous iteration, (3) the largest change in a t value is less than data.deltaT, or (4) iterations >= maxItr. The curve is not guaranteed to fit within all the metrics, only the first one to get small enough.
CubicProc:
TYPE =
PROC[bezier: Cubic.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, outputCubic: CubicProc];
Makes every node a joint.
GrowSpline:
PROC [data: Data, metrics: Metrics, outputCubic: CubicProc, hilight: CubicProc ←
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, outputCubic: CubicProc, hilight: CubicProc ←
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, outputCubic: CubicProc];
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.
}.