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] = { 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] = { 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 = { 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] = { 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] = { 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] = { 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. ~PEHitTestImpl.mesa Written by Darlene Plebon on August 22, 1983 11:48 am Routines for hit testing on trajectories. 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. 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. 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. 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. This routine determines a bounding box for the specified path segment. This routine determines whether two bounding boxes intersect. Κ…˜Iproc– "Cedar" stylešœ™K– "Cedar" stylešœ5™5J™J™)unitšΟk ˜ Jšœ œ˜Jšœ œ3˜BJšœ œs˜J˜ Jšœœ_˜tJšœœX˜e—šœœ˜Jšœ%˜,Jšœ ˜—Lš œ8˜DJ˜Jšœ œ˜Jšœœ ˜ J˜šΟn œœ*œ5˜…J™”Jšœœ˜3šžœ˜šž œ˜Jšœœ)˜>šœ&œ˜.Jšœ%˜%Jšœ˜Jšœ˜Jšœ˜—J˜—Jšœ0˜0J˜—Jšœ,˜,šœ(œ˜0Jšœ œ˜Jšœ œ˜J˜—J˜—J˜šžœœ*œ2œ˜ŒJ™ΓJšœ5œ˜TJšœœ˜J˜JšœŒ˜Œšžœ˜šžœ˜(J™ύJ˜Jšœœ˜JšœU˜UJšœ7˜7šœ,œ˜4Jšœ+˜+J˜J˜ J˜ J˜Jšœ˜—J˜—šœ2˜8JšœX˜X—J˜—šžœ˜*Jšœœ˜2šœ-œ˜5Jšœ,˜,Jšœ ˜ J˜ Jšœ˜—J˜—Jšœ,˜,Jšœ-œ˜EJšœb˜fJšœ˜—J˜šžœœ0œ5˜J™§Jšœœ˜3Jšœ˜Jšœ˜Jšœ˜šžœ˜%JšœP˜Pšœœœ˜!Jšœ:˜:šœ&œ˜.Jšœ˜Jšœ˜Jšœ%˜%Jšœ˜—J˜—J˜—Jšœœ˜Jšœ6˜6J˜—J˜šž œœœ˜PJ™Fšœœœ˜J˜)J˜)J˜—šœ˜J˜5J˜5Jšœ˜—šœ*œœ˜=šœœ˜J˜9J˜9Jšœ˜—šœœ˜J˜9J˜9Jšœ˜—Jšœ˜—J˜—J˜šžœœœœ˜aJ™=J˜YJšœœ"˜5Jšœœ"˜6Jšœ›˜›Jšœœœœœœœ˜…Jšœœœ˜J˜—J˜I modheaderšœ˜J˜—…—tw