PEHitTestImpl.mesa
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];
};