
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 [Point] =  {
RETURN[ImagerTransformation.Transform[m, p]];
};

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
Copyright ╙ 1986, 1990, 1992 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
Doug Wyatt, April 10, 1992 12:16 pm PDT
Contents:  Routines for computing measurements on Gargoyle objects.

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.
 Э╩╓  Ц(cedarcode) styleХNewlineDelimiter
Щ codeЩKЪЬ	╧eЬ<ЩHKЪЬ'Щ'KЪЬ%Щ%KЩKЩ'KШ ЧKЪ╧nЬ;ЩCKЩ Ъ╧k	Ш	KЪЬ▒Ш▒ЧKШ Ъ╧bЬЯЬЯШKЪЯЬ;ШBKЪЯЬ%ЯШ1ЧШ KЪЬЯЬШKЪЬЯЬШ!KЪЬ	ЯЬШ'KЪЬЯЬШ!KЪЬЯЬШ!KЪЬЯЬШKЪЬЯЬШ#KШ ЧKШ KЩ	Ъ
ЮЬЯЬЯЬЯЬЯЬШFKШKШ7KШAKШKШ ЧЪ
ЮЬЯЬЯЬЯЬЯЬШFKЪЬ*Щ*KШKШ/KШAKШKШ ЧЪ
ЮЬЯЬЯЬЯЬЯЬШhKЪЬШKШ2KШ2KХStartOfExpansion6[v1: GGBasicTypes.Vector, v2: GGBasicTypes.Vector]ШQKЪЯЬЯЬШ8KШKШ ЧЪ
ЮЬЯЬЯЬЯЬЯЬШWKШKШ&KШ&KШ@KШKШ ЧЪ
ЮЬЯЬЯЬЯЬЯЬШNKШ4KШKШ ЧЪ
ЮЬЯЬЯЬЯЬЯЬШUKШ,KШKШ ЧЪ
ЮЬЯЬЯЬЯЬЯЬШeKЩзKШKШKШ ЧЪ
ЮЬЯЬЯЬЯЬЯЬШ[KЪЬFЩFKЪЬШKШ&KШ)KШЧKШ KЩЪЮЬЯЬЯЬЯЬ.ШKKШ,KШKШ ЧЪЮ	ЬЯЬЯЬ4ЯЬШ^KЪЯЬ'Ш-KШЧKШ Ъ
ЮЬЯЬЯЬЯЬЯЬ-ШqKШ=KШ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ШNKШ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ШNKШ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Ш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Ш
ЪЯЬЯЬЯЬЯЬЯЬЯШBKШKЪЯЬШЧ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Ш KШ Ч ЕЧ    %R  ;<  