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. ,PEAlgebraImpl.mesa Written by Darlene Plebon on August 16, 1983 3:32 pm Useful linear algebra routines. This routine returns the point on the line segment [p0,p1] which is closest to the specified point. This procedure projects the specified point onto the line defined by p0 and p1. The returned point is colinear with p0 and p1. This routine determines the intersection of two lines, each of which is defined by two points on the line. This routine returns an indication of whether the two lines intersect, along with the point of intersection. ʘJšœ™Jšœ4™4J˜J™J˜šÏk ˜ Jšœ ˜ Jšœœ ˜J˜—šœœ˜Jšœ ˜Jšœ ˜—J˜Jšœœ˜J˜šÏnœœœ˜dJ™cJšœ>œ˜CJšœ)˜)Jšœ'˜'Jšœ;˜;Jšœ;˜;šœ'œ'œ˜WJšœ1œ˜IJšœ˜—J˜—J˜šž œœœ˜VJ™Jšœœ˜Jšœœ˜Jšœœ˜Jšœœ˜Jšœœ˜)Jšœœ˜%Jšœ œ˜!Jšœœ˜1šœ˜JšœZ˜ZJšœZ˜ZJ˜—J˜—J˜š ž œœ œ)œœ˜tJ™ØJ˜Jšœœ˜Jšœ"˜"Jšœ"˜"Jšœ"˜"Jšœ"˜"Jšœ+˜+Jšœ+˜+Jšœ@˜@Jšœ!˜!šœœ˜Jšœ6˜6Jšœ6˜6J˜—J˜—J˜Jš˜J˜—…—v ±