mccaugh@s.cs.uiuc.edu (08/11/89)
More should be said about point 3 (all points being collinear (co-linear?)): Even when m1 <> m2, if these two slopes are "very close" a "very large" radius is called for, which may force the circle's center (s,t) outside the viewing area. For that matter, overflow can occur in the divisions of succeeding steps computing s and t. Therefore, it is prudent to check for m1 "close to" m2 as well as for equality, though "closeness" is relative to the user's system.
mccaugh@s.cs.uiuc.edu (08/11/89)
Re: the request for an algorithm to obtain the circle passing through 3 given
points A = (x1,y1); B = (x2,y2); C = (x3,y3):
1. points of intersection between perpendicular-bisectors and sides are:
u1 = (x1 + x2)/2; v1 = (y1 + y2)/2; (lies on side AB)
u2 = (x2 + x3)/2; v2 = (y2 + y3)/2; (lies on side BC)
2. slopes of the 2 perpendicular-bisectors (to sides AB and BC) are:
m1 = -(x2 - x1)/(y2 - y1); m2 = -(x3 - x2)/(y3 - y2)
3. If m1 = m2, then the 3 points are collinear. Otherwise:
4. Slope-Intercept Equations of the 2 perpendicular-bisectors are:
t = m1*s - (m1*u1 - v1); t = m2*s - (m2*u2 - v2)
where common point of their intersection = (s,t) is the center
of the desired circle;
5. Solving for s,t:
s = (m1*u1 - m2*u2 - (v1 - v2))/(m1 - m2);
t = (m1*m2*(u1 - u2) + m1*v2 - m2*v1)/(m1 - m2)
6. Then the radius r is obtained from:
s_x1 = s - x1; t_y1 = t - y1;
r = sqrt(s_x1*s_x1 + t_y1*t_y1)
7. Finally, return center (s,t) and radius r.mccaugh@s.cs.uiuc.edu (08/13/89)
Re: the request for an algorithm to obtain the circle passing through 3 given
points A = (x1,y1); B = (x2,y2); C = (x3,y3):
Following is one possible solution programmed in PASCAL:
(* assuming: TYPE point = RECORD x,y: real END{point}; *)
(* assuming: neither line-segments AB nor BC are horizontal *)
PROCEDURE EnCircle (A,B,C:point; VAR error:Boolean);
(* error = True iff can not do *)
VAR x1,y1, x2,y2, x3,y3, (* 3 given points to encircle *)
u1,v1, u2,v2, (* intersections with _|_ bisectors *)
m1,m2: (* slopes of _|_ bisectors *)
real;
s,t, r: word; (* graphic coordinates of center and radius *)
error: Boolean;
BEGIN
error := False; (* until infinite radius or out-of-bounds *)
x1 := A.x; y1 := A.y;
x2 := B.x; y2 := B.y;
x3 := C.x; y3 := C.y;
(* points of intersection between perpendicular-bisectors and sides *)
u1 := (x1 + x2)*0.5; v1 := (y1 + y2)*0.5; (*lies on side AB*)
u2 := (x2 + x3)*0.5; v2 := (y2 + y3)*0.5; (*lies on side BC*)
(* slopes of the 2 perpendicular-bisectors (to sides AB and BC) *)
(* by 2nd assumption, y1 <> y2 and y2 <> y3 => no division by 0 *)
m1 := -(x2 - x1)/(y2 - y1); m2 := -(x3 - x2)/(y3 - y2);
(* m1 = m2 implies the 3 points are collinear *)
IF m1 = m2 THEN error := True (* i.e., infinite radius *)
ELSE BEGIN
(* common point of intersection (s,t) = center of circle *)
s := Round( (m1*u1 - m2*u2 - (v1 - v2))/(m1 - m2) );
t := Round( (m1*m2*(u1 - u2) + m1*v2 - m2*v1)/(m1 - m2) );
(* then the radius r is obtained from: *)
r := Round( Sqrt(Sqr(s-x1) + Sqr(t-y1)) );
(* ready to plot the circle through points A,B,C: *)
IF (MIN_X <= s-r) AND (s+r <= MAX_X) AND
(MIN_Y <= t-r) AND (t+r <= MIN_Y) THEN
Circle(s,t,r)
ELSE error := True
END
END(*EnCircle*); sprague@hpfcda.HP.COM (Fred Sprague) (08/14/89)
Nice algorythm for a circle passing through 3 points. Now do you have an equation for a circle/arc passing through 3 points in 3D space? Answer must be in terms that will allow drawing the circle/arc (in "n" small segments ) from point 1 through point 2 to point 3. I'm no math expert, but I've tried this problem several times and still have not come up with the kind of answer I'm looking for.