[_CDMiwok_01_]<cedarcommon2.0>Fit>PotentialKnotsImpl.mesa!1

PotentialKnotsImpl.mesa

last edited by Michael Plass August 30, 1982 2:06 pm

last edited by Maureen Stone December 17, 1984 3:59:09 pm PST

Doug Wyatt, September 5, 1985 2:36:52 pm PDT

Bier, July 21, 1987 2:02:28 pm PDT

Maureen Stone, September 30, 1987 6:11:48 pm PDT

DIRECTORY

Complex,

Cubic2,

DynFit,

LSPiece,

FitState,

FitBasic USING [SampleHandle],

Highlight USING [ShowPt, Context, CleanUp],

FitStateUtils,

Seq USING [ComplexSequence, ComplexSequenceRec, RealSequence, RealSequenceRec, JointSequence, BooleanSequence, BooleanSequenceRec],

Vector,

Real USING [Round],

SampledCurves,

PotentialKnots,

RealFns USING [SqRt, AlmostZero, CosDeg];

PotentialKnotsImpl: CEDAR PROGRAM

IMPORTS Complex, Cubic2, DynFit, LSPiece, Vector, RealFns, FitStateUtils, FitState, Highlight, Real, SampledCurves

EXPORTS PotentialKnots =

BEGIN OPEN PotentialKnots;

These routines use SampledCurves to find the tangents and curvature at each point. They then build a sequence of booleans to mark the joints.

SampledCurve: TYPE = SampledCurves.SampledCurve;

FindCorners: PUBLIC PROC [state: FitState.Handle, minK: REAL, forceKnot: BOOLEAN ← FALSE] = {

Takes local curvatures. Defines as a corner any value with K>=minK.

samples: Seq.ComplexSequence ← FitState.CurrentSamples[state];

sc: SampledCurve ← SampledCurves.SampledCurveFromSamples[samples, state.closed];

index: NAT ← 0;

set: FitStateUtils.SampleProc = {

IF ABS[sc[index].k] >= minK THEN s.jointType ← IF forceKnot THEN forced ELSE potential;

index ← index+1;

};

FitStateUtils.ForAllSamples[state.slist, set];

};

FindInflections: PUBLIC PROC [state: FitState.Handle, flat: REAL, forceKnot: BOOLEAN ← FALSE] = {

Takes local curvatures. Looks for zero crossings.

samples: Seq.ComplexSequence ← FitState.CurrentSamples[state];

sc: SampledCurve ← SampledCurves.SampledCurveFromSamples[samples, state.closed];

infl: Seq.BooleanSequence ← NEW[Seq.BooleanSequenceRec[sc.length]];

index: NAT ← 0;

set: FitStateUtils.SampleProc = {

IF infl[index] THEN s.jointType ← IF forceKnot THEN forced ELSE potential;

index ← index+1;

};

FOR i: NAT IN (0..infl.length-1) DO

IF sc[i-1].k*sc[i+1].k<0 THEN infl[i] ← TRUE ELSE infl[i] ← FALSE;

ENDLOOP;

IF sc.closed THEN {

last: NAT ← sc.length-1;

infl[0] ← IF sc[last].k*sc[1].k < 0 OR ABS[sc[0].k]<flat THEN TRUE ELSE FALSE;

infl[last] ← IF sc[0].k*sc[last-1].k<0 OR ABS[sc[last].k]<flat THEN TRUE ELSE FALSE;

};

now reduce sequences of zero crossings

UNTIL index = infl.length DO

ft, lt: NAT;

UNTIL index = infl.length DO IF infl[index] THEN EXIT ELSE index ← index+1; ENDLOOP;

now index is the first TRUE value

ft ← index;

UNTIL index = infl.length DO

IF NOT infl[index] THEN EXIT

ELSE index ← index+1; ENDLOOP;

now index is the first FALSE value (filtering out changebind fit
s that are too close)

lt ← index;

IF lt-ft >1 THEN { --we have a sequence of inflections. Set the one in the middle

FOR i: NAT IN [ft..lt] DO

infl[i] ← FALSE; ENDLOOP;

infl[(lt+ft)/2] ← TRUE;

};

ENDLOOP;

index ← 0;

FitStateUtils.ForAllSamples[state.slist, set];

};

HVLines: PUBLIC PROC [state: FitState.Handle, long, tol: REAL, forceKnot: BOOLEAN ← FALSE, highlight: Highlight.Context ← NIL] = {

Takes local curvatures. Looks for flat spots crossings.

samples: Seq.ComplexSequence ← FitState.CurrentSamples[state];

sc: SampledCurve ← SampledCurves.SampledCurveFromSamples[samples, state.closed];

lines: Seq.BooleanSequence ← NEW[Seq.BooleanSequenceRec[sc.length]];

start: FitBasic.SampleHandle ← NIL;

index, startIndex: NAT ← 0;

set: FitStateUtils.SampleProc = {

IF lines[index] THEN {

IF start=NIL THEN {start ← s; startIndex ← index}

ELSE { --found second end of the line

start.jointType ← s.jointType ← IF forceKnot THEN forced ELSE potential;

start.tanOut ← sc[startIndex].t;

s.tanIn ← sc[index].t;

start ← NIL;

};

index ← index+1;

};

isFlat: SampledCurves.ConditionProc = {

IF highlight#NIL THEN Highlight.ShowPt[highlight, point.p];

RETURN[ABS[point.k] <= tol];

};

length: REAL;

dir: Vector.VEC;

ft, lt, from, to: NAT;

[ft, lt] ← SampledCurves.FindSequence[sc, index, isFlat ! SampledCurves.None => EXIT];

index ← lt + 1;

[from, to, length, dir] ← GetLength[sc, ft, lt];

IF length >= long THEN {

dir ← [ABS[dir.x], ABS[dir.y]];

Test for horizontal or vertical. If so, set each end

IF dir=[1,0] OR dir=[0,1] THEN lines[from] ← lines[to] ← TRUE;

};

IF index > sc.length THEN EXIT;

ENDLOOP;

index ← 0;

FitStateUtils.ForAllSamples[state.slist, set];

};

GetLength: PROC [sc: SampledCurves.SampledCurve, ft, lt: NAT] RETURNS [from, to: NAT, length: REAL, dir: Vector.VEC] = {

prev, next: NAT;

see if "line" extends to next samples

from ← SampledCurves.Wrap[sc, ft];

to ← SampledCurves.Wrap[sc, lt];

prev ← SampledCurves.Wrap[sc, ft-1];

next ← SampledCurves.Wrap[sc, lt+1];

dir ← Vector.Unit[Vector.Sub[sc[to].p,sc[from].p]];

IF Vector.Unit[Vector.Sub[sc[from].p,sc[prev].p]]=dir THEN from ← prev;

IF Vector.Unit[Vector.Sub[sc[next].p,sc[to].p]]=dir THEN to ← next;

length ← SampledCurves.ArcLength[sc, from, to]

};

Find90: PUBLIC PROC [state: FitState.Handle, long, tol: REAL, forceKnot: BOOLEAN ← FALSE, highlight: Highlight.Context ← NIL] = {

Takes local curvatures. Looks for horizontal and vertical lines within tol. defines combination of hline sample vline as a 90 degree corner.

samples: Seq.ComplexSequence ← FitState.CurrentSamples[state];

sc: SampledCurve ← SampledCurves.SampledCurveFromSamples[samples, state.closed];

isCorner: Seq.BooleanSequence ← NEW[Seq.BooleanSequenceRec[sc.length]];

HV: TYPE = {none, h, v};

pk: NAT ← 0;

foundHV: HV ← none;

index, startIndex: NAT ← 0;

found: BOOLEAN ← FALSE;

set: FitStateUtils.SampleProc = {

The sc[index].t is tanIn + tanOut; We need to rediscover tanIn and tanOut

We discriminate between the two possibilites by testing the sign of the curvature.

IF isCorner[index] THEN {

s.tanIn ← [sc[index].t.x, 0]; --assume one direction

s.tanOut ← [0, sc[index].t.y];

IF sc[index].k*SampledCurves.DThetaDegrees[s.tanIn, s.tanOut] < 0 THEN { --switch them

s.tanOut ← s.tanIn;

s.tanIn ← [0, sc[index].t.y];

};

s.jointType ← IF forceKnot THEN forced ELSE potential;

};

index ← index+1;

};

isFlat: SampledCurves.ConditionProc = {

IF highlight#NIL THEN Highlight.ShowPt[highlight, point.p];

RETURN[ABS[point.k] <= tol];

};

we now have a sequence of TRUE for each flat spot

A 90 corner is a horizontal sequence followed by a vertical sequence

OR a vertical sequence followed by a horizontal sequence

lastTime: BOOLEAN ← FALSE;

length: REAL;

ft, lt, pk: NAT;

dir: Vector.VEC;

currentHV: HV ← none;

from, to: NAT;

[ft, lt] ← SampledCurves.FindSequence[sc, index, isFlat ! SampledCurves.None => EXIT];

[from, to, length, dir] ← GetLength[sc, ft, lt];

IF length >= long THEN {

dir ← [ABS[dir.x], ABS[dir.y]];

currentHV ← IF dir=[1,0] THEN v ELSE IF dir=[0,1] THEN h ELSE none;

IF pk=from

AND ((foundHV=h AND currentHV=v) OR (foundHV=v AND currentHV=h))

THEN isCorner[pk] ← TRUE; --mark corner

pk ← to;

};

IF lastTime THEN EXIT;

index ← lt+1;

foundHV ← currentHV; --update foundHV

IF index > sc.length THEN lastTime ← TRUE; --need one last loop

ENDLOOP;

index ← 0;

FitStateUtils.ForAllSamples[state.slist, set];

};

FindDeltaKs: PUBLIC PROC [state: FitState.Handle, minDK: REAL, forceKnot: BOOLEAN ← FALSE] = {

Takes local curvatures. Mark as a potential knot any place the change in curvature is greater than minDK. Set tangents using QuickTangent algorithm

samples: Seq.ComplexSequence ← FitState.CurrentSamples[state];

sc: SampledCurve ← SampledCurves.SampledCurveFromSamples[samples, state.closed];

dk: Seq.RealSequence ← NEW[Seq.RealSequenceRec[sc.length]];

index: NAT ← 0;

set: FitStateUtils.SampleProc = {

IF ABS[dk[index]]>= minDK THEN {

s.jointType ← IF forceKnot THEN forced ELSE potential;

IF s.tanIn=[0,0] THEN s.tanIn ← sc[index].t;

IF s.tanOut=[0,0] THEN s.tanOut ← sc[index].t;

};

index ← index+1;

};

FitStateUtils.ForAllSamples[state.slist, set];

};

DynPoly: PUBLIC PROC [state: FitState.Handle, penalty, lineLength, maxAngle: REAL] = {

finds nodes by fitting a polygon using DynFit. Forces joints at lines > lineLength

samples: Seq.ComplexSequence ← FitState.CurrentSamples[state];

closed: BOOLEAN ← FitState.GetClosed[state];

sc: SampledCurve ← SampledCurves.SampledCurveFromSamples[samples, closed];

bool: Seq.BooleanSequence ← NEW[Seq.BooleanSequenceRec[sc.length]];

endpoints: DynFit.Segments;

tans: Seq.ComplexSequence;

sn, ep, njoints: NAT ← 0;

sn is the sample number, ep is the next index into endpoints

set: FitStateUtils.SampleProc = {

IF sn=endpoints[ep] THEN {

IF s.jointType=none THEN {

IF bool[sn] THEN {

s.jointType ← forced;

s.tanIn ← tans[ep];

s.tanOut ← tans[ep+1];

}

ELSE s.jointType ← potential;

};

ep ← ep+1;

IF ep=njoints THEN RETURN[TRUE]; --no more joints

};

sn ← sn+1;

};

oDir: Vector.VEC ← [0,0];

[segments: endpoints] ← DynFit.FitSegments[samples, closed, penalty];

IF the curve is open, endpoints will always contain the first and last sample points.

IF the curve is closed, the last point in endpoints will always be samples.length, indicating that the last line connects back to the first point.

njoints ← IF closed THEN endpoints.length-1 ELSE endpoints.length;

tans ← NEW[Seq.ComplexSequenceRec[2*njoints]];

FOR i: NAT IN [0..njoints] DO --want to wrap around

wrap: PROC[old: INT] RETURNS[new: INT] = {

IF old IN [0..njoints) THEN RETURN[old];

IF closed THEN {

new ← old MOD njoints;

IF new<0 THEN new ← njoints}

ELSE new ← IF new<0 THEN 0 ELSE njoints-1;

};

cDir: Vector.VEC ← [0,0];

from: NAT ← endpoints[wrap[i-1]]; --want to wrap in endpoints

to: NAT ← endpoints[wrap[i]]; --from and to are sample indices

IF SampledCurves.ArcLength[sc, from, to] >= lineLength THEN {

angle: REAL;

cDir ← Vector.Unit[Vector.Sub[sc[to].p,sc[from].p]];

angle ← ABS[SampledCurves.FindAngleDegrees[oDir, cDir]];

IF oDir#[0,0] AND angle >= maxAngle THEN {

t: NAT ← wrap[i-1]; --index into tangent sequence

bool[from] ← TRUE;

tans[t] ← oDir; --mostly we want to leave corner tangents free

tans[t+1] ← cDir;

tans[t] ← [0,0];

tans[t+1] ← [0,0];

};

oDir ← cDir;

ENDLOOP;

FitStateUtils.ForAllSamples[state.slist, set];

};

Progress: PROC[tangent: Complex.VEC, cubic: Cubic2.Bezier] RETURNS [stop: BOOLEAN];

CubicTangents: PUBLIC PROC [state: FitState.Handle, metrics: LSPiece.Metrics, progress: Progress ← NIL] = {

Sets tangents at joints by fitting a cubic between neighboring joints

joints: Seq.JointSequence;

tangents: Seq.ComplexSequence;

samples: Seq.ComplexSequence ← FitState.CurrentSamples[state];

closed: BOOLEAN ← FitState.GetClosed[state];

n: NAT ← samples.length;

t: Seq.RealSequence ← NEW[Seq.RealSequenceRec[n]];

lastTangent: Complex.VEC;

bezier: Cubic2.Bezier;

prev: PROC [index: NAT] RETURNS [NAT] = {

IF closed THEN RETURN[IF index=0 THEN joints.length-1 ELSE index-1]

ELSE RETURN[index];

};

next: PROC [index: NAT] RETURNS [NAT] = {

IF closed THEN RETURN[IF index=joints.length-1 THEN 1 ELSE index+1]

ELSE RETURN[index];

};

pointsBetween: PROC [from, to: NAT] RETURNS [NAT] = {

IF closed AND to<from THEN RETURN[samples.length-from+to-1]

ELSE RETURN[to-from-1];

};

[joints,tangents] ← FitState.CurrentJoints[state];

FOR i: NAT IN [0..joints.length) DO

p: NAT ← joints[prev[i]].index;

q: NAT ← joints[i].index;

r: NAT ← joints[next[i]].index;

tanIn, tanOut: Complex.VEC;

nPoints: NAT ← pointsBetween[p,r];

e: REAL;

IF nPoints < minPoints THEN

lastTangent ← CheapTangent[samples[p], samples[q], samples[r], maxSin]

ELSE {

[b:bezier, maxDev: e] ← LSPiece.FitPiece[z: samples, t: t, from: p, thru: r,

metrics: metrics, initFree: freeEnds, finalFree: freeEnds];

lastTangent ←IF e > metrics.sumErr THEN [0,0] ELSE TangentVector[bezier,t[q]];

};

IF progress#NIL THEN IF progress[lastTangent,bezier] THEN EXIT;

tanIn ← IF tangents[2*i]=[0,0] THEN lastTangent ELSE tangents[2*i];

tanOut ← IF tangents[2*i+1]=[0,0] THEN lastTangent ELSE tangents[2*i+1];

FitState.SetJoint[state,joints[i].index,(IF joints[i].forced THEN forced ELSE potential), tanIn, tanOut];

ENDLOOP;

};

freeEnds: BOOLEAN ← TRUE;

minPoints: NAT ← 4;

maxSin: REAL ← 0.5;

TangentVector: PROC [b: Cubic2.Bezier, t: REAL] RETURNS [tang: Complex.VEC] = {

c: Cubic2.Coeffs ← Cubic2.BezierToCoeffs[b];

tang.x ← (3*c.c3.x*t+2*c.c2.x)*t + c.c1.x;

tang.y ← (3*c.c3.y*t+2*c.c2.y)*t + c.c1.y;

};

CircleTangents: PUBLIC PROC [state: FitState.Handle, maxAngle: REAL] = {

computes tangents at node points by finding a circle through 3 adjacent nodes. Ignore joints where angle between neighbors is greater than maxAngle.

DiffTangents[state, maxAngle, FALSE, CircleTan];

};

QuickTangents: PUBLIC PROC [state: FitState.Handle, maxAngle: REAL, setCorners: BOOLEAN ← FALSE] = {

computes tangents by differencing neighbors

DiffTangents[state, maxAngle, setCorners, CheapTangent];

};

SquareTangents: PUBLIC PROC [state: FitState.Handle, maxAngle: REAL, setCorners: BOOLEAN ← FALSE] = {

computes tangents by differencing neighbors

DiffTangents[state, maxAngle, setCorners, SquareTangent];

};

TangentProc: TYPE = PROC[a, b, c: Complex.VEC, maxAngle: REAL] RETURNS [t: Complex.VEC];

TooSharp: SIGNAL[d1,d2: Complex.VEC] = CODE;

DiffTangents: PROC [state: FitState.Handle, maxAngle: REAL, setCorners: BOOLEAN, tangentProc: TangentProc] = {

first: BOOLEAN ← TRUE;

next,prev, tI, tO: Complex.VEC;

nextJoint: PROC [sample: FitBasic.SampleHandle] RETURNS[FitBasic.SampleHandle]= {

l: FitBasic.SampleHandle ← sample;

l ← FitStateUtils.NextSa[state.slist, l, state.closed];

IF l.jointType#none THEN EXIT;

ENDLOOP;

RETURN[l];

};

prevJoint: PROC [sample: FitBasic.SampleHandle] RETURNS[FitBasic.SampleHandle]= {

l: FitBasic.SampleHandle ← sample;

l ← FitStateUtils.PrevSa[state.slist, l, state.closed];

IF l.jointType#none THEN EXIT;

ENDLOOP;

RETURN[l];

};

do: FitStateUtils.SampleProc = {

setZero: BOOLEAN ← FALSE;

IF s.jointType=none THEN RETURN;

IF first THEN {

prev ← prevJoint[s ! FitStateUtils.AtEnd => {setZero ← TRUE; CONTINUE}].xy;

first ← FALSE;

};

next ← nextJoint[s ! FitStateUtils.AtEnd => {setZero ← TRUE; CONTINUE}].xy;

tI ← tO ← IF setZero THEN [0,0] ELSE tangentProc[prev, s.xy, next, maxAngle ! TooSharp => {

IF setCorners THEN {tI ← d1; tO ← d2} ELSE tI ← tO ← [0,0]; CONTINUE}];

IF s.tanIn=[0,0] THEN s.tanIn ← tI;

IF s.tanOut=[0,0] THEN s.tanOut ← tO;

prev ← s.xy;

};

FitStateUtils.ForAllSamples[state.slist, do];

};

TestCorner: PROC [a, b, c: Vector.VEC, maxAngle: REAL] RETURNS [in, out: Vector.VEC] = {

angle, magIn, magOut: REAL;

in ← Vector.Sub[b,a];

out ← Vector.Sub[c,b];

magIn ← Vector.Mag[in];

magOut ← Vector.Mag[out];

angle ← ABS[SampledCurves.FindAngleDegrees[in,out]];

IF angle > maxAngle THEN SIGNAL TooSharp[Vector.Div[in, magIn],Vector.Div[out, magOut]]

ELSE RETURN[in,out];

};

CheapTangent: PROC [a, b, c: Complex.VEC, maxAngle: REAL] RETURNS [t: Complex.VEC] = {

in, out: Vector.VEC;

[in,out] ← TestCorner[a, b, c, maxAngle]; --will signal TooSharp if it's a corner

t ← Vector.Unit[Vector.Add[in,out]];

};

SquareTangent: PROC [a, b, c: Complex.VEC, maxAngle: REAL] RETURNS [t: Complex.VEC] = {

in, out: Vector.VEC;

[in,out] ← TestCorner[a, b, c, maxAngle];

t ← Vector.Unit[Vector.Add[Vector.Mul[in, Vector.Mag[in]], Vector.Mul[out, Vector.Mag[out]]]];

};

CircleTan: PROC [a, b, c: Complex.VEC, maxAngle: REAL] RETURNS [t: Complex.VEC] = {

d1, d2: Vector.VEC;

a1,b1,c1,a2,b2,c2,det: REAL;

midAB,midBC,center: Complex.VEC;

[d1,d2] ← TestCorner[a, b, c, maxAngle]; --will signal TooSharp if it's a corner

The center of the circle is the intersection of the two perpendicular bisectors of d1 and d2

ax+by = c is a line. Find two lines, use Cramer's rule to find intersection.

Normal to b-center is tangent vector.

midAB ← Vector.Div[Vector.Add[a,b],2];

midBC ← Vector.Div[Vector.Add[b,c],2];

a1 ← - d1.x; b1 ← - d1.y;

a2 ← - d2.x; b2 ← - d2.y;

det ← a1*b2-a2*b1;

IF RealFns.AlmostZero[det, -100] THEN { --3 pts nearly colinear

t ← Vector.Unit[Complex.Sub[c,a]];

}

ELSE {

c1 ← a1*midAB.x+b1*midAB.y;

c2 ← a2*midBC.x+b2*midBC.y;

center.x ← (c1*b2-c2*b1)/det;

center.y ← (c2*a1-c1*a2)/det;

t ← Vector.Unit[Vector.Normal[Vector.Sub[b,center]]];

};

SelectSample: PROC [state: FitState.Handle, z: Complex.VEC] = { --should be in FitStateImpl

closest,d: REAL ← 10.0E+30;

found: FitBasic.SampleHandle;

index: NAT;

i: NAT ← 0;

do: FitStateUtils.SampleProc = {

IF ABS[s.xy.x-z.x]<closest AND ABS[s.xy.y-z.y]<closest

AND (d ← Vector.Mag[Vector.Sub[z,s.xy]]) < closest THEN {

closest ← d; found ← s; index ← i;

};

i ← i+1;

};

found ← NIL;

FitStateUtils.ForAllSamples[state.slist,do];

IF found#NIL THEN state.slist.selectedSample ← found;

};

HVExtremes: PUBLIC PROC [state: FitState.Handle, forceKnot: BOOLEAN ← FALSE] = {

Finds the horizontal and vertical extremes in a set of samples and puts a joint and tangent there.

minX,minY: REAL ← LAST[INT]/2;

maxX,maxY: REAL ← - (LAST[INT]/2 -1);

s: Seq.ComplexSequence ← FitState.CurrentSamples[state];

length: INT ← s.length;

addSample: TYPE=RECORD[index: INT, x, y: REAL, tan: Complex.VEC];

addList: LIST OF REF addSample;

wrap: PROC[index: INT] RETURNS[INT] = {

RETURN[IF index>=length THEN index-length ELSE index]};

i: INT ← 0;

addJoint: PROC [from, to: INT, tan: Complex.VEC] = {

range: INT ← IF to>=from THEN from+to ELSE from+to+length;

k: INT ← wrap[range/2];

IF range MOD 2 = 0 THEN

FitState.SetJoint[state, k, (IF forceKnot THEN forced ELSE potential), tan, tan]

ELSE {

l: INT ← wrap[k+1];

addList ← CONS[NEW[addSample ← [

index: l, x: (s[k].x+s[l].x)/2.0, y: (s[k].y+s[l].y)/2.0, tan: tan]], addList];

};

ExtractProc: TYPE = PROC [v: Complex.VEC] RETURNS[REAL];

xProc: ExtractProc = {RETURN[v.x]};

yProc: ExtractProc = {RETURN[v.y]};

TangentProc: TYPE = PROC[d: REAL] RETURNS[Complex.VEC];

hTan: TangentProc = {RETURN[[d,0]]};

vTan: TangentProc = {RETURN[[0,d]]};

loop: PROC [val: REAL, compare, direction: ExtractProc, tangent: TangentProc] = {

j,first: INT ← -1;

d: REAL;

i: INT← 0;

UNTIL compare[s[i]]#val DO i ← wrap[i+1]; ENDLOOP; --worry about wrap around values

UNTIL compare[s[i]]=val DO i ← wrap[i+1]; ENDLOOP; --find first value

IF first=-1 THEN first ← i ELSE IF first=i THEN EXIT; --want to find all extremes

j ← i;

UNTIL compare[s[wrap[j+1]]]#val DO j ← wrap[j+1]; ENDLOOP; --find last one

d ← direction[s[j]]-direction[s[i]]; --get the direction right

d ← IF RealFns.AlmostZero[d,-10] THEN 0 ELSE d/ABS[d]; --normalize unless d=0

addJoint[i,j,tangent[d]];

ENDLOOP;

};

FOR i: INT IN [0..s.length) DO

IF s[i].x>maxX THEN maxX ← s[i].x;

IF s[i].y>maxY THEN maxY ← s[i].y;

IF s[i].x<minX THEN minX ← s[i].x;

IF s[i].y<minY THEN minY ← s[i].y;

ENDLOOP;

now find the range of samples with min and max values. Put joints in centers of each range

loop[minX, xProc, yProc, vTan];

loop[maxX, xProc, yProc, vTan];

loop[minY, yProc, xProc, hTan];

loop[maxY, yProc, xProc, hTan];

FOR head: LIST OF REF addSample ← addList, head.rest UNTIL head=NIL DO

as: REF addSample ← head.first;

SelectSample[state, [s[as.index].x, s[as.index].y]];

FitState.InsertBeforeSample[

handle: state,

x: as.x, y: as.y,

joint: IF forceKnot THEN forced ELSE potential,

tanIn: as.tan, tanOut: as.tan];

ENDLOOP;

};

HVTangents: PUBLIC PROC [state: FitState.Handle, tol: REAL, forceKnot: BOOLEAN ← FALSE] = {

Run this after setting the tangents to "true" the nearly horizontal and vertical tangents. tol=angle.

do: FitStateUtils.SampleProc = {

set: BOOLEAN ← FALSE;

getNew: PROC [old,new: Vector.VEC] RETURNS [Vector.VEC] = {

angle: REAL ← ABS[SampledCurves.FindAngleDegrees[old,new]];

IF angle < tol THEN set ← TRUE

ELSE IF (180-angle) < tol THEN {set ← TRUE; new ← [-new.x, -new.y]}

ELSE new ← old;

RETURN[new];

};

IF s.jointType=none OR s.tanIn= [0,0] OR s.tanOut=[0,0] THEN RETURN;

s.tanIn ← getNew[s.tanIn, [1,0]]; --does both [1,0] and [-1,0]

s.tanIn ← getNew[s.tanIn, [0,1]];

s.tanOut ← getNew[s.tanOut, [1,0]];

s.tanOut ← getNew[s.tanOut, [0,1]];

IF set AND forceKnot THEN s.jointType ← forced;

};

FitStateUtils.ForAllSamples[state.slist, do];

};

NearlyEqual: PUBLIC PROC [state: FitState.Handle, tol: REAL] = {

Run this to make nearly equal left and right tangents the same. tol=angle. Split the difference.

do: FitStateUtils.SampleProc = {

IF s.jointType#none AND s.tanIn#[0,0] AND s.tanOut#[0,0] THEN {

angle: REAL ← ABS[SampledCurves.FindAngleDegrees[s.tanIn,s.tanOut]];

IF angle<tol THEN s.tanIn ← s.tanOut ← [(s.tanIn.x+s.tanOut.x)/2, (s.tanIn.y+s.tanOut.y)/2];

};

FitStateUtils.ForAllSamples[state.slist, do];

};

ForceCorners: PUBLIC PROC [state: FitState.Handle, angle: REAL] = {

Run this to force joints on potential knots whose tangents differ by angle.

cos: REAL ← RealFns.CosDeg[angle];

do: FitStateUtils.SampleProc = {

a: REAL;

IF s.jointType=none OR s.tanIn= [0,0] OR s.tanOut=[0,0] THEN RETURN;

a ← SampledCurves.FindAngleDegrees[s.tanIn,s.tanOut];

IF ABS[a] > angle THEN s.jointType𡤏orced;

};

FitStateUtils.ForAllSamples[state.slist, do];

};

QuickPoly: PUBLIC PROC [state: FitState.Handle, highlight: Highlight.Context ← NIL] = {

tests the lines between joints for horizontal or vertical within tol=dmin/dmax. Puts joints with horizontal or vertical tangents at the end of each line. ForceKnot sets the "corner" bit to force a knot but sets both tangents to be the same.

lpk: FitBasic.SampleHandle;

wrap: BOOLEAN ← FALSE;

first: BOOLEAN ← TRUE;

3*dy+dx is an id for the direction. runs [-4..4] for dx, dy in [-1..1];

evenDir, oddDir,newDir: INT ← 10; --impossible number for init

do: FitStateUtils.SampleProc = {

IF first THEN {

first ← FALSE;

lpk ← s;

IF highlight#NIL THEN Highlight.ShowPt[highlight, lpk.xy];

IF NOT state.closed THEN s.jointType ← potential;}

ELSE {

dx: REAL ← s.xy.x - s.prev.xy.x;

dy: REAL ← s.xy.y-s.prev.xy.y;

max: REAL ← MAX[ABS[dx],ABS[dy]];

IF RealFns.AlmostZero[max, -100] THEN GOTO tooSmall;

newDir ← Real.Round[dx/max]+3*Real.Round[dy/max];

IF newDir#evenDir AND newDir#oddDir THEN { --found a change in direction

lpk.jointType ← potential;

lpk ← s.prev;

IF highlight#NIL THEN Highlight.ShowPt[highlight, lpk.xy];

IF newDir MOD 2 = 0 THEN evenDir ← newDir ELSE oddDir ← newDir;

IF wrap THEN RETURN[TRUE];

};

EXITS tooSmall => NULL;

};

FitStateUtils.ForAllSamples[state.slist, do];

wrap ← TRUE; --we're now wrapping around

FitStateUtils.ForAllSamples[state.slist, do];

IF highlight#NIL THEN Highlight.CleanUp[highlight];

};

END.

HVTangents: PUBLIC PROC [state: FitState.Handle, tol: REAL, forceKnot: BOOLEAN ← FALSE] = {

Run this after setting the tangents to "true" the nearly horizontal and vertical tangents. tol=angle.

smallTan: REAL ← RealFns.TanDeg[tol];

t: Complex.VEC; --temporary variable

do: FitStateUtils.SampleProc = {

set: BOOLEAN ← FALSE;

IF s.jointType=none THEN RETURN;

t ← [ABS[s.tanIn.x],ABS[s.tanIn.y]]; --we want positive quantities for compare

IF t.x > t.y AND t.y < t.x*smallTan THEN {set ← TRUE; s.tanIn ← [1,0]};

IF t.y > t.x AND t.x < t.y*smallTan THEN {set ← TRUE; s.tanIn ← [0,1]};

t← [ABS[s.tanOut.x],ABS[s.tanOut.y]];

IF t.x > t.y AND t.y < t.x*smallTan THEN {set ← TRUE; s.tanOut ← [1,0]};

IF t.y > t.x AND t.x < t.y*smallTan THEN {set ← TRUE; s.tanOut ← [0,1]};

IF set AND forceKnot THEN s.jointType ← forced;

};

FitStateUtils.ForAllSamples[state.slist, do];

};