MatchTurtleImpl.mesa
Kurlander, September 6, 1987 6:02:03 pm PDT
Bier, April 8, 1991 10:21 pm PDT
Pier, August 19, 1988 5:08:51 pm PDT
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
Making Turtles
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 = {
SegmentWalkProc: TYPE = PROC [traj: TrajData, seg: Segment, index: NAT] RETURNS [done: BOOL ← FALSE];
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] = {
Finds the greatest distance from a turtle to a point
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];
};
Utilities for Making Turtles
CopyTurtle:
PROC [turtle: TurtleHeader]
RETURNS [newTurtle: TurtleHeader] = {
newTurtle ← NEW[TurtleHeaderObj ← turtle^];
newTurtle.tail ← CopyTurtleTail[turtle.tail];
};
CopyTurtleInPlace:
PROC [original, storage: TurtleHeader]
RETURNS [TurtleHeader] = {
Copies one turtle into another (original into storage). Storage must have the same size tail as original
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] = {
Translates first point to the origin. Rotate [first point..COM] line to be along +x (for rotation invariant turtles), scales the arc length to be targetLength (for scale invariant turtles).
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] = {
Rotate the start point of the turtle.
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];
};
Geometry and Topology
FindCenterOfMass:
PROC [turtleList:
LIST
OF TurtleInfo]
RETURNS [center: Point] = {
Finds the center of mass of the uniform density wire specified by turtleList
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] = {
Slides the origin of a closed turtle so that the first point of the turtle is at least as far from the center of mass as any other point on the turtle.
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];
};
Making Turtles for Gargoyle Slices (implements GetShapeOfSlice)
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 = {
PROC [seg: Segment, transform: Transformation] RETURNS [keep: BOOL];
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] = {
First, we make a turtleTail out of the vector from the bottom left to bottom right points. We know that these are the first and ninth text points.
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;
Next, we package it away and send it off
turtle ← PackageTurtleTail[LineToTurtle[lowerLeft.point, lowerRight.point, NIL]];
};
Making Turtles for Gargoyle Segments (implements SegmentToTurtle)
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];
};
Modifying Turtles
FlipTurtle:
PUBLIC
PROC [turtle: TurtleHeader]
RETURNS [newTurtle: TurtleHeader] = {
Ever try flipping a turtle? They can't get back on their feet! Flips a turtle and normalizes it.
IF NOT turtle.closed THEN newTurtle ← SimpleFlipTurtle[turtle] ELSE newTurtle ← turtle;
newTurtle ← NormalizeTurtle[newTurtle];
SimpleFlipTurtle:
PROC [turtle: TurtleHeader]
RETURNS [newTurtle: TurtleHeader] = {
Flips a turtle without normalizing it
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];
};
};
Comparing Turtles to Turtles
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;
Try to quickly find an answer for all turtle1-turtle2 matches
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];
No quick reject
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] = {
turtle1 is the from turtle and turtle2 is the scene turtle in all cases as of September 5, 1987.
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]];
Identify quick reject cases.
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;
Set up a generator.
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
One turtle to use now and another turtle to use when the start position changes.
};
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.