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: Circle Through 3 Points
Message-ID: <207400008@s.cs.uiuc.edu>
Date: 10 Aug 89 23:20:14 GMT
Lines: 41
Nf-ID: #N:s.cs.uiuc.edu:207400008:000:1149
Nf-From: s.cs.uiuc.edu!mccaugh    Aug  9 14:26: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):


     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.