DIRECTORY GGCircles, GGLines, GGModelTypes, GGVector, RealFns; GGCirclesImpl: CEDAR PROGRAM IMPORTS GGLines, GGVector, RealFns EXPORTS GGCircles = BEGIN Arc: TYPE = GGModelTypes.Arc; Circle: TYPE = REF CircleObj; CircleObj: TYPE = GGModelTypes.CircleObj; Point: TYPE = GGModelTypes.Point; Edge: TYPE = GGModelTypes.Edge; Line: TYPE = GGModelTypes.Line; Vector: TYPE = GGModelTypes.Vector; CreateEmptyCircle: PUBLIC PROC [] RETURNS [circle: Circle] = { circle _ NEW[CircleObj _ [ origin: [0.0, 0.0], radius: 0.0 ]]; }; CopyCircle: PUBLIC PROC [from: Circle, to: Circle] = { to.origin _ from.origin; to.radius _ from.radius; }; FillCircleFromPointAndRadius: PUBLIC PROC [pt: Point, radius: REAL, circle: Circle] = { circle.origin _ pt; circle.radius _ radius; }; CircleFromPointAndRadius: PUBLIC PROC [pt: Point, radius: REAL] RETURNS [circle: Circle] = { circle _ CreateEmptyCircle[]; FillCircleFromPointAndRadius[pt, radius, circle]; }; LineMeetsCircle: PUBLIC PROC [line: Line, circle: Circle] RETURNS [points: ARRAY [1..2] OF Point, hitCount: [0..2]] = { d, magD, b: REAL; p, h: Point; d _ GGLines.SignedLineDistance[circle.origin, line]; magD _ ABS[d]; SELECT magD FROM > circle.radius => hitCount _ 0; = circle.radius => { -- tangent. One intersection point. hitCount _ 1; points[1] _ GGVector.Sub[circle.origin, GGVector.Scale[[-line.s, line.c], d]]; }; < circle.radius => { -- two intersections hitCount _ 2; p _ GGVector.Sub[circle.origin, GGVector.Scale[[-line.s, line.c], d]]; b _ RealFns.SqRt[circle.radius*circle.radius - d*d]; h _ GGVector.Scale[[line.c, line.s], b]; points[1] _ GGVector.Sub[p, h]; points[2] _ GGVector.Add[p, h]; }; ENDCASE => ERROR; }; RatherClose: PROC [p1, p2: Point] RETURNS [BOOL] = { epsilon: REAL = 1.0e-5; RETURN[ABS[p1[1] - p2[1]] < epsilon AND ABS[p1[2] - p2[2]] < epsilon]; }; CircleMeetsCircle: PUBLIC PROC [circle1, circle2: Circle] RETURNS [points: ARRAY [1..2] OF Point, hitCount: [0..2]] = { o1ToO2, o1ToO2Hat: Vector; magO1ToO2: REAL; IF RatherClose[circle1.origin, circle2.origin] THEN { hitCount _ 0; RETURN; }; o1ToO2 _ GGVector.Sub[circle2.origin, circle1.origin]; magO1ToO2 _ GGVector.Magnitude[o1ToO2]; SELECT magO1ToO2 FROM > circle1.radius + circle2.radius => hitCount _ 0; = circle1.radius + circle2.radius => { hitCount _ 1; o1ToO2Hat _ GGVector.Scale[o1ToO2, 1.0/magO1ToO2]; points[1] _ GGVector.Add[circle1.origin, GGVector.Scale[o1ToO2Hat, circle1.radius]]; }; IN (ABS[circle1.radius - circle2.radius] .. circle1.radius + circle2.radius) => { p: Point; normal: Vector; s, h, m: REAL; hitCount _ 2; o1ToO2Hat _ GGVector.Scale[o1ToO2, 1.0/magO1ToO2]; s _ 0.5*(circle1.radius + circle2.radius + magO1ToO2); h _ 2.0*RealFns.SqRt[s*(s-magO1ToO2)*(s-circle1.radius)*(s-circle2.radius)]/magO1ToO2; m _ RealFns.SqRt[circle1.radius*circle1.radius - h*h]; p _ GGVector.Add[circle1.origin, GGVector.Scale[o1ToO2Hat, m]]; normal _ [-h*o1ToO2Hat[2], h*o1ToO2Hat[1]]; points[1] _ GGVector.Sub[p, normal]; points[2] _ GGVector.Add[p, normal]; }; = ABS[circle1.radius - circle2.radius] => { hitCount _ 1; IF circle1.radius > circle2.radius THEN { o1ToO2Hat _ GGVector.Scale[o1ToO2, 1.0/magO1ToO2]; points[1] _ GGVector.Add[circle1.origin, GGVector.Scale[o1ToO2Hat, circle1.radius]]; } ELSE { o1ToO2Hat _ GGVector.Scale[o1ToO2, -1.0/magO1ToO2]; points[1] _ GGVector.Add[circle2.origin, GGVector.Scale[o1ToO2Hat, circle2.radius]]; }; }; < ABS[circle1.radius - circle2.radius] => { hitCount _ 0; }; ENDCASE => ERROR; }; SignedCircleDistance: PUBLIC PROC [pt: Point, circle: Circle] RETURNS [d: REAL] = { originToPoint: REAL; originToPoint _ GGVector.Magnitude[GGVector.Sub[pt, circle.origin]]; d _ originToPoint - circle.radius; }; CircleDistance: PUBLIC PROC [pt: Point, circle: Circle] RETURNS [d: REAL] = { d _ ABS[SignedCircleDistance[pt, circle]]; }; PointProjectedOntoCircle: PUBLIC PROC [pt: Point, circle: Circle] RETURNS [projectedPt: Point] = { epsilon: REAL = 1.0e-5; originToPoint: Vector; magOriginToPoint: REAL; originToPoint _ GGVector.Sub[pt, circle.origin]; magOriginToPoint _ GGVector.Magnitude[originToPoint]; IF magOriginToPoint < epsilon THEN { projectedPt _ [circle.origin[1] + circle.radius, circle.origin[2]]; RETURN; }; projectedPt _ GGVector.Add[circle.origin, GGVector.Scale[originToPoint, circle.radius/magOriginToPoint]]; }; CreateArc: PUBLIC PROC [v1, v2: Point] RETURNS [arc: Arc] = {}; CreateEmptyArc: PUBLIC PROC RETURNS [arc: Arc] = {}; FillArc: PUBLIC PROC [v1, v2: Point, arc: Arc] = {}; CopyArc: PUBLIC PROC [from: Arc, to: Arc] = {}; CirclePointOnArc: PUBLIC PROC [pt: Point, arc: Arc] RETURNS [BOOL] = { RETURN[FALSE]}; NearestEndpoint: PUBLIC PROC [pt: Point, arc: Arc] RETURNS [endpoint: Point] = {}; DistanceSquaredToNearestEndpoint: PUBLIC PROC [pt: Point, arc: Arc] RETURNS [distanceSquared: REAL] = {}; NearestPointOnArc: PUBLIC PROC [pt: Point, arc: Arc] RETURNS [onArc: Point] = {}; DistancePointToArc: PUBLIC PROC [pt: Point, arc: Arc] RETURNS [distance: REAL] = {}; DistanceSquaredPointToArc: PUBLIC PROC [pt: Point, arc: Arc] RETURNS [distanceSquared: REAL] = {}; END. îGGCirclesImpl.mesa Author: Eric Bier on June 4, 1985 4:58:33 pm PDT Last edited by Bier on August 19, 1985 4:40:54 pm PDT Contents: Routines for finding the intersections of various types of circles, lines, and points. Circles This procedures allocates a new Circle. Line: cy -sx - d = 0. (f(x) = 0) Circle: x2 + y2 = r2. (g(x) = 0) CircleMeetsEdge: PUBLIC PROC [circle: Circle, edge: Edge] RETURNS [intersection: Point, miss: BOOL] = {}; We drop a normal from the point onto the circle and find where it hits. Arcs Assumes pt is on edge.line. Is it on edge? Faster than DistancePointToPoint[pt, NearestEndpoint[pt, edge]] (if you don't care what the endpoint is). Perpendicular distance if possible, else distance to nearest endpoint. Ê+˜Ihead1™Iprocšœ0™0Lšœ5™5Lšœa™aL˜šÏk ˜ Lšœ4˜4—L˜šœœ˜Lšœ˜"Lšœ ˜—Lš˜L˜Lšœœ˜Lšœœœ ˜Lšœ œ˜)Lšœœ˜!Lšœœ˜Lšœœ˜šœœ˜#L˜L˜—L™L™L˜šÏnœœœœ˜>šœ œ˜Lšœ˜Lšœ ˜ Lšœ˜Lšœ˜——šž œœœ ˜7Lšœ˜Lšœ˜Lšœ˜—L˜šžœœœœ˜XLšœ˜Lšœ˜Lšœ˜—˜L™'—š žœœœœœ˜]Lšœ˜Lšœ1˜1Lšœ˜—L˜š žœœœœ œœ˜xLšœÏbœ™ Lš œ Ïuœ œ œŸœ™ Lšœ œ˜L˜ Lšœ4˜4Lšœœ˜Lšœ˜Lšœ ˜ šœÏc$˜9Lšœ ˜ LšœN˜NL˜—šœ¡˜)Lšœ ˜ LšœF˜FLšœ4˜4Lšœ(˜(Lšœ˜Lšœ˜L˜—Lšœœ˜Lšœ˜L˜—šž œœœœ˜4Lšœ œ ˜Lšœœœœ˜FL˜—š žœœœœ œœ˜xL˜Lšœ œ˜šœ-œ˜5Lšœ ˜ Lšœ˜L˜—Lšœ6˜6Lšœ'˜'Lšœ ˜Lšœ2˜2šœ&˜&Lšœ ˜ Lšœ2˜2LšœT˜TL˜—šœœJ˜QL˜ L˜Lšœ œ˜Lšœ ˜ Lšœ2˜2Lšœ6˜6LšœV˜VLšœ6˜6Lšœ?˜?Lšœ+˜+Lšœ$˜$Lšœ$˜$L˜—šœœ&˜+Lšœ ˜ šœ!œ˜)Lšœ2˜2LšœT˜TL˜—šœ˜Lšœ3˜3LšœT˜TL˜—L˜—šœœ&˜+Lšœ ˜ L˜—Lšœœ˜Lšœ˜—L˜Lšžœ œœœ™jL™šžœ œœœ˜TL˜LšœD˜DLšœ"˜"Lšœ˜—š žœœœœœ˜NLšœœ#˜*Lšœ˜—šžœœœœ˜cLšœG™GLšœ œ ˜L˜Lšœœ˜Lšœ0˜0Lšœ5˜5šœœ˜$LšœC˜CLšœ˜L˜—Lšœi˜iLšœ˜—L™J™L˜Lšž œœœœ˜@Lšžœœœœ˜5Lšžœœœ!˜5Lšžœœœ˜0š žœœœœœ˜GLšœœ˜Lšœ+™+—Lšžœœœœ˜SLš ž œœœœœ˜išžœœœœ˜QLšœi™i—š žœœœœ œ˜ULšœF™F—Lš žœœœœœ˜cL™Lšœ˜J˜J˜—…—æÿ