<> <> <> DIRECTORY PEAlgebra, PETypes USING [Point]; PEAlgebraImpl: CEDAR PROGRAM IMPORTS PEAlgebra EXPORTS PEAlgebra = BEGIN OPEN PEAlgebra, PETypes; ClosestPointOnLineSegment: PUBLIC PROCEDURE [point, p0, p1: Point] RETURNS [closestPoint: Point] = { <> distanceP0P1, distanceP0ClosestPoint, distanceP1ClosestPoint: REAL; closestPoint _ Projection[point, p0, p1]; distanceP0P1 _ DistanceSquared[p0, p1]; distanceP0ClosestPoint _ DistanceSquared[p0, closestPoint]; distanceP1ClosestPoint _ DistanceSquared[p1, closestPoint]; IF distanceP0ClosestPoint > distanceP0P1 OR distanceP1ClosestPoint > distanceP0P1 THEN IF distanceP0ClosestPoint < distanceP1ClosestPoint THEN closestPoint _ p0 ELSE closestPoint _ p1; }; Projection: PUBLIC PROCEDURE [point, p0, p1: Point] RETURNS [colinearPoint: Point] = { <> diffX: REAL _ p1.x - p0.x; diffY: REAL _ p1.y - p0.y; diffX2: REAL _ Sqr[diffX]; diffY2: REAL _ Sqr[diffY]; diffX2PlusDiffY2: REAL _ diffX2 + diffY2; diffXY: REAL _ p0.y*p1.x - p0.x*p1.y; diffXDiffY: REAL _ diffX * diffY; IF diffX2PlusDiffY2 = 0.0 THEN colinearPoint _ p0 ELSE { colinearPoint.x _ (diffXDiffY*point.y + diffX2*point.x - diffXY*diffY) / diffX2PlusDiffY2; colinearPoint.y _ (diffXDiffY*point.x + diffY2*point.y + diffXY*diffX) / diffX2PlusDiffY2; }; }; Intersection: PUBLIC PROCEDURE [line1A, line1B, line2A, line2B: Point] RETURNS [intersecting: BOOLEAN, p: Point] = { <> line1Diff, line2Diff: Point; t1, t2, denominator: REAL; line1Diff.x _ line1B.x - line1A.x; line1Diff.y _ line1B.y - line1A.y; line2Diff.x _ line2B.x - line2A.x; line2Diff.y _ line2B.y - line2A.y; t1 _ line1A.y*line1B.x - line1B.y*line1A.x; t2 _ line2A.y*line2B.x - line2B.y*line2A.x; denominator _ line1Diff.y*line2Diff.x - line2Diff.y*line1Diff.x; intersecting _ denominator # 0.0; IF intersecting THEN { p.x _ (t2*line1Diff.x - t1*line2Diff.x) / denominator; p.y _ (t2*line1Diff.y - t1*line2Diff.y) / denominator; }; }; END.