PEHitTestImpl.mesa
Copyright (C) 1984 by Xerox Corporation. All rights reserved.
Written by Darlene Plebon on August 22, 1983 11:48 am
Routines for hit testing on trajectories.
DIRECTORY
Graphics USING [Box],
PEAlgebra USING [ClosestPointOnLineSegment, DistanceSquared, Sqr],
PEBezier USING [Bezier, BezierLineProc, BezierPointProc, BezierSubdivideUntilLines, BezierSubdivideUntilPoints, SegmentToBezier],
PEHitTest,
PETrajectoryOps USING [ForAllSegments, ForAllTrajectories, ForAllVertices, SegmentProc, TrajectoryProc, VertexProc],
PETypes USING [Point, Segment, SegmentList, SegmentNode, TrajectoryList, TrajectoryNode, VertexNode];
PEHitTestImpl: CEDAR PROGRAM
IMPORTS PEAlgebra, PEBezier, PETrajectoryOps
EXPORTS PEHitTest =
BEGIN OPEN PEAlgebra, PEBezier, PEHitTest, PETrajectoryOps, PETypes;
maxAllowed: REAL = 30.0;
maxAllowedSquared: REAL = 900.0;
VertexHitTest: PUBLIC PROCEDURE [segmentList: SegmentList, point: Point] RETURNS [hitVertex: VertexNode, hitSegment: SegmentNode] = {
This routine returns the vertex node in the specified segment list that is closest to the specified point along with the segment node containing that vertex. If the specified point is not within a threshold distance of any vertex, NIL is returned for the closest vertex node.
minDistanceSquared: REAL ← maxAllowedSquared + 1.0;
HitTestSegment: SegmentProc = {
HitTestVertex: VertexProc = {
distanceSquared: REAL ← DistanceSquared[point, v.first.point];
IF distanceSquared < minDistanceSquared THEN {
minDistanceSquared ← distanceSquared;
hitVertex ← v;
hitSegment ← s;
};
};
ForAllVertices[s.first.vertices, HitTestVertex];
};
ForAllSegments[segmentList, HitTestSegment];
IF minDistanceSquared > maxAllowedSquared THEN {
hitVertex ← NIL;
hitSegment ← NIL;
};
};
SegmentHitTest: PUBLIC PROCEDURE [segmentList: SegmentList, point: Point] RETURNS [hitSegment: SegmentNode, hitPoint: Point, hitT: REAL] = {
This routine determines whether the specified point is "close" to one of the segments in the specified segment list. This routine returns the segment that the point is closest to (or NIL if the point is close to no segment), the point on that segment to which it is closest, and the value of the parameter t at that point.
minDistanceSquaredToLine, minDistanceSquaredToPoint: REAL ← maxAllowedSquared + 1.0;
hitT0, hitT3: REAL;
hitBezier: Bezier;
hitTestBox: Graphics.Box ← [xmin: point.x - maxAllowed, xmax: point.x + maxAllowed, ymin: point.y - maxAllowed, ymax: point.y + maxAllowed];
HitTestSegment: SegmentProc = {
CheckClosenessToLine: BezierLineProc = {
First determine the point on the line segment [b0,b3] which is closest to the test point. In the case where the projection of the test point onto the line defined by b0 and b3 is not on the segment [b0, b3], either b0 or b3 is closest to the test point.
closestPoint: Point;
distanceSquared: REAL;
closestPoint ← ClosestPointOnLineSegment[point: point, p0: bezier.b0, p1: bezier.b3];
distanceSquared ← DistanceSquared[point, closestPoint];
IF distanceSquared < minDistanceSquaredToLine THEN {
minDistanceSquaredToLine ← distanceSquared;
hitSegment ← s;
hitT0 ← t0;
hitT3 ← t3;
hitBezier ← bezier;
};
};
IF BoxesIntersect[BoundingBox[s.first], hitTestBox] THEN
BezierSubdivideUntilLines[bezier: SegmentToBezier[s.first], proc: CheckClosenessToLine];
};
CheckClosenessToPoint: BezierPointProc = {
distanceSquared: REAL ← DistanceSquared[point, p];
IF distanceSquared < minDistanceSquaredToPoint THEN {
minDistanceSquaredToPoint ← distanceSquared;
hitPoint ← p;
hitT ← t;
};
};
ForAllSegments[segmentList, HitTestSegment];
IF minDistanceSquaredToLine > maxAllowedSquared THEN hitSegment ← NIL
ELSE BezierSubdivideUntilPoints[bezier: hitBezier, proc: CheckClosenessToPoint, t0: hitT0, t3: hitT3];
};
TrajectoryHitTest: PUBLIC PROCEDURE [trajectoryList: TrajectoryList, point: Point] RETURNS [hitTrajectory: TrajectoryNode, hitPoint: Point] = {
This routines determines whether the specified point is "close" to one of the trajectories in the specified trajectory list. This routine returns the trajectory that the point is closest to (or NIL if the point is close to no trajectory) and the point on that trajectory to which it is closest.
hitDistanceSquared: REAL ← maxAllowedSquared + 1.0;
distanceSquared: REAL;
segmentHitSegment: SegmentNode;
segmentHitPoint: Point;
HitTestTrajectory: TrajectoryProc = {
[segmentHitSegment, segmentHitPoint,] ← SegmentHitTest[t.first.segments, point];
IF segmentHitSegment # NIL THEN {
distanceSquared ← DistanceSquared[point, segmentHitPoint];
IF distanceSquared < hitDistanceSquared THEN {
hitTrajectory ← t;
hitPoint ← segmentHitPoint;
hitDistanceSquared ← distanceSquared;
};
};
};
hitTrajectory ← NIL;
ForAllTrajectories[trajectoryList, HitTestTrajectory];
};
BoundingBox: PUBLIC PROCEDURE [segment: Segment] RETURNS [box: Graphics.Box] = {
This routine determines a bounding box for the specified path segment.
IF segment.fp # NIL THEN {
box.xmin ← box.xmax ← segment.fp.point.x;
box.ymin ← box.ymax ← segment.fp.point.y;
}
ELSE {
box.xmin ← box.xmax ← segment.vertices.first.point.x;
box.ymin ← box.ymax ← segment.vertices.first.point.y;
};
FOR v: VertexNode ← segment.vertices, v.rest UNTIL v = NIL DO
SELECT TRUE FROM
v.first.point.x < box.xmin => box.xmin ← v.first.point.x;
v.first.point.x > box.xmax => box.xmax ← v.first.point.x;
ENDCASE;
SELECT TRUE FROM
v.first.point.y < box.ymin => box.ymin ← v.first.point.y;
v.first.point.y > box.ymax => box.ymax ← v.first.point.y;
ENDCASE;
ENDLOOP;
};
BoxesIntersect: PUBLIC PROCEDURE [box1, box2: Graphics.Box] RETURNS [boxesIntersect: BOOLEAN] = {
This routine determines whether two bounding boxes intersect.
box2Center: Point ← [x: (box2.xmin + box2.xmax) / 2.0, y: (box2.ymin + box2.ymax) / 2.0];
box2HalfWidth: REAL ← box2Center.x - box2.xmin + 0.5;
box2HalfHeight: REAL ← box2Center.y - box2.ymin + 0.5;
box: Graphics.Box ← [xmin: box1.xmin - box2HalfWidth, xmax: box1.xmax + box2HalfWidth, ymin: box1.ymin - box2HalfHeight, ymax: box1.ymax + box2HalfHeight];
IF box2Center.x >= box.xmin AND box2Center.x <= box.xmax AND box2Center.y >= box.ymin AND box2Center.y <= box.ymax THEN RETURN [TRUE]
ELSE RETURN [FALSE];
};
END.