PotentialKnotsImpl.mesa
Copyright © 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
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;
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];
};
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]];
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;
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] = {
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;
tans[t+1] ← cDir;
};
};
oDir ← cDir;
ENDLOOP;
FitStateUtils.ForAllSamples[state.slist, set];
};
Progress: PROC[tangent: Complex.VEC, cubic: Cubic.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: 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] = {
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;
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
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;
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;
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.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.
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];
};