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.
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;
Circles
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;
};
This procedures allocates a new Circle.
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]] = {
Line: cy -sx - d = 0. (f(x) = 0)
Circle: x2 + y2 = r2. (g(x) = 0)
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;
};
CircleMeetsEdge: PUBLIC PROC [circle: Circle, edge: Edge] RETURNS [intersection: Point, miss: BOOL] = {};
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] = {
We drop a normal from the point onto the circle and find where it hits.
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]];
};
Arcs
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]};
Assumes pt is on edge.line. Is it on edge?
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] = {};
Faster than DistancePointToPoint[pt, NearestEndpoint[pt, edge]] (if you don't care what the endpoint is).
DistancePointToArc:
PUBLIC
PROC [pt: Point, arc: Arc]
RETURNS [distance:
REAL] = {};
Perpendicular distance if possible, else distance to nearest endpoint.
DistanceSquaredPointToArc: PUBLIC PROC [pt: Point, arc: Arc] RETURNS [distanceSquared: REAL] = {};
END.