DIRECTORY Seq USING [JointSequence, ComplexSequence], Complex USING [VEC], Rope USING [ROPE], LSPiece USING [Metrics], Cubic2 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 ]; Default: PROC [data: Data]; Error: SIGNAL [why: Rope.ROPE]; Metrics: TYPE = LSPiece.Metrics; Cubic2Proc: TYPE = PROC[bezier: Cubic2.Bezier, sumErr, maxDev: REAL, iterations: INT] RETURNS[quit: BOOLEAN _ FALSE]; FitSpline: PROC [data: Data, metrics: Metrics, outputCubic2: Cubic2Proc]; GrowSpline: PROC [data: Data, metrics: Metrics, outputCubic2: Cubic2Proc, hilight: Cubic2Proc _ NIL]; DynSpline: PROC [data: Data, metrics: Metrics, penalty: REAL, trim: BOOLEAN _ TRUE, outputCubic2: Cubic2Proc, hilight: Cubic2Proc _ NIL]; FitPiece: PROC [data: Data, from, thru: NAT, initFree, finalFree: BOOLEAN _ TRUE, metrics: Metrics, outputCubic2: Cubic2Proc]; TangentProc: TYPE = PROC[data: Data, at: NAT] RETURNS[Complex.VEC]; --at is the index of the point where the tangent is needed ie. data.samples[at]; AdaptiveFit: PROC [data: Data, from, thru: NAT, initFree, finalFree: BOOLEAN _ TRUE, metrics: Metrics, outputCubic2: Cubic2Proc, tangent: TangentProc]; }. `PiecewiseFit.mesa Copyright c 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 Maureen Stone, September 24, 1987 11:23:40 am PDT Public Interface to the piecewise cubic fitting routines 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. 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. Metrics: TYPE = REF MetricRec; MetricRec: TYPE = RECORD [ maxItr: INT _ 10, -- 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. 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. Makes every node a joint. 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. 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. 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. Ignores joint information and adaptively subdivides the samples, placing joints at the points of maximum deviation. 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. Κy˜codešœ™Kšœ Οmœ7™BKšœ*™*Kšœ>™>K™,K™1—K˜Kšœ8™8K™šΟk ˜ Kšœžœ"˜+Kšœžœžœ˜Kšœžœžœ˜Kšœžœ ˜Kšœžœ ˜—K˜KšΠbl œžœž œ˜#K˜Kšœžœžœ ˜šœ žœžœ˜Kšœ˜Kšœžœ˜KšœΟc˜:Kšœ &˜DK˜—K™[K™–K™ΦšΟnœžœ˜K™χK™—Kšœžœ žœ˜K™šœ žœ˜ Kšœ žœžœ ™šœ žœžœ™Kšœžœ  ™2Kšœžœ @™WKšœžœ  >™UKšœžœ  7™OK™—Kšœ) œ…™Ό—K˜š‘ œžœžœ(žœžœžœžœžœ˜uKšœΌ™Ό—š‘ œžœ:˜IK™—š‘ œžœPžœ˜eK™Κ—š ‘ œžœ)žœžœ2žœ˜‰K™€—K˜š ‘œžœžœžœžœ.˜~K™Λ—Kš œ žœžœžœžœ žœ P˜”š ‘ œžœžœžœžœD˜—K™ύ—K˜K˜—…—Z3