Amusements

The problem

Given three points , and . Find the center and radius of the circle passing through it.

Discussion

Three non-collinear points represent a unique circle on a unique plane. It is easy to construct the circle from 3 points by drawing perpendicular bisectors of any two chords. If the 3 points are not collinear, the bisectors should meet at the center of the circle.

Using vectors, it is possible to devise an algorithm to do this. However, an easier method will be substituting the three points into the general equation of the circle

and solving for , and . Center is and the radius is
.

Starightforward algorithm

This can be solved by substituting the three values in the above equation and solving the set of three simultaneous equations.

The solution to the above set of simultaneous equations yields that the equation of the circle passing through , and is given by equating the value of the following determinanat to zero:

A simpler algorithm

A modified algorithm is given below:

The task will be much simpler if we apply a linear transformation so that one of the points (say ) is , and now the constant term vanishes, and now there are only two variables and two unknowns. We can transform the co-ordinates back after solving.

So, transform , , to

and now the equations are

where

Now, we can solve for g and f here.

Finally, applying the tranformations back, the center is .

The following C function illustrates this algorithm.

#include <math.h>
#define TRUE 1
#define FALSE 0

int  /* Returns TRUE if it is a valid circle, FALSE if the points are collinear */
solve_3_points_circle (
   double  x1, double  y1, /* Point 1 */
   double  x2, double  y2, /* Point 2 */
   double  x3, double  y3, /* Point 3 */
   double* cx, double* cy, /* Center  */
   double* r               /* Radius  */
)
{
   double z1, z2, d;

   /* Apply the transforms */
   x1 -= x3;
   y1 -= y3;
   x2 -= x3;
   y2 -= y3;

   Temporary variables to avoid some computations */
   z1 = x1 * x1 + y1 * y1;
   z2 = x2 * x2 + y2 * y2;
   d = 2.0 * (x1 * y2 - x2 * y1);
   if (fabs(d) < 0.00000001) {
      return FALSE;
   }

   /* Calculate the center of the transformed circle */
   *cx = (y2 * z1 - y1 * z2)/d;
   *cy = (x1 * z2 - x2 * z1)/d;
   r = sqrt(*cx * *cx + *cy * *cy);

   /* Apply the transforms back */
   *cx += x3;
   *cy += y3;
   return TRUE;
}

Algorithm given by Plastock and Kalley

Plastock and Kalley gives the following formulae for solving this problem:

The center and the radius of a circle passing through the points ,
and , are given by:

where

These formulae can be used to find the parameters of the circle.

Solution by following the geometric construction

The line passing through and is

where

The perpendicular bisector of this line passes through and has a slope of .

So, the perpendicular bisector is

Similarly, the perpendicular bisector of the side passing through and is

where

Now, the center of the circle is the point of intersection of these two perpendicular bisectors. So, equating the right hand sides of the above two equations, and solving for x,