GGUtilityImplB.mesa
Contents: Routines for computing measurements on Gargoyle objects.
Copyright © 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
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;
GGMeasure
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] = {
degrees is an angle in 0 <= degrees < 180.
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] = {
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.
distanceInPoints ← 0.0;
};
DistanceFromPointToLine:
PUBLIC
PROC [p: Point, p1, p2: Point]
RETURNS [distance:
REAL] = {
Computes distance from p to the straight line incident with p1 and p2.
line: Line;
line ← Lines2d.LineFromPoints[p1, p2];
distance ← Lines2d.LineDistance[p, line];
};
GGTransform
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;
ax1+by1=x2;
dx1+ey1=y2;
but a=e and b=-d so
ax1-dy1=x2;
ay1+dx1=y2;
IF del=0 THEN ERROR;
a ← (x1*x2+y1*y2)/del;
e ← a;
d ← (x1*y2-y1*x2)/del;
b ← -d ;
c ← pts[2].x-pts[0].x;
f ← pts[2].y-pts[0].y;
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]
};
Operations on LIST OF Slice
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;
Non-destructive (copies the first list).
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] = {
... destructively sorts the given list in increasing order according to compareProc. The sort is not stable, so order of equal elements is not preserved.
InnerSort:
PROC [head:
LIST
OF Slice, max:
NAT]
RETURNS [new, next:
LIST
OF Slice] = {
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.
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 {
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.
mid.rest ← new; new ← mid; mid ← head;
};
mid.rest ← NIL;
IF next = NIL THEN RETURN;
Second, grab the second pair of elements off the list. We have already checked, and there is at least one.
mid ← next;
next ← next.rest;
IF next #
NIL
THEN {
There are two elements for the second pair, so we need to put them in order.
temp: LIST OF Slice ← next;
next ← temp.rest;
temp.rest ← NIL;
IF
compareProc[mid.first, temp.first] = greater
THEN {
The first two nodes are in the wrong order, so swap them.
mid.rest ← NIL; temp.rest ← mid; mid ← temp}
};
Third, merge the two lead lists. If this exhausts the original list, then return.
new ← SliceListMerge[new, mid, compareProc];
IF next = NIL 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.
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] = {
Sort back to front (in increasing order). Does not preserve order in case of ties.
CompareProc: GGUtility.SliceCompareProc = {
[ref1: Slice, ref2: Slice] RETURNS [Basics.Comparison]
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] = {
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.
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.