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.
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 [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;
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.