DIRECTORY
Complex,
Cubic,
DynFit,
LSPiece,
FitState,
FitBasic USING [SampleHandle],
Highlight USING [ShowPt, Context, CleanUp],
FitStateUtils,
Seq USING [ComplexSequence, ComplexSequenceRec, RealSequence, RealSequenceRec, JointSequence, BooleanSequence, BooleanSequenceRec],
Vector,
Real USING [RoundLI],
SampledCurves,
PotentialKnots,
RealFns USING [SqRt, AlmostZero, CosDeg];

PotentialKnotsImpl: CEDAR PROGRAM IMPORTS Complex, Cubic, DynFit, LSPiece, Vector, RealFns, FitStateUtils, FitState, Highlight, Real, SampledCurves
EXPORTS PotentialKnots =
BEGIN OPEN PotentialKnots;

SampledCurve: TYPE = SampledCurves.SampledCurve;
FindCorners: PUBLIC PROC [state: FitState.Handle, minK: REAL, forceKnot: BOOLEAN _ FALSE] = {
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] = {
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;
};
UNTIL index = infl.length DO
ft, lt: NAT;
UNTIL index = infl.length DO IF infl[index] THEN EXIT ELSE index _ index+1; ENDLOOP;
ft _ index;
UNTIL index = infl.length DO
IF NOT infl[index] THEN EXIT
ELSE index _ index+1; ENDLOOP;
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] = {
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 _ NIL;
};
};
index _ index+1;
};
isFlat: SampledCurves.ConditionProc = {
IF highlight#NIL THEN Highlight.ShowPt[highlight, point.p];
RETURN[ABS[point.k] <= tol];
};
DO
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]];
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;
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] = {
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 = {
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];
};
lastTime: BOOLEAN _ FALSE;
DO
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] = {
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] = {
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;
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];
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;
tans[t+1] _ cDir;
};
};
oDir _ cDir;
ENDLOOP;
FitStateUtils.ForAllSamples[state.slist, set];
};

CubicTangents: PUBLIC PROC [state: FitState.Handle, metrics: LSPiece.Metrics, progress: Progress _ NIL] = {
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: Cubic.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: Cubic.Bezier, t: REAL] RETURNS [tang: Complex.Vec] = {
c: Cubic.Coeffs _ Cubic.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] = {
DiffTangents[state, maxAngle, FALSE, CircleTan];
};

QuickTangents: PUBLIC PROC [state: FitState.Handle, maxAngle: REAL, setCorners: BOOLEAN _ FALSE] = {
DiffTangents[state, maxAngle, setCorners, CheapTangent];
};

SquareTangents: PUBLIC PROC [state: FitState.Handle, maxAngle: REAL, setCorners: BOOLEAN _ FALSE] = {
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;
 DO
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;
 DO
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
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] = {
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;
DO 
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;
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] = {
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] = {
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] = {
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_forced;
};
FitStateUtils.ForAllSamples[state.slist, do];
};
QuickPoly: PUBLIC PROC [state: FitState.Handle, highlight: Highlight.Context _ NIL] = {
lpk: FitBasic.SampleHandle;
wrap: BOOLEAN _ FALSE;
first: BOOLEAN _ TRUE;
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.RoundLI[dx/max]+3*Real.RoundLI[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.



ÄPotentialKnotsImpl.mesa
last edited by Maureen Stone December 17, 1984 3:59:09 pm PST
last edited by Michael Plass  August 30, 1982 2:06 pm
These routines use SampledCurves to find the tangents and curvature at each point.  They then build a sequence of booleans to mark the joints. 
Takes local curvatures.  Defines as a corner any value with K>=minK. 
Takes local curvatures.  Looks for zero crossings.
now reduce sequences of zero crossings
now index is the first TRUE value
now index is the first FALSE value (filtering out changebind fit
s that are too close)
Takes local curvatures.  Looks for flat spots crossings.
start.tanOut _ sc[startIndex].t;
s.tanIn _ sc[index].t;
Test for horizontal or vertical.  If so, set each end
see if "line" extends to next samples
Takes local curvatures.  Looks for horizontal and vertical lines within tol.  defines combination of hline sample vline as a 90 degree corner.
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.  
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
Takes local curvatures.  Mark as a potential knot any place the change in curvature is greater than minDK.  Set tangents using QuickTangent algorithm 
finds nodes by fitting a polygon using DynFit.  Forces joints at lines > lineLength
sn is the sample number, ep is the next index into endpoints
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.
Progress: PROC[tangent: Complex.Vec, cubic: Cubic.Bezier] RETURNS [stop: BOOLEAN];
Sets tangents at joints by fitting a cubic between neighboring joints
computes tangents at node points by finding a circle through 3 adjacent nodes.  Ignore joints where angle between neighbors is greater than maxAngle.
computes tangents by differencing neighbors
computes tangents by differencing neighbors
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.
Finds the horizontal and vertical extremes in a set of samples and puts a joint and tangent there. 
now find the range of samples with min and max values.  Put joints in centers of each range
Run this after setting the tangents to "true" the nearly horizontal and vertical tangents. tol=angle.
Run this to make nearly equal left and right tangents the same. tol=angle.  Split the difference.
Run this to force joints on potential knots whose tangents differ by angle.
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.
3*dy+dx is an id for the direction.  runs [-4..4] for dx, dy in [-1..1];  
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];
};
�ʽ˜J˜Jš
œ™Jš
œ=™=Jš
œ5™5J˜š
Ïk	˜	Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜J˜	Jšœ	�œ˜Jšœ
�œ˜+J˜Jšœ�œz˜ƒ
Jš
œ˜Jšœ�œ˜J˜Jš
œ˜Jšœ�œ˜)—J˜Jšœ�œ
�œ
�œj˜“
Jš�œ˜Jš�œ�
˜J˜J™�
Jšœ�œ˜0•StartOfExpansion[]šÏnœ�œ
�œ �œ
�œ�œ˜]Jš
ÏcE™EJš
œ>˜>Jš
œP˜PJšœ�œ˜˜!Jš�œ
�œ�œ�œ�œ�œ˜WJ˜J˜—J˜.J˜—š
žœ�œ �œ
�œ�œ˜aJš
Ÿ2™2Jš
œ>˜>Jš
œP˜PJšœ�œ$˜CJšœ�œ˜˜!Jš
�œ
�œ�œ�œ�œ˜JJ˜J˜—š�œ�œ
�œ�˜#Jš
�œ�œ
�œ
�œ�œ
˜BJš�œ
˜—š�œ�œ˜Jšœ�œ˜Jšœ
�œ�œ
�œ�œ
�œ
�œ
�œ
˜NJšœ
�œ�œ
�œ�œ
�œ
�œ
�œ
˜TJ˜—J™&š�œ�˜Jšœ�œ
˜Jš�œ�œ
�œ
�œ
�œ
�œ�œ
˜TJ™!Jš
œ˜š�œ�˜Jš�œ
�œ
�œ
�˜Jš�œ�œ
˜—J™VJš
œ˜š�œ
�œŸ>˜Qš�œ�œ
�œ
�œ
˜Jšœ
�œ�œ
˜—Jšœ�œ
˜J˜—Jš�œ
˜—J˜
J˜.J˜—šžœ�œ%�œ
�œ�œ!�œ˜‚
Jš
Ÿ8™8Jš
œ>˜>Jš
œP˜PJšœ�œ$˜DJšœ�œ
˜#Jšœ�œ˜˜!š�œ�œ˜Jš�œ�œ
�œ ˜1š�œŸ˜%Jšœ �œ�œ�œ˜HJ™ J™Jšœ�œ
˜J˜—J˜—J˜J˜—š
œ'˜'Jš�œ�œ
�œ&˜;Jš�œ
�œ˜Jš
œ˜—š
�˜Jšœ�œ
˜
J˜Jšœ�œ
˜JšœP�œ˜VJ˜J˜0š�œ�œ˜Jšœ�œ	�œ	˜Jšœ	Ÿ
œŸœ™5Jš�œ�œ�œ�œ
˜>J˜—Jš�œ�œ
�œ
˜Jš�œ
˜—J˜
J˜.J˜J˜—šÏb	œ�œ*�œ�œ�œ
�œ˜xJšœ�œ
˜J™%Jš
œ"˜"Jš
œ ˜ Jš
œ$˜$Jš
œ%˜%Jš
œ3˜3Jš�œ4�œ
˜GJš�œ2�œ˜CJš
œ.˜.J˜J˜—šžœ�œ%�œ
�œ�œ!�œ˜�
Jš
ŸŽ
™Ž
Jš
œ>˜>Jš
œP˜PJšœ �œ$˜GJš�œ�œ˜Jšœ�œ˜Jšœ	�œ˜Jšœ�œ˜Jšœ�œ�œ
˜˜!J™JJ™Tš�œ�œ˜JšœŸ˜4J˜š�œ@�œŸ
˜VJ˜J˜J˜—Jšœ�œ�œ�œ˜6J˜—J˜J˜—š
œ'˜'Jš�œ�œ
�œ&˜;Jš�œ
�œ˜Jš
œ˜—J™1J™DJ™8Jšœ
�œ�œ
˜š
�˜Jšœ�œ
˜
Jšœ�œ
˜J˜Jšœ�œ˜Jšœ
�œ
˜JšœP�œ˜VJ˜0š�œ�œ˜Jšœ�œ	�œ	˜Jš
œ�œ�œ�œ
�œ�œ�œ˜Cš�œ˜
Jš�œ
�œ�œ�œ˜@Jš�œ�œŸ
˜'—J˜J˜—Jš�œ
�œ
�œ
˜J˜
JšœŸ˜%Jš�œ�œ�œŸ˜?Jš�œ
˜—J˜
J˜.J˜J˜—š
žœ�œ!�œ
�œ�œ˜^Jš
Ÿ–
™–
Jš
œ>˜>Jš
œP˜PJšœ�œ!˜;Jšœ�œ˜˜!š�œ
�œ�œ˜ Jšœ�œ�œ�œ˜7Jš�œ�œ˜-Jš�œ�œ˜/J˜—J˜J˜—J˜.J˜—J˜šžœ�œ9�œ˜VJš
ŸS™SJš
œ>˜>Jšœ�
œ˜,Jš
œJ˜JJšœ�œ$˜CJ˜Jš
œ˜Jšœ�œ˜J™<˜!š�œ�˜š�œ�œ˜š�œ
�œ˜Jš
œ˜J˜J˜J˜
—Jš�œ˜J˜—J˜
Jš	�œ�œ
�œ
�œŸ˜1J˜—J˜
J˜—Jš
œ˜J˜EJ™UJ™’
Jšœ
�œ�œ�œ˜BJšœ�œ$˜.š	�œ�œ
�œ�œ
Ÿ˜3š	œ�œ�œ�œ�œ˜*Jš�œ�œ�œ
�œ˜(š�œ�œ˜Jšœ
�œ	˜Jš�œ�œ˜—Jš�œ�œ�œ�œ˜*J˜—J˜Jšœ�œŸ˜=Jšœ�œŸ ˜>š�œ5�œ˜=Jšœ�œ
˜J˜4Jšœ�œ-˜8š�œ�œ�œ˜*Jšœ�œŸ˜1Jšœ
�œ
˜J˜J˜J˜—J˜—J˜Jš�œ
˜—J˜.J˜J˜—Jšžœ�œ,�œ�œ™Ršž
œ�œF�œ˜kJš
ŸE™EJš
œ˜J˜Jš
œ>˜>Jšœ�
œ˜,Jšœ�œ˜Jšœ�œ˜2J˜J˜š	œ�œ	�œ�œ�œ˜)Jš�œ�œ
�œ
�œ	�œ�œ	˜CJš�œ
�œ˜J˜—š	œ�œ	�œ�œ�œ˜)Jš�œ�œ
�œ
�œ�œ�œ	˜CJš�œ
�œ˜J˜—š	œ�œ�œ�œ�œ˜5Jš�œ�œ	�œ
�œ˜;Jš�œ
�œ˜J˜—Jš
œ2˜2š�œ�œ
�œ�˜#Jšœ�œ˜Jšœ�œ˜Jšœ�œ˜J˜Jšœ	�œ˜"Jšœ�œ
˜š�œ�˜Jš
œF˜F—š�œ˜˜MJ˜;—Jšœ
�œ�œ�œ˜NJ˜—Jš�œ
�œ
�œ
�œ�œ
�œ
˜?Jšœ�œ�œ
�œ˜DJšœ	�œ�œ
�œ˜IJšœ)�œ�œ�œ˜iJš�œ
˜—J˜J˜—Jšœ
�œ�œ
˜Jšœ�œ˜Jšœ�œ˜J˜š	ž
œ�œ�œ�œ�˜NJ˜*J˜*J˜*Jš�
œ
˜J˜—šžœ�œ$�œ˜HJšŸŒ
œŸ
™•
Jšœ�œ
˜0J˜J˜—š
ž
œ�œ$�œ�œ�œ˜dJš
Ÿ+™+Jš
œ8˜8J˜—J˜š
žœ�œ$�œ�œ�œ˜eJš
Ÿ+™+Jš
œ9˜9J˜—J˜Jš
žœ�œ�œ!�œ�œ˜XJšœ
�œ�œ
˜,šžœ�œ$�œ�œ˜nJšœ�œ�œ
˜Jš
œ˜šœ�œ!�œ˜QJ˜"šœ
�˜Jš
œ7˜7Jš�œ�œ
�œ
˜Jš�œ
˜—Jš�œ˜
J˜—šœ�œ"�œ˜RJ˜"šœ
�˜Jš
œ7˜7Jš�œ�œ
�œ
˜Jš�œ
˜—Jš�œ˜
J˜—˜ Jšœ	�œ�œ
˜Jš�œ�œ
�œ
˜ š�œ�œ˜Jšœ7�œ�œ˜KJšœ�œ
˜J˜—Jšœ7�œ�œ˜Kšœ	�œ	�œ�œ7˜[Jš�œ�œ�œ�	œ˜H—Jš�œ�œ˜#Jš�œ�œ˜%Jš
œ˜J˜—J˜-J˜J˜—šž
œ�œ!�œ�œ˜XJšœ�œ
˜J˜J˜J˜J˜Jšœ�œ)˜4Jš�œ�œ
�œ8˜WJš�œ
�œ	˜J˜J˜—š œ�œ"�œ�œ˜VJ˜Jšœ*Ÿ'˜QJš
œ$˜$J˜J˜—šž
œ�œ"�œ�œ˜WJ˜Jš
œ*˜*Jš
œ^˜^J˜J˜—šž	œ�œ"�œ�œ˜SJ˜Jšœ�œ
˜J˜ Jšœ)Ÿ'˜PJ™\J™MJ™%J˜&J˜&J˜J˜J˜š�œ�œŸ˜?J˜"J˜
—š�œ˜J˜J˜J˜J˜J˜5J˜—J˜J˜—šžœ�œ/Ÿ˜\Jšœ�œ˜Jš
œ˜Jšœ�˜Jšœ�œ˜š
œ ˜ š�œ
�œ�œ
�œ˜6š�œ0�˜9Jš
œ"˜"Jš
œ˜——J˜J˜—Jšœ�œ
˜Jš
œ,˜,Jš�œ�œ
�œ$˜5J˜J˜—š
ž
œ�œ
�œ%�œ�œ˜PJš
Ÿc™cJšœ�œ�œ
�œ˜Jšœ�œ�œ
�œ˜%Jš
œ8˜8Jšœ�œ˜Jš	œ�œ
�œ�œ�œ˜AJšœ	�œ
�œ
�œ˜š	œ�œ�œ
�œ
�œ˜'Jš�œ
�œ�œ�œ	˜7—Jšœ�œ˜šœ
�œ�œ˜4Jš	œ�œ�œ
�œ	�œ˜:Jšœ�œ˜š�œ�œ�œ
˜Jšœ�œ�œ�œ˜P—š�œ˜Jšœ�œ
˜šœ
�œ
�œ˜ Jš
œO˜O—J˜—J˜—Jš	œ
�œ�œ�œ
�œ˜8Jšœ�œ˜#Jšœ�œ˜#Jš	œ
�œ�œ�œ�œ˜7Jšœ�œ	˜$Jšœ�œ	˜$šœ�œ�œ<˜QJšœ	�œ˜Jšœ�œ
˜Jšœ�œ˜
š�œ
˜Jš�œ�œ�œŸ ˜SJš�œ�œ�œŸ˜EJš
�œ
�œ�œ
�œ	�œ
�œŸ˜QJš
œ˜Jš�œ�œ�œŸ˜JJšœ%Ÿ˜?Jš
œ�œ�œ�œ�œŸ˜MJš
œ˜Jš�œ
˜—J˜—š�œ�œ
�œ�˜Jš�œ
�œ˜"Jš�œ
�œ˜"Jš�œ
�œ˜"Jš�œ
�œ˜"Jš�œ
˜—J™[Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜š	�œ�œ �œ�œ
�˜FJšœ�œ˜J˜4š
œ˜Jš
œ˜Jš
œ˜Jšœ�œ�œ�œ˜/Jš
œ˜—Jš�œ
˜—J˜—šž
œ�œ
�œ�œ
�œ�œ˜[Jš
Ÿe™e˜ Jšœ�œ�œ
˜šœ�œ�œ˜;Jšœ�œ�œ*˜;Jš�œ
�œ�˜Jš�œ�œ�œ˜CJš�œ
˜Jš�œ˜J˜—Jš
�œ�œ�œ�œ
�œ
˜EJšœ#Ÿ˜?Jš
œ"˜"Jš
œ$˜$Jš
œ$˜$Jš�œ�œ�œ˜/J˜—J˜-J˜—šžœ�œ
�œ�œ˜@Jš
Ÿa™a˜ š�œ�œ�œ�œ˜?Jšœ�œ�œ3˜DJš�œ�œK˜\J˜—J˜—J˜-J˜—šžœ�œ
�œ!�œ˜CJš
ŸK™KJšœ�œ˜"˜ Jšœ�œ
˜Jš
�œ�œ�œ�œ
�œ
˜DJš
œ5˜5Jš�œ
�œ�œ˜*J˜—J˜-J˜—šž	œ�œ
�œ9�œ˜WJš
Ÿò
™ò
J˜Jšœ�œ�œ
˜Jšœ�œ�œ
˜Jš
œJ™JJšœ�œŸ˜>˜ š�œ�œ˜Jšœ�œ
˜Jš
œ˜Jš�œ�œ
�œ%˜:Jš�œ
�œ�œ˜2—š�œ˜Jšœ�œ˜ Jšœ�œ˜Jš	œ�œ�œ
�œ�œ˜!Jš�œ�œ
�œ
˜4Jš
œ6˜6š�œ�œ�œŸ˜IJš
œ˜J˜
Jš�œ�œ
�œ%˜:Jš�œ�œ�œ�œ˜?Jš�œ�œ
�œ
�œ˜Jš
œ˜—Jš�œ
�œ
˜J˜—J˜—J˜-Jšœ�œŸ˜(J˜-Jš�œ�œ
�œ˜3J˜—Jš�œ
˜J˜šž
œ�œ
�œ�œ
�œ�œ™[Jš
Ÿe™eJšœ
�œ™%JšœŸ™%™ Jšœ�œ�œ
™Jš�œ�œ
�œ
™ Jšœ�œ�œŸ)™NJš�œ�œ�œ�œ™GJš�œ�œ�œ�œ™GJšœ�œ
�œ™%Jš�œ�œ�œ�œ™HJš�œ�œ�œ�œ™HJš�œ�œ�œ™/J™—J™-J™—J˜J˜—…—I€q