Path: utzoo!attcan!uunet!dino!uxc.cso.uiuc.edu!uxc.cso.uiuc.edu!m.cs.uiuc.edu!s.cs.uiuc.edu!mccaugh
From: mccaugh@s.cs.uiuc.edu
Newsgroups: comp.graphics
Subject: Re: Circle Through 3 Points
Message-ID: <207400012@s.cs.uiuc.edu>
Date: 12 Aug 89 23:01:58 GMT
References: <207400008@s.cs.uiuc.edu>
Lines: 53
Nf-ID: #R:s.cs.uiuc.edu:207400008:s.cs.uiuc.edu:207400012:000:2182
Nf-From: s.cs.uiuc.edu!mccaugh    Aug 11 13:49:00 1989


 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*);