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