DIRECTORY
Angles2d, AtomButtonsTypes, Basics, GGBasicTypes, GGCoreTypes, GGMeasure, GGModelTypes, GGSegmentTypes, GGTransform, GGUtility, Imager, ImagerTransformation, Lines2d, Vectors2d;

GGUtilityImplB: CEDAR PROGRAM
IMPORTS Angles2d, Basics, ImagerTransformation, Lines2d, Vectors2d
EXPORTS GGMeasure, GGTransform, GGUtility = BEGIN

Line: TYPE = GGCoreTypes.Line;
Point: TYPE = GGBasicTypes.Point;
Segment: TYPE = GGSegmentTypes.Segment;
Scene: TYPE = GGModelTypes.Scene;
Slice: TYPE = GGModelTypes.Slice;
Traj: TYPE = GGModelTypes.Traj;
Vector: TYPE = GGBasicTypes.Vector;


SlopeOfSegment: PUBLIC PROC [seg: Segment] RETURNS [degrees: REAL] = {
direction: Vector;
direction _ Vectors2d.VectorFromPoints[seg.lo, seg.hi];
degrees _ Angles2d.AsSlope[Vectors2d.AngleFromVector[direction]];
};

SlopeOfPoints: PUBLIC PROC [p0, p1: Point] RETURNS [degrees: REAL] = {
direction: Vector;
direction _ Vectors2d.VectorFromPoints[p0, p1];
degrees _ Angles2d.AsSlope[Vectors2d.AngleFromVector[direction]];
};

CounterClockwiseBetweenSegments: PUBLIC PROC [seg1, seg2: Segment] RETURNS [degreesSeg1ToSeg2: REAL] = {
v1, v2: Vector;
v1 _ Vectors2d.VectorFromPoints[seg1.lo, seg1.hi];
v2 _ Vectors2d.VectorFromPoints[seg2.lo, seg2.hi];
degreesSeg1ToSeg2 _ Angles2d.Normalize[Vectors2d.AngleCCWBetweenVectors[v1, v2]];
IF degreesSeg1ToSeg2=360.0 THEN degreesSeg1ToSeg2 _ 0.0;
};

SmallestAngleOfPoints: PUBLIC PROC [a, b, c: Point] RETURNS [degreesAngleABC: REAL] = {
v0, v1: GGBasicTypes.Vector;
v0 _ Vectors2d.VectorFromPoints[b, a];
v1 _ Vectors2d.VectorFromPoints[b, c];
degreesAngleABC _ Vectors2d.SmallestAngleBetweenVectors[v0, v1];
};

LengthOfSegment: PUBLIC PROC [seg: Segment] RETURNS [lengthInPoints: REAL] = {
lengthInPoints _ Vectors2d.Distance[seg.lo, seg.hi];
};

DistanceBetweenPoints: PUBLIC PROC [p0, p1: Point] RETURNS [lengthInPoints: REAL] = {
lengthInPoints _ Vectors2d.Distance[p0, p1];
};

DistanceFromPointToSegment: PUBLIC PROC [p: Point, seg: Segment] RETURNS [distanceInPoints: REAL] = {
distanceInPoints _ 0.0;
};

DistanceFromPointToLine: PUBLIC PROC [p: Point, p1, p2: Point] RETURNS [distance: REAL] = {
line: Line;
line _ Lines2d.LineFromPoints[p1, p2];
distance _ Lines2d.LineDistance[p, line];
};

Identity: PUBLIC PROC RETURNS [id: ImagerTransformation.Transformation] = {
id _ ImagerTransformation.Translate[[0, 0]];
};

Transform: PUBLIC PROC [m: ImagerTransformation.Transformation, p: Point] RETURNS [newP: Point] =  {
result: ImagerTransformation.VEC;
result _ ImagerTransformation.Transform[m, [p.x, p.y] ];
newP _ [result.x, result.y];
};

RotateAboutPoint: PUBLIC PROC [origin: Point, degrees: REAL] RETURNS [m: ImagerTransformation.Transformation] = {
m _ ImagerTransformation.Translate[ [-origin.x, -origin.y] ];
m _ ImagerTransformation.PostRotate[m, degrees];
m _ ImagerTransformation.PostTranslate[m, [origin.x, origin.y]];
};

ScaleAboutPoint: PUBLIC PROC [origin: Point, scalar: REAL] RETURNS [m: ImagerTransformation.Transformation] = {
m _ ImagerTransformation.Translate[ [-origin.x, -origin.y] ];
m _ ImagerTransformation.PostScale[m, scalar];
m _ ImagerTransformation.PostTranslate[m, [origin.x, origin.y]];
};

ScaleUnevenAboutPoint: PUBLIC PROC [origin: Point, scalarX: REAL, scalarY: REAL] RETURNS [m: ImagerTransformation.Transformation] = {
m _ ImagerTransformation.Translate[ [-origin.x, -origin.y] ];
m _ ImagerTransformation.PostScale2[m, [scalarX, scalarY]];
m _ ImagerTransformation.PostTranslate[m, [origin.x, origin.y]];
};
SixPoints: PUBLIC PROC[pts: ARRAY [0..5] OF Point] RETURNS[transform: ImagerTransformation.Transformation] = {
dpts: ARRAY [0..3] OF Point;
a,b,d,e: REAL;
del: REAL;
xform: ImagerTransformation.Transformation;
dpts[0].x _ pts[1].x-pts[0].x;
dpts[0].y _ pts[1].y-pts[0].y;
dpts[1].x _ pts[2].x-pts[0].x;
dpts[1].y _ pts[2].y-pts[0].y;

dpts[2].x _ pts[4].x-pts[3].x;
dpts[2].y _ pts[4].y-pts[3].y;
dpts[3].x _ pts[5].x-pts[3].x;
dpts[3].y _ pts[5].y-pts[3].y;
del _ dpts[0].x*dpts[1].y-dpts[1].x*dpts[0].y;
IF del=0 THEN ERROR;
a _ (dpts[2].x*dpts[1].y-dpts[3].x*dpts[0].y)/del;
b _ (dpts[0].x*dpts[3].x-dpts[1].x*dpts[2].x)/del;
d _ (dpts[2].y*dpts[1].y-dpts[3].y*dpts[0].y)/del;
e _ (dpts[0].x*dpts[3].y-dpts[1].x*dpts[2].y)/del;
xform _ ImagerTransformation.Create[a: a, b: b, c: 0, d: d, e: e, f: 0];
xform _ ImagerTransformation.PostTranslate[xform, [x: pts[3].x, y: pts[3].y]];
xform _ ImagerTransformation.PreTranslate[xform, [x: -pts[0].x, y: -pts[0].y]];
RETURN[xform];
};

FourPoints: PUBLIC PROC[pts: ARRAY [0..3] OF Point] RETURNS[transform: ImagerTransformation.Transformation] = {
xform: ImagerTransformation.Transformation;
a,b,d,e: REAL;
x1: REAL _ pts[1].x-pts[0].x;
x2: REAL _ pts[3].x-pts[2].x;
y1: REAL _ pts[1].y-pts[0].y;
y2: REAL _ pts[3].y-pts[2].y;
del: REAL _ x1*x1+y1*y1;
IF del=0 THEN ERROR;
a _ (x1*x2+y1*y2)/del;
e _ a;
d _ (x1*y2-y1*x2)/del;
b _ -d ;
xform _ ImagerTransformation.Create[a: a, b: b, c: 0, d: d, e: e, f: 0];
xform _ ImagerTransformation.PostTranslate[xform, [x: pts[2].x, y: pts[2].y]];
xform _ ImagerTransformation.PreTranslate[xform, [x: -pts[0].x, y: -pts[0].y]];
RETURN[xform]
};
StartSliceList: PUBLIC PROC [] RETURNS [entityList, ptr: LIST OF Slice] = {
ptr _ entityList _ NIL;
};

AddSlice: PUBLIC PROC [entity: Slice, entityList, ptr: LIST OF Slice] RETURNS [newList, newPtr: LIST OF Slice] = {
IF ptr = NIL THEN {
IF NOT entityList = NIL THEN ERROR;
newPtr _ newList _ CONS[entity, NIL];
RETURN;
}
ELSE {
newList _ entityList;
ptr.rest _ CONS[entity, NIL];
newPtr _ ptr.rest;
};
};

AppendSliceList: PUBLIC PROC [list1, list2: LIST OF Slice] RETURNS [result: LIST OF Slice] = {
pos: LIST OF Slice;
newCell: LIST OF Slice;
IF list1 = NIL THEN RETURN[list2];
result _ CONS[list1.first, NIL];
pos _ result;
FOR l: LIST OF Slice _ list1.rest, l.rest UNTIL l = NIL DO
newCell _ CONS[l.first, NIL];
pos.rest _ newCell;
pos _ newCell;
ENDLOOP;
pos.rest  _ list2;
};

DeleteSliceFromList: PUBLIC PROC [slice: Slice, sliceList: LIST OF Slice] RETURNS [smallerList: LIST OF Slice] = {
beforeEnt, ent, afterEnt: LIST OF Slice;
found: BOOL _ FALSE;
[beforeEnt, ent, afterEnt, found] _ FindSliceAndNeighbors[slice, sliceList];
IF NOT found THEN RETURN[sliceList];
IF beforeEnt = NIL THEN smallerList _ afterEnt
ELSE {
beforeEnt.rest _ afterEnt;
smallerList _ sliceList;
};
};

FindSliceAndNeighbors: PUBLIC PROC [slice: Slice, sliceList: LIST OF Slice] RETURNS [beforeEnt, ent, afterEnt: LIST OF Slice, found: BOOL _ FALSE] = {
lastE: LIST OF Slice _ NIL;
eList: LIST OF Slice _ sliceList;
IF eList = NIL THEN RETURN[NIL, NIL, NIL, FALSE];
UNTIL eList = NIL DO
IF eList.first = slice THEN {
beforeEnt _ lastE;
ent _ eList;
afterEnt _ eList.rest;
found _ TRUE;
RETURN;
};
lastE _ eList;
eList _ eList.rest;
ENDLOOP;
};

CopySliceList: PUBLIC PROC [sliceList: LIST OF Slice] RETURNS [copyList: LIST OF Slice] = {
z: LIST OF Slice _ NIL;
IF sliceList = NIL THEN RETURN[NIL];
copyList _ CONS[sliceList.first, NIL];
z _ copyList;
UNTIL (sliceList _ sliceList.rest) = NIL DO
z.rest _ CONS[sliceList.first, NIL];
z _ z.rest;
ENDLOOP;
};

Comparison: TYPE = Basics.Comparison;
SliceCompareProc: TYPE = GGUtility.SliceCompareProc;
SortSliceList: PUBLIC PROC [list: LIST OF Slice, compareProc: SliceCompareProc] RETURNS [LIST OF Slice] = {

InnerSort: PROC [head: LIST OF Slice, max: NAT] RETURNS [new, next: LIST OF Slice] = {
mid: LIST OF Slice;
new _ head;
mid _ head.rest;
IF mid = NIL THEN RETURN;
next _ mid.rest;
IF compareProc[new.first, mid.first] = greater THEN {
mid.rest _ new; new _ mid; mid _ head;
};
mid.rest _ NIL;
IF next = NIL THEN RETURN;

mid _ next;
next _ next.rest;
IF next # NIL THEN {
temp: LIST OF Slice _ next;
next _ temp.rest;
temp.rest _ NIL;
IF compareProc[mid.first, temp.first] = greater THEN {
mid.rest _ NIL; temp.rest _ mid; mid _ temp}
};

new _ SliceListMerge[new, mid, compareProc];
IF next = NIL THEN RETURN;

FOR depth: NAT IN [2..max) DO
[mid, next] _ InnerSort[next, depth];
new _ SliceListMerge[new, mid, compareProc];
IF next = NIL THEN RETURN;
ENDLOOP;
};
IF list = NIL OR list.rest = NIL THEN RETURN [list];
RETURN [InnerSort[list, 32].new];
};

SortSliceListByPriority: PUBLIC PROC [list: LIST OF Slice] RETURNS [LIST OF Slice] = {
CompareProc: GGUtility.SliceCompareProc = {
priority1, priority2: INT;
priority1 _ ref1.priority;
priority2 _ ref2.priority;
RETURN[Basics.CompareInt[priority1, priority2]];
};
RETURN[SortSliceList[list, CompareProc]];
};

LengthSliceList: PROC [sliceList: LIST OF Slice] RETURNS [count: NAT] = {
count _ 0;
FOR list: LIST OF Slice _ sliceList, list.rest UNTIL list = NIL DO
count _ count + 1;
ENDLOOP;
};

SliceListMerge: PROC [a, b: LIST OF Slice, compare: GGUtility.SliceCompareProc] RETURNS [c: LIST OF Slice _ NIL] = {
aPtr, bPtr, cPtr: LIST OF Slice;
aPtr _ a;
bPtr _ b;
DO
IF aPtr = NIL THEN {
IF c = NIL THEN {c _ cPtr _ bPtr} ELSE cPtr.rest _ bPtr;
RETURN;
};
IF bPtr = NIL THEN {
IF c = NIL THEN {c _ cPtr _ aPtr} ELSE cPtr.rest _ aPtr;
RETURN;
};
SELECT compare[aPtr.first, bPtr.first] FROM
less, equal => {
IF c = NIL THEN c _ aPtr ELSE cPtr.rest _ aPtr;
cPtr _ aPtr;
aPtr _ aPtr.rest;
};
greater => {
IF c = NIL THEN c _ bPtr ELSE cPtr.rest _ bPtr;
cPtr _ bPtr;
bPtr _ bPtr.rest;
}; 
ENDCASE => ERROR;
ENDLOOP;
};

StartTrajList: PUBLIC PROC [] RETURNS [entityList, ptr: LIST OF Traj] = {
ptr _ entityList _ NIL;
};

AddTraj: PUBLIC PROC [entity: Traj, entityList, ptr: LIST OF Traj] RETURNS [newList, newPtr: LIST OF Traj] = {
IF ptr = NIL THEN {
IF NOT entityList = NIL THEN ERROR;
newPtr _ newList _ CONS[entity, NIL];
RETURN;
}
ELSE {
newList _ entityList;
ptr.rest _ CONS[entity, NIL];
newPtr _ ptr.rest;
};
};


END.


ήGGUtilityImplB.mesa
Contents:  Routines for computing measurements on Gargoyle objects.
Copyright c 1986 by Xerox Corporation.  All rights reserved.
Last edited by Bier on January 28, 1987
Pier, October 23, 1987 2:29:35 pm PDT
Bier, May 28, 1990 6:49 pm PDT

GGMeasure
degrees is an angle in 0 <= degrees < 180.
Caution:  this computes distance from p to the straight line incident with both endpoints of seg.  It does not find the distance from p to seg, unless seg is straight.
Computes distance from p to the straight line incident with p1 and p2.
GGTransform

ax1+by1=x2;
dx1+ey1=y2;
but a=e and b=-d so
ax1-dy1=x2;
ay1+dx1=y2;
c _ pts[2].x-pts[0].x;
f _ pts[2].y-pts[0].y; 

Operations on LIST OF Slice

Non-destructive (copies the first list).
... destructively sorts the given list in increasing order according to compareProc.  The sort is not stable, so order of equal elements is not preserved.
First, grab the first pair of elements off the head of the list and make sure that they are sorted.  If there is only one element, we return it immediately.  If there are only two elements in the list first sort them, then return them.
The first two nodes are in the wrong order, so swap them, leaving new pointing at the lesser of the two, and mid pointing at the greater.
Second, grab the second pair of elements off the list.  We have already checked, and there is at least one.
There are two elements for the second pair, so we need to put them in order.
The first two nodes are in the wrong order, so swap them.
Third, merge the two lead lists.  If this exhausts the original list, then return.
Finally, build up the tree by progressively building small lists and merging them into larger lists.  The size doubles at each level.  We start with new holding onto a list of 4 elements, and next holding onto the remainder of the list.
Sort back to front (in increasing order).  Does not preserve order in case of ties.
[ref1: Slice, ref2: Slice] RETURNS [Basics.Comparison]
If a and b are sorted from lesser to greater, c will be.  This merge is stable.  Two elements in a that are equal will end up in the same order that they started in.  Two equal elements from b will preserve their order.  All elements in a will end up before all equal elements in b.
Κ
ΰ˜IcodešΟbœ™šΟnœ;™CKšœ
Οm
œ1™<Kš
œ'™'Kš
œ%™%K™—K™š
Οk	˜	Jš
ϱ
˜±
—K˜šœ œ
 ˜Jš œ;˜BKš œ% ˜1—˜Kšœ œ˜Kšœ œ˜!Kšœ	 œ˜'Kšœ œ˜!Kšœ œ˜!Kšœ œ˜Kšœ œ˜#K˜—K˜K™	š
žœ œ
 œ œ œ˜FK˜Kš
œ7˜7Kš
œA˜AK˜K˜—š
ž
œ œ
 œ œ œ˜FKš
œ*™*K˜Kš
œ/˜/Kš
œA˜AK˜K˜—š
žœ œ
 œ œ œ˜hKš
œ˜Kš
œ2˜2Kš
œ2˜2K•StartOfExpansion6[v1: 
GGBasicTypes.Vector, v2: 
GGBasicTypes.Vector]š
œQ˜QKš œ œ˜8K˜K˜—š
žœ œ
 œ œ œ˜WK˜Kš
œ&˜&Kš
œ&˜&Kš
œ@˜@K˜K˜—š
žœ œ
 œ œ œ˜NKš
œ4˜4K˜K˜—š
žœ œ
 œ œ œ˜UKš
œ,˜,K˜K˜—š
žœ œ
 œ œ œ˜eK™§
Kš
œ˜K˜K˜—š
žœ œ
 œ œ œ˜[Kš
œF™FKš
œ˜Kš
œ&˜&Kš
œ)˜)K˜—K˜K™šžœ œ
 œ
 œ.˜KKš
œ,˜,K˜K˜—šž	œ œ
 œ4 œ˜dKšœ œ
˜!Kš
œ8˜8Kš
œ˜K˜—K˜š
žœ œ
 œ œ œ-˜qKš
œ=˜=Kš
œ0˜0Kš
œ@˜@K˜—K˜š
žœ œ
 œ œ œ-˜oKš
œ=˜=Kš
œ.˜.Kš
œ@˜@K˜—K˜šΠbnœ œ
 œ œ œ œ-˜…
Kš
œ=˜=Kš
œ;˜;Kš
œ@˜@K˜—K™šž	œ œ
 œ œ œ œ4˜nKšœ œ œ˜Kšœ	 œ
˜Kšœ œ
˜
Kš
œ+˜+K˜K˜K˜K˜K˜K˜K˜K˜K˜Kš
œ.˜.Kš œ œ
 œ
˜K˜2K˜2K˜2K˜2K˜HKš
œN˜NKš
œO˜OKš œ˜K˜K˜—šž
œ œ
 œ œ œ œ4˜oKš
œ+˜+Kšœ	 œ
˜Kšœ œ˜Kšœ œ˜Kšœ œ˜Kšœ œ˜Kšœ œ˜K™K™K™K™K™Kš œ œ
 œ
˜Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ™Kš
œ™K˜HKš
œN˜NKš
œO˜OKš œ˜
K˜—K™Kšœ œ
 œ™K™šžœ œ
 œ œ œ
 œ˜KKšœ œ
˜K˜K˜—šžœ œ
 œ" œ
 œ œ œ
 œ˜rš œ œ
 œ˜Kš
 œ
 œ œ
 œ
 œ
˜#Kšœ œ	 œ˜%Kš œ
˜K˜
—š œ˜Kš
œ˜Kšœ œ	 œ˜Kš
œ˜K˜—K˜K˜—šžœ œ
 œ œ
 œ œ
 œ
 œ˜^Kšœ œ
 œ˜Kšœ	 œ
 œ˜K™(Kš œ	 œ
 œ
 œ˜"Kšœ	 œ œ˜ Kš
œ
˜
š œ œ
 œ œ œ
 ˜:Kšœ
 œ
 œ˜Kš
œ˜Kš
œ˜—Kš œ
˜Kš
œ˜Kšœž
˜—šžœ œ
 œ œ
 œ œ œ
 œ˜rKšœ œ
 œ˜(Kšœ œ œ
˜Kš
œL˜LKš œ
 œ œ
 œ˜$Kš œ
 œ
 œ˜.š œ˜Kš
œ˜Kš
œ˜K˜—Kš
œ˜K˜—šžœ œ œ
 œ œ œ
 œ œ œ˜–
Kšœ œ
 œ	 œ
˜Kšœ œ
 œ˜!Kš œ	 œ
 œ
 œ
 œ œ œ œ˜1š œ	 œ
 ˜š œ œ˜Kš
œ˜Kš
œ˜Kš
œ˜Kšœ œ
˜
Kš œ
˜Kš
œ˜—Kš
œ˜Kš
œ˜—Kš œ
˜Kš
œ˜K˜—šž
œ œ
 œ
 œ
 œ œ œ
 œ˜[Kšœ œ
 œ	 œ
˜Kš
 œ
 œ
 œ
 œ
 œ˜$Kšœ œ œ˜&Kš
œ
˜
š œ  œ
 ˜+Kšœ	 œ œ˜$K˜Kš œ
˜—K˜—K˜Kšœ œ˜%Kšœ œ˜4šž
œ œ
 œ œ
 œ' œ œ
 œ˜kKš
œš
™š
K˜šž	œ œ œ
 œ
 œ œ
 œ
 œ˜VKš
œλ
™λ
Kšœ œ
 œ˜Kš
œ˜Kš
œ˜Kš œ œ
 œ
 œ
˜Kš
œ˜š œ
œ! œ˜5Kš
œ‰
™‰
Kš
œ&˜&Kš
œ˜—Kšœ œ
˜Kš œ œ
 œ
 œ
˜K˜Kš
œk™kKš
œ˜Kš
œ˜š œ œ
 œ˜Kš
œL™LKšœ œ
 œ˜Kš
œ˜Kšœ œ
˜š œ
œ" œ˜6Kš
œ9™9Kšœ œ˜,—K˜K˜—K™RKš
œ,˜,Kš œ œ
 œ
 œ
˜K˜Kš
œμ
™μ
š œ œ
 œ
 ˜Kš
œ%˜%Kš
œ,˜,Kš œ œ
 œ
 œ
˜Kš œ
˜—K˜—Kš œ œ
 œ
 œ
 œ
 œ˜4Kš œ˜!K˜K˜—šžœ œ œ
 œ œ œ
 œ˜VK™Sšžœ ˜+Kšœ œ™6Kšœ œ
˜Kš
œ˜Kš
œ˜Kš œ*˜0K˜—Kš œ#˜)K˜K˜—šžœ œ
 œ
 œ œ	 œ˜IKš
œ
˜
š œ œ
 œ œ œ
 ˜BJš
œ˜Jš œ
˜—K˜K˜—šžœ œ œ
 œ- œ œ
 œ	 œ˜tK™šKšœ œ
 œ˜ Kš
œ	˜	Kš
œ	˜	š
 ˜š œ œ
 œ˜Kš œ œ
 œ œ˜8Kš œ
˜K˜—š œ œ
 œ˜Kš œ œ
 œ œ˜8Kš œ
˜K˜—š œ! ˜+˜Kš œ œ
 œ
 œ˜/Kš
œ˜Kš
œ˜K˜—˜Kš œ œ
 œ
 œ˜/Kš
œ˜Kš
œ˜Kš
œ˜—Kš œ œ
˜—Kš œ
˜—K˜K˜—šž
œ œ
 œ œ œ
 œ
˜IKšœ œ
˜K˜K˜—šžœ œ
 œ! œ
 œ œ œ
 œ
˜nš œ œ
 œ˜Kš
 œ
 œ œ
 œ
 œ
˜#Kšœ œ	 œ˜%Kš œ
˜K˜
—š œ˜Kš
œ˜Kšœ œ	 œ˜Kš
œ˜K˜—K˜—K˜K˜Kš œ
˜K˜J˜—…—%’<`