<> <> <> <> <> <> <<>> 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] = { <<... 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] = { <> 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 = { <<[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] = { <> 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.