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;

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] _ [0,0];
tans[t+1] _ [0,0];
};
};
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: 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] = {
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.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.



ΤPotentialKnotsImpl.mesa
Copyright c 1985 by Xerox Corporation.  All rights reserved.
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
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.
tans[t] _ oDir;	--mostly we want to leave corner tangents free
tans[t+1] _ cDir;
Progress: PROC[tangent: Complex.VEC, cubic: Cubic2.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];
};
Κ‰˜
codeš
œ™Kšœ
Οm
œ1™<Kš
œ5™5Kš
œ=™=K™,K™"K™0—K˜š
Οk	˜	Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜K˜	Kšœ	žœ˜Kšœ
žœ˜+K˜Kšœžœz˜ƒ
Kš
œ˜Kšœžœ	˜K˜Kš
œ˜Kšœžœ˜)—K˜KšΠblœžœ
ž˜!Kšžœk˜rKšžœ˜Kšžœž
˜K˜K™
Kšœžœ˜0•StartOfExpansion[]šΟnœžœ
žœ žœ
žœžœ˜]Kš
ΟcE™EKš
œ>˜>Kš
œP˜PKšœžœ˜˜!Kšžœ
žœžœžœžœžœ˜WK˜K˜—K˜.K˜—š
 œžœ žœ
žœžœ˜aKš
‘2™2Kš
œ>˜>Kš
œP˜PKšœžœ$˜CKšœžœ˜˜!Kš
žœ
žœžœžœžœ˜JK˜K˜—šžœžœ
žœž˜#Kš
žœžœ
žœ
žœžœ
˜BKšžœ
˜—šžœžœ˜Kšœžœ˜Kšœ
žœžœ
žœžœ
žœ
žœ
žœ
˜NKšœ
žœžœ
žœžœ
žœ
žœ
žœ
˜TK˜—K™&šžœž˜Kšœžœ
˜Kšžœžœ
žœ
žœ
žœ
žœžœ
˜TK™!Kš
œ˜šžœž˜Kšžœ
žœ
žœ
ž˜Kšžœžœ
˜—K™VKš
œ˜šžœ
žœ‘>˜Qšžœžœ
žœ
žœ
˜Kšœ
žœžœ
˜—Kšœžœ
˜K˜—Kšžœ
˜—K˜
K˜.K˜—š œžœ%žœ
žœžœ!žœ˜‚
Kš
‘8™8Kš
œ>˜>Kš
œP˜PKšœžœ$˜DKšœžœ
˜#Kšœžœ˜˜!šžœžœ˜Kšžœžœ
žœ ˜1šžœ‘˜%Kšœ žœžœžœ˜HK™ K™Kšœžœ
˜K˜—K˜—K˜K˜—š
œ'˜'Kšžœžœ
žœ&˜;Kšžœ
žœ˜Kš
œ˜—š
ž˜Kšœžœ
˜
Kšœžœ
˜Kšœžœ
˜KšœPžœ˜VK˜K˜0šžœžœ˜Kšœžœ	žœ	˜Kšœ	‘
œ‘œ™5Kšžœžœžœžœ
˜>K˜—Kšžœžœ
žœ
˜Kšžœ
˜—K˜
K˜.K˜K˜—šΟb	œžœ*žœžœžœ
žœžœ˜xKšœžœ
˜K™%Kš
œ"˜"Kš
œ ˜ Kš
œ$˜$Kš
œ%˜%Kš
œ3˜3Kšžœ4žœ
˜GKšžœ2žœ˜CKš
œ.˜.K˜K˜—š œžœ%žœ
žœžœ!žœ˜
Kš
‘Ž
™Ž
Kš
œ>˜>Kš
œP˜PKšœ žœ$˜GKšžœžœ˜Kšœžœ˜Kšœ	žœ˜Kšœžœ˜Kšœžœžœ
˜˜!K™JK™Tšžœžœ˜Kšœ‘˜4K˜šžœ@žœ‘
˜VK˜K˜K˜—Kšœžœžœžœ˜6K˜—K˜K˜—š
œ'˜'Kšžœžœ
žœ&˜;Kšžœ
žœ˜Kš
œ˜—K™1K™DK™8Kšœ
žœžœ
˜š
ž˜Kšœžœ
˜
Kšœžœ
˜Kšœžœ
˜Kšœžœ˜Kšœ
žœ
˜KšœPžœ˜VK˜0šžœžœ˜Kšœžœ	žœ	˜Kš
œžœžœžœ
žœžœžœ˜Cšžœ˜
Kšžœ
žœžœžœ˜@Kšžœžœ‘
˜'—K˜K˜—Kšžœ
žœ
žœ
˜K˜
Kšœ‘˜%Kšžœžœžœ‘˜?Kšžœ
˜—K˜
K˜.K˜K˜—š
 œžœ!žœ
žœžœ˜^Kš
‘–
™–
Kš
œ>˜>Kš
œP˜PKšœžœ!˜;Kšœžœ˜˜!šžœ
žœžœ˜ Kšœžœžœžœ˜7Kšžœžœ˜-Kšžœžœ˜/K˜—K˜K˜—K˜.K˜—K˜š œžœ9žœ˜VKš
‘S™SKš
œ>˜>Kšœž
œ˜,Kš
œJ˜JKšœžœ$˜CK˜Kš
œ˜Kšœžœ˜K™<˜!šžœž˜šžœžœ˜šžœ
žœ˜Kš
œ˜K˜K˜K˜
—Kšžœ˜K˜—K˜
Kš	žœžœ
žœ
žœ‘˜1K˜—K˜
K˜—Kšœ
žœ	˜K˜EK™UK™’
Kšœ
žœžœžœ˜BKšœžœ$˜.š	žœžœ
žœžœ
‘˜3š	œžœžœžœžœ˜*Kšžœžœžœ
žœ˜(šžœžœ˜Kšœ
žœ	˜Kšžœžœ˜—Kšžœžœžœžœ˜*K˜—Kšœ
žœ	˜Kšœžœ‘˜=Kšœžœ‘ ˜>šžœ5žœ˜=Kšœžœ
˜K˜4Kšœžœ-˜8šžœžœžœ˜*Kšœžœ‘˜1Kšœ
žœ
˜K™>K™K˜K˜K˜—K˜—K˜Kšžœ
˜—K˜.K˜K˜—Kš
 œžœžœžœžœ™Sš 
œžœFžœ˜kKš
‘E™EKš
œ˜K˜Kš
œ>˜>Kšœž
œ˜,Kšœžœ˜Kšœžœ˜2Kšœžœ
˜K˜š	œžœ	žœžœžœ˜)Kšžœžœ
žœ
žœ	žœžœ	˜CKšžœ
žœ˜K˜—š	œžœ	žœžœžœ˜)Kšžœžœ
žœ
žœžœžœ	˜CKšžœ
žœ˜K˜—š	œžœžœžœžœ˜5Kšžœžœ	žœ
žœ˜;Kšžœ
žœ˜K˜—Kš
œ2˜2šžœžœ
žœž˜#Kšœžœ˜Kšœžœ˜Kšœžœ˜Kšœžœ
˜Kšœ	žœ˜"Kšœžœ
˜šžœž˜Kš
œF˜F—šžœ˜˜MK˜;—Kšœ
žœžœžœ˜NK˜—Kšžœ
žœ
žœ
žœžœ
žœ
˜?Kšœžœžœ
žœ˜DKšœ	žœžœ
žœ˜IKšœ)žœžœžœ˜iKšžœ
˜—K˜K˜—Kšœ
žœžœ
˜Kšœžœ˜Kšœžœ˜K˜š 
œžœžœžœžœž˜OK˜,K˜*K˜*Kšž
œ
˜K˜—š œžœ$žœ˜HKš‘Œ
œ‘
™•
Kšœžœ
˜0K˜K˜—š
 
œžœ$žœžœžœ˜dKš
‘+™+Kš
œ8˜8K˜—K˜š
 œžœ$žœžœžœ˜eKš
‘+™+Kš
œ9˜9K˜—K˜Kš œžœžœžœžœžœ
žœ˜XKšœ
žœžœžœ
˜,š œžœ$žœžœ˜nKšœžœžœ
˜Kšœžœ
˜šœžœ!žœ˜QK˜"šœ
ž˜Kš
œ7˜7Kšžœžœ
žœ
˜Kšžœ
˜—Kšžœ˜
K˜—šœžœ"žœ˜RK˜"šœ
ž˜Kš
œ7˜7Kšžœžœ
žœ
˜Kšžœ
˜—Kšžœ˜
K˜—˜ Kšœ	žœžœ
˜Kšžœžœ
žœ
˜ šžœžœ˜Kšœ7žœžœ˜KKšœžœ
˜K˜—Kšœ7žœžœ˜Kšœ	žœ	žœžœ7˜[Kšžœžœžœž	œ˜H—Kšžœžœ˜#Kšžœžœ˜%Kš
œ˜K˜—K˜-K˜K˜—š 
œžœžœžœžœžœ˜XKšœžœ
˜K˜K˜K˜K˜Kšœžœ)˜4Kšžœžœ
žœ8˜WKšžœ
žœ	˜K˜K˜—š’œžœžœžœžœ
žœ˜VKšœžœ
˜Kšœ*‘'˜QKš
œ$˜$K˜K˜—š 
œžœžœžœžœ
žœ˜WKšœžœ
˜Kš
œ*˜*Kš
œ^˜^K˜K˜—š 	œžœžœžœžœ
žœ˜SKšœžœ
˜Kšœžœ
˜Kšœžœ
˜ Kšœ)‘'˜PK™\K™MK™%K˜&K˜&K˜K˜K˜šžœžœ‘˜?K˜"K˜
—šžœ˜K˜K˜K˜K˜K˜5K˜—K˜K˜—š œžœ%žœ‘˜\Kšœžœ˜Kš
œ˜Kšœž˜Kšœžœ˜š
œ ˜ šžœ
žœžœ
žœ˜6šžœ0ž˜9Kš
œ"˜"Kš
œ˜——K˜K˜—Kšœžœ
˜Kš
œ,˜,Kšžœžœ
žœ$˜5K˜K˜—š
 
œžœ
žœ%žœžœ˜PKš
‘c™cKšœžœžœ
žœ˜Kšœžœžœ
žœ˜%Kš
œ8˜8Kšœžœ˜Kšœžœ
žœžœžœžœ˜AKšœ	žœ
žœ
žœ˜š	œžœžœ
žœ
žœ˜'Kšžœ
žœžœžœ	˜7—Kšœžœ˜šœ
žœžœžœ˜4Kš	œžœžœ
žœ	žœ˜:Kšœžœ˜šžœžœžœ
˜Kšœžœžœžœ˜P—šžœ˜Kšœžœ
˜šœ
žœ
žœ˜ Kš
œO˜O—K˜—K˜—Kšœ
žœžœ
žœžœ
žœ˜8Kšœžœ˜#Kšœžœ˜#Kšœ
žœžœžœžœ	žœ˜7Kšœžœ	˜$Kšœžœ	˜$šœžœžœ<˜QKšœ	žœ˜Kšœžœ
˜Kšœžœ˜
šžœ
˜Kšžœžœžœ‘ ˜SKšžœžœžœ‘˜EKš
žœ
žœžœ
žœ	žœ
žœ‘˜QKš
œ˜Kšžœžœžœ‘˜JKšœ%‘˜?Kš
œžœžœžœžœ‘˜MKš
œ˜Kšžœ
˜—K˜—šžœžœ
žœž˜Kšžœ
žœ˜"Kšžœ
žœ˜"Kšžœ
žœ˜"Kšžœ
žœ˜"Kšžœ
˜—K™[Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜š	žœžœ žœžœ
ž˜FKšœžœ˜K˜4š
œ˜Kš
œ˜Kš
œ˜Kšœžœžœžœ˜/Kš
œ˜—Kšžœ
˜—K˜—š 
œžœ
žœžœ
žœžœ˜[Kš
‘e™e˜ Kšœžœžœ
˜š	œžœžœžœ	žœ˜;Kšœžœžœ*˜;Kšžœ
žœž˜Kšžœžœžœ˜CKšžœ
˜Kšžœ˜K˜—Kš
žœžœžœžœ
žœ
˜EKšœ#‘˜?Kš
œ"˜"Kš
œ$˜$Kš
œ$˜$Kšžœžœžœ˜/K˜—K˜-K˜—š œžœ
žœžœ˜@Kš
‘a™a˜ šžœžœžœžœ˜?Kšœžœžœ3˜DKšžœžœK˜\K˜—K˜—K˜-K˜—š œžœ
žœ!žœ˜CKš
‘K™KKšœžœ˜"˜ Kšœžœ
˜Kš
žœžœžœžœ
žœ
˜DKš
œ5˜5Kšžœ
žœžœ˜*K˜—K˜-K˜—š 	œžœ
žœ9žœ˜WKš
‘ς
™ς
K˜Kšœžœžœ
˜Kšœžœžœ
˜Kš
œJ™JKšœžœ‘˜>˜ šžœžœ˜Kšœžœ
˜Kš
œ˜Kšžœžœ
žœ%˜:Kšžœ
žœžœ˜2—šžœ˜Kšœžœ˜ Kšœžœ˜Kš	œžœžœ
žœžœ˜!Kšžœžœ
žœ
˜4Kš
œ2˜2šžœžœžœ‘˜IKš
œ˜K˜
Kšžœžœ
žœ%˜:Kšžœžœžœžœ˜?Kšžœžœ
žœ
žœ˜Kš
œ˜—Kšžœ
žœ
˜K˜—K˜—K˜-Kšœžœ‘˜(K˜-Kšžœžœ
žœ˜3K˜—Kšžœ
˜K˜š 
œžœ
žœžœ
žœžœ™[Kš
‘e™eKšœ
žœ™%Kšœžœ‘™%™ Kšœžœžœ
™Kšžœžœ
žœ
™ Kšœžœžœ‘)™NKšžœžœžœžœ™GKšžœžœžœžœ™GKšœžœ
žœ™%Kšžœžœžœžœ™HKšžœžœžœžœ™HKšžœžœžœ™/K™—K™-K™—K˜K˜—…—I‚rί