<> <> <> <> DIRECTORY AtomButtons, CubicPaths, GGBasicTypes, GGModelTypes, GGSegment, GGSegmentTypes, GGSequence, GGSlice, GGSliceOps, GGUserInput, GList, ImagerPath, ImagerTransformation, Match, MatchTurtle, MatchViewer, RealFns, Vectors2d; MatchTurtleImpl: CEDAR PROGRAM IMPORTS AtomButtons, CubicPaths, GList, GGSegment, GGSequence, GGSlice, GGSliceOps, ImagerPath, ImagerTransformation, MatchViewer, RealFns, Vectors2d EXPORTS MatchTurtle = BEGIN MatchData: TYPE = MatchViewer.MatchData; PositionDescriptor: TYPE = MatchTurtle.PositionDescriptor; PositionDObj: TYPE = MatchTurtle.PositionDObj; Matcher: TYPE = MatchTurtle.Matcher; MatcherObj: TYPE = MatchTurtle.MatcherObj; Point: TYPE = GGBasicTypes.Point; Segment: TYPE = GGSegmentTypes.Segment; SegmentGenerator: TYPE = GGModelTypes.SegmentGenerator; Slice: TYPE = GGModelTypes.Slice; TrajData: TYPE = GGModelTypes.TrajData; TurtleHeader: TYPE = MatchTurtle.TurtleHeader; TurtleHeaderObj: TYPE = MatchTurtle.TurtleHeaderObj; TurtleInfo: TYPE = MatchTurtle.TurtleInfo; TurtleInfoObj: TYPE = MatchTurtle.TurtleInfoObj; Traj: TYPE = GGModelTypes.Traj; smallNumber: REAL = 1.0e-20; -- for divide by zero checks <> GetShapeOfSlice: PUBLIC PROC [slice: Slice] RETURNS [TurtleHeader] = { RETURN [ SELECT GGSliceOps.GetType[slice] FROM $Box => BoxToTurtle[slice], $Circle => CircleToTurtle[slice], $Text => TextToTurtle[slice], $Outline => ERROR, -- This routine should not be called for outlines ENDCASE => NIL -- for slices without real shape (eg. IP) ]; }; TrajToTurtle: PUBLIC PROC [traj: Traj] RETURNS [turtle: TurtleHeader] = { AppendTurtleSeg: GGSequence.SegmentWalkProc = { <> tail _ SegmentToTurtle[seg, tail]; }; tail: LIST OF TurtleInfo _ NIL; trajData: TrajData _ NARROW[traj.data]; [] _ GGSequence.WalkSegmentsInTraj[trajData, AppendTurtleSeg]; turtle _ PackageTurtleTail[tail]; }; SegmentToTurtle: PUBLIC PROC [seg: Segment, soFar: LIST OF TurtleInfo, reverse: BOOL _ FALSE] RETURNS [path: LIST OF TurtleInfo] = { SELECT seg.class.type FROM $Line => path _ LineToTurtle[seg.lo, seg.hi, soFar, reverse]; $Arc => path _ ArcToTurtle[seg, soFar, reverse]; $Conic => path _ ConicToTurtle[seg, soFar, reverse]; $Bezier => path _ BezierToTurtle[seg, soFar, reverse]; $CubicSpline => path _ CubicSplineToTurtle[seg, soFar, reverse]; ENDCASE => ERROR; IF path # NIL THEN { -- make sure that path contains seg.hi (or near enough point) extreme: Point _ IF reverse THEN seg.lo ELSE seg.hi; dist: REAL _ Vectors2d.DistanceSquared[path.first.end, extreme]; IF dist >= 1.0 THEN path _ CONS[NEW[TurtleInfoObj _ [length: RealFns.SqRt[dist] + path.first.length, start: path.first.end, end: extreme]], path]; } ELSE path _ LIST[NEW[TurtleInfoObj _ [length: Vectors2d.Distance[seg.lo, seg.hi], start: IF reverse THEN seg.hi ELSE seg.lo, end: IF reverse THEN seg.lo ELSE seg.hi]]]; -- make sure path # NIL on return (seg may be too small to register) }; CopyTurtleTail: PUBLIC PROC [turtleTail: LIST OF TurtleInfo] RETURNS [newTail: LIST OF TurtleInfo _ NIL] = { FOR list: LIST OF TurtleInfo _ turtleTail, list.rest UNTIL list=NIL DO newTail _ CONS[NEW[TurtleInfoObj _ list.first^], newTail]; ENDLOOP; newTail _ NARROW[GList.DReverse[newTail], LIST OF TurtleInfo]; }; PackageTurtleTail: PUBLIC PROC [tail: LIST OF TurtleInfo] RETURNS [turtle: TurtleHeader] = { turtle _ NEW[TurtleHeaderObj]; turtle.length _ tail.first.length; -- note tail is backwards here turtle.tail _ NARROW[GList.Reverse[tail], LIST OF TurtleInfo]; turtle.center _ turtle.originalCenter _ FindCenterOfMass[turtle.tail]; turtle.closed _ IsEssentiallyClosed[turtle.tail]; turtle.radius _ MaxDistanceToTurtle[turtle.tail, turtle.center]; turtle.originalStart _ turtle.tail.first.start; IF turtle.closed THEN turtle _ FindCanonicalStart[turtle]; turtle _ NormalizeTurtle[turtle]; -- converts the turtle to a canonical form, based upon current rotation or scale invariance }; MaxDistanceToTurtle: PROC [turtleList: LIST OF TurtleInfo, point: Point] RETURNS [maxDist: REAL] = { <> maxDist _ Vectors2d.DistanceSquared[point, turtleList.first.start]; FOR turtleList _ turtleList, turtleList.rest UNTIL turtleList=NIL DO newDist: REAL _ Vectors2d.DistanceSquared[point, turtleList.first.end]; IF newDist > maxDist THEN maxDist _ newDist; ENDLOOP; maxDist _ RealFns.SqRt[maxDist]; }; <> CopyTurtle: PROC [turtle: TurtleHeader] RETURNS [newTurtle: TurtleHeader] = { newTurtle _ NEW[TurtleHeaderObj _ turtle^]; newTurtle.tail _ CopyTurtleTail[turtle.tail]; }; CopyTurtleInPlace: PROC [original, storage: TurtleHeader] RETURNS [TurtleHeader] = { <> copyTail: LIST OF TurtleInfo _ storage.tail; originalTail: LIST OF TurtleInfo _ original.tail; storage^ _ original^; FOR list: LIST OF TurtleInfo _ copyTail, list.rest UNTIL list=NIL DO list.first^ _ originalTail.first^; originalTail _ originalTail.rest; ENDLOOP; storage.tail _ copyTail; RETURN[storage]; }; NormalizeTurtle: PROC [turtle: TurtleHeader] RETURNS [TurtleHeader] = { <> turtleList: LIST OF TurtleInfo _ turtle.tail; targetLength: REAL = 500.0; matchData: MatchData _ MatchViewer.GetMatchData[]; firstLoop: BOOL _ TRUE; scaleFactor: REAL _ 1.0; IF turtleList=NIL THEN RETURN[NIL] ELSE { transform: ImagerTransformation.Transformation; transform _ ImagerTransformation.Translate[[-turtleList.first.start.x, -turtleList.first.start.y]]; IF AtomButtons.GetBinaryState[matchData.rotationInv] THEN { angle: REAL; epsilon: REAL = 0.01; startDir: Vectors2d.Vector _ Vectors2d.Sub[turtle.center, turtleList.first.start]; IF ABS[startDir.x] < epsilon AND ABS[startDir.y] < epsilon THEN angle _ 0.0 ELSE angle _ Vectors2d.AngleFromVector[startDir]; ImagerTransformation.ApplyPostRotate[transform, -angle]; }; IF AtomButtons.GetBinaryState[matchData.scaleInv] THEN { length: REAL _ NARROW[GList.NthElement[turtleList, -1], TurtleInfo].length; scaleFactor _ IF length < 1.0 THEN 1.0 ELSE targetLength / length; ImagerTransformation.ApplyPostScale[transform, scaleFactor]; }; FOR tList: LIST OF TurtleInfo _ turtleList, tList.rest UNTIL tList=NIL DO IF firstLoop THEN { tList.first.start _ ImagerTransformation.Transform[transform, tList.first.start]; firstLoop _ FALSE; }; tList.first.end _ ImagerTransformation.Transform[transform, tList.first.end]; tList.first.length _ tList.first.length * scaleFactor; IF tList.rest#NIL THEN tList.rest.first.start _ tList.first.end; -- this end = next start ENDLOOP; turtle.length _ turtle.length * scaleFactor; turtle.radius _ turtle.radius * scaleFactor; turtle.center _ ImagerTransformation.Transform[transform, turtle.center]; IF turtle.tform = NIL THEN turtle.tform _ transform ELSE turtle.tform _ ImagerTransformation.Concat[turtle.tform, transform]; }; RETURN[turtle]; }; SetStartClosedTurtle: PROC [original: TurtleHeader, newStart: LIST OF TurtleInfo, storage: TurtleHeader] RETURNS [TurtleHeader] = { <> oldStart, firstEnd, secondEnd: LIST OF TurtleInfo; storage _ CopyTurtleInPlace[original, storage]; IF original.tail=newStart THEN RETURN [storage]; oldStart _ firstEnd _ storage.tail; FOR list: LIST OF TurtleInfo _ original.tail, list.rest UNTIL list.rest=newStart DO firstEnd _ firstEnd.rest; ENDLOOP; newStart _ firstEnd.rest; -- replace newStart with its analog on the copy firstEnd.rest _ NIL; -- splice into two lists FOR list: LIST OF TurtleInfo _ newStart, list.rest UNTIL list=NIL DO -- adjust lengths of newStart list.first.length _ list.first.length - firstEnd.first.length; secondEnd _ list; ENDLOOP; FOR list: LIST OF TurtleInfo _ oldStart, list.rest UNTIL list=NIL DO -- adjust lengths of oldStart list.first.length _ list.first.length + secondEnd.first.length; ENDLOOP; secondEnd.rest _ oldStart; -- combine the two fragments storage.tail _ newStart; storage.originalStart _ ImagerTransformation.InverseTransform[original.tform, newStart.first.start]; RETURN[storage]; }; <<>> <> <<>> FindCenterOfMass: PROC [turtleList: LIST OF TurtleInfo] RETURNS [center: Point] = { <> lastLength, xSum, ySum: REAL _ 0.0; epsilon: REAL = 0.01; FOR list: LIST OF TurtleInfo _ turtleList, list.rest UNTIL list=NIL DO length: REAL _ list.first.length - lastLength; xSum _ xSum + ((list.first.start.x + list.first.end.x) / 2.0) * length; ySum _ ySum + ((list.first.start.y + list.first.end.y) / 2.0) * length; lastLength _ list.first.length; ENDLOOP; IF lastLength < epsilon THEN RETURN [[turtleList.first.start.x, turtleList.first.start.y]]; RETURN [[xSum/lastLength, ySum/lastLength]]; }; IsEssentiallyClosed: PROC [turtleList: LIST OF TurtleInfo] RETURNS [BOOL _ FALSE] = { firstInfo, lastInfo: TurtleInfo; IF turtleList = NIL OR turtleList.rest = NIL THEN RETURN [FALSE]; -- length must be > 2 firstInfo _ NARROW[GList.NthElement[turtleList, 1], TurtleInfo]; lastInfo _ NARROW[GList.NthElement[turtleList, -1], TurtleInfo]; IF ABS[lastInfo.end.x - firstInfo.start.x] + ABS[lastInfo.end.y - firstInfo.start.y] < 1.0 THEN RETURN [TRUE]; }; RealEqual: PROC [r1, r2: REAL, epsilon: REAL _ 1.0e-6] RETURNS [BOOL _ FALSE] = { IF ABS[r1-r2] <= epsilon THEN RETURN[TRUE] ELSE RETURN[FALSE]; }; FindCanonicalStart: PROC [turtle: TurtleHeader] RETURNS [TurtleHeader] = { <> radiusSquared: REAL _ turtle.radius * turtle.radius; IF NOT CounterClockwise[turtle] THEN turtle _ SimpleFlipTurtle[turtle]; FOR list: LIST OF TurtleInfo _ turtle.tail, list.rest UNTIL list=NIL DO IF RealEqual[radiusSquared, Vectors2d.DistanceSquared[turtle.center, list.first.start], .1] THEN { copy: TurtleHeader _ CopyTurtle[turtle]; copy _ SetStartClosedTurtle[turtle, list, copy]; RETURN[copy]; }; ENDLOOP; ERROR; -- should never reach this return (should increase epsilon in RealEqual call) }; CounterClockwise: PROC [turtle: TurtleHeader] RETURNS [BOOL _ FALSE] = { area: REAL _ 0.0; IF NOT turtle.closed THEN ERROR; IF turtle.tail = NIL OR turtle.tail.rest = NIL THEN RETURN[FALSE]; -- degenerate tail (bogus result) FOR tail: LIST OF TurtleInfo _ turtle.tail, tail.rest UNTIL tail = NIL DO area _ area + tail.first.start.x * tail.first.end.y - tail.first.start.y * tail.first.end.x; ENDLOOP; RETURN[area < 0.0]; }; <<>> <> CircleToTurtle: PROC [slice: Slice] RETURNS [turtle: TurtleHeader] = { p0, p1, p2, p3, center, outerPoint: Point; transform: ImagerTransformation.Transformation; dummyArc: Segment; dist: REAL; [center, outerPoint, transform] _ GGSlice.CircleGetParams[slice]; turtle _ NEW[TurtleHeaderObj]; p0 _ ImagerTransformation.Transform[transform, [0.0, 1.0]]; p1 _ ImagerTransformation.Transform[transform, [1.0, 0.0]]; p2 _ ImagerTransformation.Transform[transform, [0.0, -1.0]]; p3 _ ImagerTransformation.Transform[transform, [-1.0, 0.0]]; dummyArc _ GGSegment.MakeArc[p0, p1, p2, NIL]; -- may be a tad inefficient, but saves code turtle.tail _ ArcToTurtle[dummyArc, NIL]; dummyArc _ GGSegment.MakeArc[p2, p3, p0, NIL]; turtle.tail _ ArcToTurtle[dummyArc, turtle.tail]; dist _ Vectors2d.Distance[p0, turtle.tail.first.end]; -- maybe should check for empty tail? IF dist >= 1.0 THEN turtle.tail _ CONS[NEW[TurtleInfoObj _ [length: dist + turtle.tail.first.length, start: turtle.tail.first.end, end: p0]], turtle.tail]; turtle.length _ turtle.tail.first.length; -- note turtle.tail is backwards here turtle.tail _ NARROW[GList.DReverse[turtle.tail], LIST OF TurtleInfo]; -- put in proper order turtle.center _ turtle.originalCenter _ center; turtle.closed _ TRUE; turtle.radius _ Vectors2d.Distance[center, outerPoint]; turtle.originalStart _ turtle.tail.first.start; IF NOT CounterClockwise[turtle] THEN turtle _ SimpleFlipTurtle[turtle]; -- would normally be handled in FindCanonicalStart, but it would be overkill to call that for circles turtle _ NormalizeTurtle[turtle]; }; BoxToTurtle: PROC [slice: Slice] RETURNS [turtle: TurtleHeader] = { lastHi: Point _ [0,0]; dist: REAL; AppendTurtleSeg: GGModelTypes.WalkProc = { <> lastHi _ ImagerTransformation.Transform[transform, seg.hi]; turtle.tail _ LineToTurtle[ImagerTransformation.Transform[transform, seg.lo], lastHi, turtle.tail]; keep _ TRUE; }; turtle _ NEW[TurtleHeaderObj]; turtle.tail _ NIL; [] _ GGSliceOps.WalkSegments[slice, AppendTurtleSeg]; dist _ Vectors2d.Distance[lastHi, turtle.tail.first.end]; IF dist >= 1.0 THEN turtle.tail _ CONS[NEW[TurtleInfoObj _ [length: dist + turtle.tail.first.length, start: turtle.tail.first.end, end: lastHi]], turtle.tail]; turtle.length _ turtle.tail.first.length; -- note turtle.tail is backwards here turtle.tail _ NARROW[GList.DReverse[turtle.tail], LIST OF TurtleInfo]; -- put in proper order turtle.center _ turtle.originalCenter _ FindCenterOfMass[turtle.tail]; turtle.closed _ TRUE; turtle.radius _ MaxDistanceToTurtle[turtle.tail, turtle.center]; turtle.originalStart _ turtle.tail.first.start; turtle _ FindCanonicalStart[turtle]; turtle _ NormalizeTurtle[turtle]; -- converts the turtle to a canonical form, based upon current rotation or scale invariance }; TextToTurtle: PROC [slice: Slice] RETURNS [turtle: TurtleHeader] = { <> entireD: GGModelTypes.SliceDescriptor _ GGSliceOps.NewParts[slice, NIL, slice]; pointGen: GGModelTypes.PointGenerator _ GGSliceOps.PointsInDescriptor[entireD]; lowerLeft: GGModelTypes.PointAndDone _ GGSliceOps.NextPoint[slice, pointGen]; lowerRight: GGModelTypes.PointAndDone; THROUGH [1..7] DO [] _ GGSliceOps.NextPoint[slice, pointGen]; ENDLOOP; lowerRight _ GGSliceOps.NextPoint[slice, pointGen]; IF lowerLeft.done OR lowerRight.done THEN ERROR; <> turtle _ PackageTurtleTail[LineToTurtle[lowerLeft.point, lowerRight.point, NIL]]; }; <<>> <> <<>> LineToTurtle: PROC [lo, hi: Point, soFar: LIST OF TurtleInfo, reverse: BOOL _ FALSE] RETURNS [path: LIST OF TurtleInfo] = { -- slightly different calling sequence required (called from additional places) length: REAL _ Vectors2d.Distance[lo, hi]; IF length < epsilon/2.0 THEN RETURN[soFar]; IF soFar#NIL THEN length _ length + soFar.first.length; path _ CONS[NEW[TurtleInfoObj _ [length: length, start: IF reverse THEN hi ELSE lo, end: IF reverse THEN lo ELSE hi]], soFar]; }; ArcToTurtle: PROC [seg: Segment, soFar: LIST OF TurtleInfo, reverse: BOOL _ FALSE] RETURNS [LIST OF TurtleInfo] = { ConicTo: ImagerPath.ConicToProc = { ImagerPath.ConicToCurves[lastConicP0, p1, p2, r, BreakUpBezier]; lastConicP0 _ p2; }; BreakUpBezier: ImagerPath.CurveToProc = { path: CubicPaths.Path _ NEW[CubicPaths.PathRec]; path.cubics _ NEW[CubicPaths.PathSequence[1]]; path.cubics[0] _ [lastBezierP0, p1, p2, p3]; CubicPaths.UpdateBounds[path]; CubicPaths.WalkPath[path, epsilon, PointProc]; lastBezierP0 _ p3; }; PointProc: CubicPaths.PointProc = { start: Point _ IF soFar=NIL THEN p0 ELSE soFar.first.end; length: REAL _ Vectors2d.Distance[p, start]; IF length < epsilon/2.0 THEN RETURN; IF soFar#NIL THEN length _ length + soFar.first.length; soFar _ CONS[NEW[TurtleInfoObj _ [length: length, start: start, end: p]], soFar]; }; p0, p1, p2, lastConicP0, lastBezierP0: Point; IF reverse THEN [p2, p1, p0] _ GGSegment.ArcGetParams[seg] ELSE [p0, p1, p2] _ GGSegment.ArcGetParams[seg]; lastConicP0 _ lastBezierP0 _ p0; ImagerPath.ArcToConics[p0, p1, p2, ConicTo]; RETURN[soFar]; }; ConicToTurtle: PROC [seg: Segment, soFar: LIST OF TurtleInfo, reverse: BOOL _ FALSE] RETURNS [LIST OF TurtleInfo] = { BreakUpBezier: ImagerPath.CurveToProc = { path: CubicPaths.Path _ NEW[CubicPaths.PathRec]; path.cubics _ NEW[CubicPaths.PathSequence[1]]; path.cubics[0] _ [lastBezierP0, p1, p2, p3]; CubicPaths.UpdateBounds[path]; CubicPaths.WalkPath[path, epsilon, PointProc]; lastBezierP0 _ p3; }; PointProc: CubicPaths.PointProc = { start: Point _ IF soFar=NIL THEN p0 ELSE soFar.first.end; length: REAL _ Vectors2d.Distance[p, start]; IF length < epsilon/2.0 THEN RETURN; IF soFar#NIL THEN length _ length + soFar.first.length; soFar _ CONS[NEW[TurtleInfoObj _ [length: length, start: start, end: p]], soFar]; }; p0, p1, p2, lastBezierP0: Point; r: REAL; IF reverse THEN [p2, p1, p0, r] _ GGSegment.ConicGetParams[seg] ELSE [p0, p1, p2, r] _ GGSegment.ConicGetParams[seg]; lastBezierP0 _ p0; ImagerPath.ConicToCurves[p0, p1, p2, r, BreakUpBezier]; RETURN[soFar]; }; BezierToTurtle: PROC [seg: Segment, soFar: LIST OF TurtleInfo, reverse: BOOL _ FALSE] RETURNS [LIST OF TurtleInfo] = { PointProc: CubicPaths.PointProc = { start: Point _ IF soFar=NIL THEN p0 ELSE soFar.first.end; length: REAL _ Vectors2d.Distance[p, start]; IF length < epsilon/2.0 THEN RETURN; IF soFar#NIL THEN length _ length + soFar.first.length; soFar _ CONS[NEW[TurtleInfoObj _ [length: length, start: start, end: p]], soFar]; }; p0, p1, p2, p3: Point; path: CubicPaths.Path _ NEW[CubicPaths.PathRec]; IF reverse THEN [p3, p2, p1, p0] _ GGSegment.BezierGetParams[seg] ELSE [p0, p1, p2, p3] _ GGSegment.BezierGetParams[seg]; path.cubics _ NEW[CubicPaths.PathSequence[1]]; path.cubics[0] _ [p0, p1, p2, p3]; CubicPaths.UpdateBounds[path]; CubicPaths.WalkPath[path, epsilon, PointProc]; RETURN[soFar]; }; CubicSplineToTurtle: PROC [seg: Segment, soFar: LIST OF TurtleInfo, reverse: BOOL _ FALSE] RETURNS [LIST OF TurtleInfo] = { PointProc: CubicPaths.PointProc = { start: Point _ IF soFar=NIL THEN path.cubics[0].b0 ELSE soFar.first.end; length: REAL _ Vectors2d.Distance[p, start]; IF length < epsilon/2.0 THEN RETURN; IF soFar#NIL THEN length _ length + soFar.first.length; soFar _ CONS[NEW[TurtleInfoObj _ [length: length, start: start, end: p]], soFar]; }; path: CubicPaths.Path _ GGSegment.CubicSplineGetParams[seg]; IF reverse THEN CubicPaths.ReversePath[CubicPaths.CopyPath[path]]; CubicPaths.WalkPath[path, epsilon, PointProc]; RETURN[soFar]; }; <<>> <> FlipTurtle: PUBLIC PROC [turtle: TurtleHeader] RETURNS [newTurtle: TurtleHeader] = { <> IF NOT turtle.closed THEN newTurtle _ SimpleFlipTurtle[turtle] ELSE newTurtle _ turtle; newTurtle _ NormalizeTurtle[newTurtle]; }; SimpleFlipTurtle: PROC [turtle: TurtleHeader] RETURNS [newTurtle: TurtleHeader] = { <> lastLength, thisLength: REAL _ 0.0; newTurtle _ CopyTurtle[turtle]; IF turtle.tail # NIL THEN { FOR tailList: LIST OF TurtleInfo _ newTurtle.tail, tailList.rest UNTIL tailList=NIL DO temp: Point _ tailList.first.start; -- swap start and end tailList.first.start _ tailList.first.end; tailList.first.end _ temp; thisLength _ tailList.first.length; tailList.first.length _ turtle.length - lastLength; lastLength _ thisLength ENDLOOP; newTurtle.tail _ NARROW[GList.DReverse[newTurtle.tail], LIST OF TurtleInfo]; newTurtle.originalStart _ ImagerTransformation.InverseTransform[newTurtle.tform, newTurtle.tail.first.start]; }; }; <<>> <> epsilon: REAL = 3.0; ManhattanDistance: PROC [pt1, pt2: Point] RETURNS [REAL] = { RETURN[ABS[pt2.x - pt1.x] + ABS[pt2.y - pt1.y]]; }; TurtleEqualEitherWay: PUBLIC PROC [turtle1, turtle2: TurtleHeader, tol: REAL _ MatchViewer.GetMatchTolerance[], posD: PositionDescriptor _ NIL] RETURNS [BOOL _ FALSE] = { matchData: MatchData _ MatchViewer.GetMatchData[]; IF AtomButtons.GetBinaryState[matchData.polarity] OR turtle1.closed THEN RETURN[TurtleEqual[turtle1, turtle2, tol, posD]] ELSE { flipped1: TurtleHeader _ FlipTurtle[turtle1]; RETURN[TurtleEqual[turtle1, turtle2, tol, posD] OR TurtleEqual[flipped1, turtle2, tol, posD]]; }; }; TurtleEqual: PUBLIC PROC [turtle1, turtle2: TurtleHeader, tol: REAL _ MatchViewer.GetMatchTolerance[], posD: PositionDescriptor] RETURNS [BOOL _ FALSE] = { IF NOT posD.valid THEN { matcher: Matcher _ CreateMatcher[turtle1, turtle2, tol, TRUE]; next: PositionDescriptor _ NextMatch[matcher]; IF next # NIL THEN { IF posD.settable THEN { posD^ _ next^; posD.others _ matcher; -- return the orientation that achieves the turtle match }; RETURN[TRUE]; -- we did find an orientation that matches the turtles } ELSE RETURN[FALSE]; } ELSE RETURN[TurtleEqualAux[turtle1, turtle2, tol, posD]]; }; TurtleEqualAux: PUBLIC PROC [turtle1, turtle2: TurtleHeader, tol: REAL _ MatchViewer.GetMatchTolerance[], posD: PositionDescriptor _ NIL] RETURNS [BOOL _ FALSE] = { maxError: REAL; <> IF turtle1 = turtle2 THEN RETURN[TRUE]; -- true if both NIL IF turtle1 = NIL OR turtle2 = NIL THEN RETURN[FALSE]; IF turtle1.closed # turtle2.closed THEN RETURN[FALSE]; -- closed can never match open maxError _ tol * (turtle1.length + turtle2.length) / 2.0; IF ABS[turtle1.radius - turtle2.radius] > maxError THEN RETURN[FALSE]; IF ABS[turtle1.length - turtle2.length] > maxError THEN RETURN[FALSE]; <> IF NOT turtle1.closed THEN { -- Open turtles are easy IF OpenTurtleEqual[turtle1, turtle2, maxError, posD] THEN { SetPosD[posD, turtle1, turtle2]; RETURN[TRUE]; } ELSE RETURN[FALSE]; } ELSE { -- Closed turtles may require testing multiple starting points. matchData: MatchData _ MatchViewer.GetMatchData[]; rotationInv: BOOL _ AtomButtons.GetBinaryState[matchData.rotationInv]; turtleCopy: TurtleHeader _ CopyTurtle[turtle2]; FOR tail2: LIST OF TurtleInfo _ turtle2.tail, tail2.rest UNTIL tail2 = NIL DO IF NOT rotationInv AND ManhattanDistance[turtle1.center, Vectors2d.Add[turtle2.center, Vectors2d.Sub[turtle1.tail.first.start, tail2.first.start]]] > maxError THEN LOOP; -- reject: not rotation invariant and the centers are far apart << [Artwork node; type 'Artwork on' to command tool] >> IF ABS[Vectors2d.Distance[turtle2.center, tail2.first.start] - turtle2.radius] < maxError THEN { turtleCopy _ SetStartClosedTurtle[turtle2, tail2, turtleCopy]; turtleCopy _ NormalizeTurtle[turtleCopy]; IF OpenTurtleEqual[turtle1, turtleCopy, maxError, posD] THEN { SetPosD[posD, turtle1, turtleCopy]; RETURN[TRUE]; }; }; ENDLOOP; }; }; SetPosD: PROC [posD: PositionDescriptor, turtle1, turtle2: TurtleHeader] = { <> IF posD # NIL AND posD.settable AND NOT posD.valid THEN { posD.valid _ TRUE; posD.tform1 _ turtle1.tform; posD.tform2 _ turtle2.tform; }; }; GetInterpolatedPoint: PROC [param, lengthSoFar: REAL, t: TurtleInfo] RETURNS [pt: Point] = { ratio, divisor: REAL; divisor _ t.length - lengthSoFar; IF ABS[divisor] < smallNumber THEN RETURN[t.start]; ratio _ (param - lengthSoFar)/divisor; pt _ Vectors2d.Add[t.start, Vectors2d.Scale[Vectors2d.Sub[t.end, t.start], ratio]]; }; OpenTurtleEqual: PROC [turtle1, turtle2: TurtleHeader, maxError: REAL, posD: PositionDescriptor _ NIL] RETURNS [BOOL _ TRUE] = { OPEN ImagerTransformation; length1, length2, maxDist, dist: REAL _ 0.0; t1: LIST OF TurtleInfo _ turtle1.tail; t2: LIST OF TurtleInfo _ turtle2.tail; tailPoint: Point _ [0,0]; IF ManhattanDistance[turtle1.center, turtle2.center] > maxError THEN RETURN[FALSE]; IF posD#NIL AND posD.valid AND ( ManhattanDistance[ -- compare in the posD canonical coordinate frame Transform[posD.tform1, turtle1.originalStart], Transform[posD.tform2, turtle2.originalStart]] > 2.0 * maxError OR ManhattanDistance[ Transform[posD.tform1, turtle1.originalCenter], Transform[posD.tform2, turtle2.originalCenter]] > 2.0 * maxError) THEN RETURN [FALSE]; -- (multiplying maxError by 2 since this operation is very conducive to floating point error) IF t1=NIL OR t2=NIL THEN RETURN[FALSE]; maxDist _ ManhattanDistance[t1.first.start, t2.first.start]; WHILE t1#NIL OR t2#NIL DO IF t1=NIL THEN { -- take element off t2 (t1 is NIL) dist _ ManhattanDistance[t2.first.end, tailPoint]; -- tailPoint is last point in exhausted list maxDist _ MAX[dist, maxDist]; length2 _ t2.first.length; t2 _ t2.rest; } ELSE IF t2=NIL THEN { -- take element off t1 (t2 is NIL) dist _ ManhattanDistance[t1.first.end, tailPoint]; -- tailPoint is last point in exhausted list maxDist _ MAX[dist, maxDist]; length1 _ t1.first.length; t1 _ t1.rest; } ELSE { -- t1 and t2 both have elements left IF t1.first.length < t2.first.length THEN { -- take element off t1 pt: Point _ GetInterpolatedPoint[t1.first.length, length2, t2.first]; dist _ ManhattanDistance[pt, t1.first.end]; maxDist _ MAX[dist, maxDist]; length1 _ t1.first.length; tailPoint _ t1.first.end; t1 _ t1.rest; } ELSE { -- take element off t2 pt: Point _ GetInterpolatedPoint[t2.first.length, length1, t1.first]; dist _ ManhattanDistance[pt, t2.first.end]; maxDist _ MAX[dist, maxDist]; length2 _ t2.first.length; tailPoint _ t2.first.end; t2 _ t2.rest; }; }; IF maxDist > maxError THEN RETURN [FALSE]; ENDLOOP; }; CreateMatcher: PUBLIC PROC [turtle1, turtle2: TurtleHeader, tol: REAL _ -1.0, oneWay: BOOL _ FALSE] RETURNS [m: Matcher] = { m _ NEW[MatcherObj _ [noMatch: TRUE]]; <> IF turtle1 = turtle2 THEN RETURN; -- no match (bool has been set to TRUE) IF turtle1 = NIL OR turtle2 = NIL THEN RETURN; IF turtle1.closed # turtle2.closed THEN RETURN; -- closed can never match open m.maxError _ tol * (turtle1.length + turtle2.length) / 2.0; IF ABS[turtle1.radius - turtle2.radius] > m.maxError THEN RETURN; IF ABS[turtle1.length - turtle2.length] > m.maxError THEN RETURN; <> m.turtle1 _ turtle1; m.turtle2 _ turtle2; m.tailSoFar _ turtle2.tail; m.checkFirst _ TRUE; m.checkSecond _ NOT oneWay; m.noMatch _ FALSE; IF turtle2.closed THEN m.turtleCopy _ CopyTurtle[turtle2]; -- will be used for orientation testing <> }; NextMatch: PUBLIC PROC [m: Matcher] RETURNS [PositionDescriptor _ NIL] = { IF m.noMatch THEN RETURN[NIL]; IF NOT m.turtle1.closed THEN { IF m.checkFirst THEN { m.checkFirst _ FALSE; IF OpenTurtleEqual[m.turtle1, m.turtle2, m.maxError] THEN RETURN[NEW[PositionDObj _ [tform1: m.turtle1.tform, tform2: m.turtle2.tform, valid: TRUE, settable: FALSE, others: m]]]; }; IF m.checkSecond THEN { flipped1: TurtleHeader _ FlipTurtle[m.turtle1]; m.noMatch _ TRUE; -- no more matches after this IF OpenTurtleEqual[flipped1, m.turtle2, m.maxError] THEN RETURN[NEW[PositionDObj _ [tform1: flipped1.tform, tform2: m.turtle2.tform, valid: TRUE, settable: FALSE, others: m]]] }; RETURN[NIL]; } ELSE { -- we have to test against every possible axis (potentially slow!) until we find a match matchData: MatchData _ MatchViewer.GetMatchData[]; rotationInv: BOOL _ AtomButtons.GetBinaryState[matchData.rotationInv]; FOR tail2: LIST OF TurtleInfo _ m.tailSoFar, tail2.rest UNTIL tail2 = NIL DO IF NOT rotationInv AND ManhattanDistance[m.turtle1.center, Vectors2d.Add[m.turtle2.center, Vectors2d.Sub[m.turtle1.tail.first.start, tail2.first.start]]] > m.maxError THEN LOOP; -- an optimization IF ABS[Vectors2d.Distance[m.turtle2.center, tail2.first.start] - m.turtle2.radius] < m.maxError THEN { m.turtleCopy _ SetStartClosedTurtle[m.turtle2, tail2, m.turtleCopy]; m.turtleCopy _ NormalizeTurtle[m.turtleCopy]; IF OpenTurtleEqual[m.turtle1, m.turtleCopy, m.maxError] THEN { m.tailSoFar _ tail2.rest; RETURN[NEW[PositionDObj _ [tform1: m.turtle1.tform, tform2: m.turtleCopy.tform, valid: TRUE, settable: FALSE, others: m]]]; }; }; ENDLOOP; }; }; END.