<> <> <> <<>> <> 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.