-- BuildLineImpl.mesa
-- Mesa 6 version
-- Last changed by J Warnock, July 29, 1980 10:13 AM

DIRECTORY
BuildLine: FROM "BuildLine",
BuildSpline: FROM "BuildSpline",
RealFns: FROM "RealFns",
Cubic: FROM "Cubic",
Vector:FROM "Vector",
SystemDefs: FROM "SystemDefs";

BuildLineImpl: PROGRAM
IMPORTS Vector,RealFns,SystemDefs,BuildSpline
EXPORTS BuildLine =
BEGIN OPEN Vector, BuildLine;

KnotHead:TYPE = POINTER TO Knot;
KnotArray: TYPE = DESCRIPTOR FOR ARRAY OF Knot;
Free:PROCEDURE[p:POINTER]={acnt←acnt-1; SystemDefs.FreeHeapNode[p];};
Alloc:PROCEDURE[nwords:CARDINAL]RETURNS [POINTER]={acnt←acnt+1; RETURN[SystemDefs.AllocateHeapNode[nwords]];};
acnt:INTEGER←0;
knothd:KnotHead←NIL;
knottail:KnotHead←NIL;
knotcnt:INTEGER←0;

StartLine: PUBLIC PROCEDURE =
BEGIN
FreeChain[];
END;

EnterLineKnot:PUBLIC PROCEDURE [x,y:REAL] =
BEGIN
k:POINTER TO Knot←LinkKnot[];
k.p.x←x; k.p.y←y;
k.slopeflg←FALSE;
END;

EnterLineKnotSlope:PUBLIC PROCEDURE [x,y,sx,sy:REAL] =
BEGIN
k:POINTER TO Knot←LinkKnot[];
k.p.x←x; k.p.y←y;
k.s←Norm[Vec[sx,sy]];
k.slopeflg←TRUE;
END;

LinkKnot:PROCEDURE RETURNS [k:POINTER TO Knot]=
BEGIN
k←Alloc[SIZE[Knot]];
k.flink←knothd;
k.blink←NIL;
IF knothd=NIL THEN knottail←k ELSE knothd.blink←k;
knothd←k;
knotcnt←knotcnt+1;
END;

FreeChain:PROCEDURE=
BEGIN
tknot:POINTER TO Knot;
UNTIL knotcnt = 0 DO
tknot←knothd;
Free[knothd];
knothd←tknot.flink;
knotcnt←knotcnt-1;
ENDLOOP;
knothd←NIL;
END;

BuildLine: PUBLIC PROCEDURE[width:REAL,proc:PROCEDURE[cb:Cubic.Coeffs]] =
BEGIN OPEN Cubic;
i:INTEGER;
tp,sp:Vec;
tknot:POINTER TO Knot;
w2:REAL←width/2;
SELECT knotcnt FROM
< 2 => RETURN;
ENDCASE =>
{i←knotcnt;
tknot←knothd;
UNTIL i = 0
DO
i←i-1;
IF NOT tknot.slopeflg THEN
{IF tknot.blink=NIL THEN
{tknot.s←Norm[Sub[tknot.p,tknot.flink.p]];
tknot.slopeflg←TRUE;};
IF tknot.flink=NIL THEN
{tknot.s←Norm[Sub[tknot.blink.p,tknot.p]];
tknot.slopeflg←TRUE;};
IF tknot.flink#NIL AND tknot.blink#NIL THEN
{o:Vec;
val:BOOLEAN;
[o,val]←FindCircleCenter[tknot.blink.p,tknot.p,tknot.flink.p];
IF NOT val THEN
{tknot.s←Norm[Sub[tknot.p,tknot.flink.p]];
tknot.slopeflg←TRUE;} ELSE
{vf,vc:Vec;
vc←Sub[tknot.p,o];
vf←Sub[tknot.flink.p,o];
IF Cross[vf,vc] <= 0 THEN
{tknot.s.x←vc.y;tknot.s.y←-vc.x;}
ELSE
{tknot.s.x←-vc.y;tknot.s.y←vc.x;};
tknot.s←Norm[tknot.s];
tknot.slopeflg←TRUE;};
};
};
tknot←tknot.flink;
ENDLOOP;
BuildSpline.StartSpline[];
i←knotcnt;
tknot←knothd;
UNTIL i = 0
DO
i←i-1;
IF tknot.flink # NIL AND
(tknot.p = tknot.flink.p AND tknot.s # tknot.flink.s) THEN
{sp←Norm[Add[tknot.s,tknot.flink.s]];}
ELSE
{sp←tknot.s;};
tp←Vec[tknot.p.x-(sp.y*w2),tknot.p.y+(sp.x*w2)];
BuildSpline.EnterKnotSlope[tp.x,tp.y,-sp.x,-sp.y];
IF tknot.flink=NIL THEN EXIT;
tknot←tknot.flink;
ENDLOOP;
i←knotcnt;
tknot←knottail;
UNTIL i = 0
DO
i←i-1;
IF tknot.blink # NIL AND
(tknot.p = tknot.blink.p AND tknot.s # tknot.blink.s) THEN
{sp←Norm[Add[tknot.s,tknot.blink.s]];}
ELSE
{sp←tknot.s;};
tp←Vec[tknot.p.x+(sp.y*w2),tknot.p.y-(sp.x*w2)];
BuildSpline.EnterKnotSlope[tp.x,tp.y,sp.x,sp.y];
IF tknot.blink=NIL THEN EXIT;
tknot←tknot.blink;
ENDLOOP;
BuildSpline.BuildCyclicSpline[proc];
};
FreeChain[];
END;

FindCircleCenter:PUBLIC PROCEDURE[p0,p1,p2:Vec] RETURNS [o:Vec,valid:BOOLEAN]=
{d1,d2:Vec;
d20,d21,det:REAL;
x20,y20,x21,y21,x22,y22:REAL;
eps:REAL←0.001;
d1←Mul[Sub[p0,p1],2];
d2←Mul[Sub[p1,p2],2];
x20←p0.x*p0.x; y20←p0.y*p0.y;
x21←p1.x*p1.x; y21←p1.y*p1.y;
x22←p2.x*p2.x; y22←p2.y*p2.y;
d20←x20-x21+y20-y21;
d21←x21-x22+y21-y22;
det←Det[Matrix[d1.x,d1.y,d2.x,d2.y]];
IF ABS [det] < eps THEN
{RETURN[Vec[0,0],FALSE]} ELSE
{o.x←(d20*d2.y-d21*d1.y)/det; o.y←(d1.x*d21-d2.x*d20)/det;
RETURN[o,TRUE];};
};

BuildCyclicLine: PUBLIC PROCEDURE
[width:REAL,proc:PROCEDURE[cb:Cubic.Coeffs]]=
BEGIN
knothd.blink←knottail;
knottail.flink←knothd;
BuildLine[width,proc];
END;

Mag:PROCEDURE[v:Vec] RETURNS [m:REAL]=
BEGIN
m←RealFns.SqRt[v.x*v.x+v.y*v.y];
END;

Norm:PROCEDURE[v:Vec] RETURNS [nv:Vec]=
BEGIN
m:REAL;
IF (m←Mag[v]) = 0 THEN RETURN[Vec[0,0]];
nv.x←v.x/m; nv.y←v.y/m;
END;


END.