Draft FAQ:

How to compute the center & radius of the circumcircle given 3 points:
complex can be less complicated than real

Henry G. Baker

January, 1997

Copyright (c) 1997 by Henry G. Baker.  All rights reserved.

This FAQ can be found at URL:
ftp://ftp.netcom.com/pub/hb/hbaker/FAQ-circumcircle.txt

(Please email any comments or corrections to hbaker@netcom.com.)

High school geometry tells us that the _circumcircle_ is the circle
that touches the 3 vertices of a triangle.  Furthermore, it gives a
construction for finding the center and radius of this circle -- the
center is the intersection of the perpendicular bisectors of the 3
sides of the triangle, and the radius is the distance between that
center and any of the three vertices of the triangle.  Unfortunately,
this construction is not necessarily the best or most efficient method
for finding the center and radius.  In this note we examine several
different methods and compare them.


Notation
--------

Since this is an ASCII text file, we will be very sparing of diagrams,
and will use no greek symbols.

            C
            /|\
           /  \
        b /    \ a
         /  O   \
        /        \
       |/________\
     A      c    / B

(Contrary to the diagram, this triangle is not necessarily isosceles.)

We denote the vertex _points_ at the three corners of the triangle by
A, B, C.  By an abuse of notation, we also use A, B, C to denote the
_coordinates_ of these three points -- i.e., A=(Ax,Ay), B=(Bx,By),
C=(Cx,Cy).  Further abuse of the notation gives us the _vectors_ A, B,
C from the origin.  Additional abuses of the notation provide the
_complex numbers_ A=Ax+iAy, B=Bx+iBy, C=Cx+iCy, and the _angles_
A=CAB, B=ABC, C=BCA.

We denote the `circumcenter' (center of the circumcircle) point by the
letter O=(Ox,Oy).  As before, O is also both a vector and a complex
number.

We follow tradition by labelling the (directed) sides _opposite_ to
vertices/angles A, B, C, as the lines/vectors a, b, c.  By an abuse of
notation, these sides are the _vectors_ a=C-B, b=A-C, c=B-A, as well
as the _complex numbers_ a=C-B, b=A-C, c=B-A.  We note also that A, B,
C and a, b, c occur in _cyclic_ counterclockwise order, so that
a+b+c=0.

The _lengths_ of the sides a, b, c are denoted by |a|, |b|, |c|,
respectively.  Since a, b, c are _vectors_, they inherit the `dot' and
`cross' products:

a.b = ax bx + ay by = - |a| |b| cos C, etc.

a X b = ax by - ay bx = - |a| |b| sin C, etc.

Nota Bene -- The minus (-) signs above come from our cyclic choice of
directions for the vectors a, b, c.  (Yes, I know that this is not the
usual 3D definition of `cross product'; you'll just have to get over
it.)

Complex numbers such as (the point) A=Ax+iAy or (the side) a=ax+iay
may have _conjugates_; these are denoted by A'=Ax-iAy and a'=ax-iay,
respectively.  Note that

|a|^2 = aa' = (a.a) and |A|^2 = AA' = (A.A), etc.

Thus, we can compute the `dot' and `cross' products for complex
numbers as follows:

ab' = (ax+iay)(bx-iby)
    = (ax bx + ay by) - i(ax by - ay bx)
    = (a.b) - i (a X b)

a.b = (ab'+a'b)/2         (ab'+a'b = a.b - i aXb + a.b + i aXb = 2 a.b)

a X b = i(ab'-a'b)/2      (ab'-a'b = a.b - i aXb - a.b - i aXb = -2i aXb)

Note that

(ia) X (ib) = i(ia(ib)'-(ia)'ib)/2
            = i(ia(-ib')-(-ia')ib)/2
            = i(ab'-a'b)/2
            = a X b

and also that

a X (ib) = i(a(ib)'-a'ib)/2
         = i(a(-ib')-ia'b)/2
         = i(-iab'-ia'b)/2
         = (ab'+a'b)/2
         = a.b

The (signed) _radius_ of the circumcircle we denote by R, and the
(signed) _area_ of the triangle by T.  Note the classic formula for
the radius of the circumcircle (which we will prove below):

R = |a||b||c|/(4T)

The sign of the circumcircle radius is the same as the sign of the
triangle area, and will indicate whether the circle is
counterclockwise (+) or clockwise (-).  Note that if the 3 vertices A,
B, C are collinear, the area T of the triangle is zero, and the radius
R is infinite (oo).

Note that a classic method of computing the area T of the triangle is
the `determinant' method:

      |Ax Ay 1|
2 T = |Bx By 1| = BxCy-ByCx-AxCy+AyCx+AxBy-AyBx
      |Cx Cy 1|

An equivalent vector method for computing the area T is:

2 T = b X (-a)
    = -(b X a)
    = a X b               (or bXc or cXa, in the cyclic ordering)
    = ax by - ay bx
    = (Cx-Bx)(Ay-Cy)-(Cy-By)(Ax-Cx)
    = CxAy+BxCy-BxAy-CxCy-CyAx-ByCx+CyCx+ByAx
    = BxCy-ByCx-AxCy+AyCx+AxBy-AyBx

For example, the triangle with corners (1,0), (2,0), (1,1) has area

          |1 0 1|
T = (1/2) |2 0 1| = 1/2
          |1 1 1|

The radius R of the circumcircle for this triangle is

R = |a||b||c|/(4T) = (1 1 sqrt(2))/2 = sqrt(2)/2,

which is correct, since the circumcenter is (1/2,1/2).


Perpendicular Bisectors of the Sides
------------------------------------

We will compute the intersection of the perpendiculars to the
midpoints of the sides a and b.

The midpoint of the side a is (B+C)/2.  The vector perpendicular to
the side a is the vector ia.  Thus, the line perpendicular to the side
a at the midpoint (B+C)/2 is the expression with the parameter t:

(B+C)/2 + t ia = (B+C)/2 + t i (C-B)

The midpoint of the side b is (C+A)/2.  The vector perpendicular to
the side b is the vector ib.  Thus, the line perpendicular to the side
b at the midpoint (C+A)/2 is the expression with the parameter u:

(C+A)/2 + u ib = (C+A)/2 + u i (A-C)

These expressions give the same point O when

(B+C)/2 + t ia = (C+A)/2 + u ib = O

Rearranging, we get:

t ia - u ib = (C+A)/2 - (B+C)/2
            = (A-B)/2
            = -c/2

Multiplying both sides by -i gives

t a - u b = ic/2            (I)

To solve for (real) t,u, we utilize the properties of the complex
numbers.  Multiplying I by b' gives

t ab' - u bb' = icb'/2      (II)

Multiplying I' by b gives (t=t', u=u' since t,u are real)

t a'b - u b'b = -ic'b/2     (III)

Subtracting III from II gives

t (ab'-a'b) - u (bb'-bb') = i(cb'+c'b)/2

hence

- t 2 i (aXb) = i (c.b)

and

t = (b.c)/(-2 aXb)
  = (b.c)/(-4T)             (t is real, and + if T>0 and A<pi/2)
  = (R cos A)/|a|           (b.c = -|b||c| cos A)

Similarly, multiplying I by a' gives

t aa' - u ba' = ica'/2      (IV)

Multiplying I' by a gives

t a'a - u b'a = -ic'a/2     (V)

Subtracting V from IV gives

t (aa'-aa') - u (ba'-b'a) = i(ca'+c'a)/2

Hence

2 u i bXa = i(c.a)

and

-2 u aXb = (a.c)

and

u = (a.c)/(-2 aXb)
  = (a.c)/(-4T)             (u is real, and + if T>0 and B<pi/2)
  = (R cos B)/|b|           (a.c = -|a||c| cos B)

By symmetry, we can compute v, where O = (A+B)/2 + v ic as

v = (a.b)/(-4T)             (v is real, and + if T>0 and C<pi/2)
  = (R cos C)/|c|

Now (t,u,v) are _almost_ the barycentric coordinates of the point O.
Consider t.  It will be multiplied once by |a| in reaching O from
(B+C)/2 because the length of ia is |ia|=|a|.  If we multiply t|a|
again by |a|, then we will have the _area_ of OBC, which is the first
barycentric coordinate of O -- i.e., that corresponding to the vertex
A.  Similarly, u must be multiplied by |b|^2 and v must be multiplied
by |c|^2.  So the barycentric coordinates for O are:

O = (t|a|^2, u|b|^2, v|c|^2)

  = (|a|^2 (b.c), |b|^2 (a.c), |c|^2 (a.b))/(-4T)

  = ((a.a)(b.c), (b.b)(a.c), (c.c)(a.b))/(-4T)

  = (-|a||a||b||c|cos A, -|b||a||b||c|cos B, -|c||a||b||c|cos C)/(-4T)

  = (|a|cos A, |b|cos B, |c|cos C) (|a||b||c|)/(4T)

  = R (|a|cos A, |b|cos B, |c|cos C)      (a useful barycentric formula)

  = (|a|R cos A, |b|R cos B, |c|R cos C)

  = ((2R sin A)(R cos A), (2R sin B)(R cos B), (2R sin C)(R cos C))

  = (R^2 2 sin A cos A, R^2 2 sin B cos B, R^2 2 sin C cos C)

  = R^2 (sin 2A, sin 2B, sin 2C)    (another useful barycentric formula)

and therefore the Cartesian coordinates for O are:

O = (aa'(b.c)A + bb'(a.c)B + cc'(a.b)C)/(-4T)

  = ((a.a)(b.c)A + (b.b)(a.c)B + (c.c)(a.b)C)/(-4T)

For example, if A=(1,0), B=(2,0), C=(1,1), then a=C-B=(-1,1),
b=A-C=(0,-1), c=B-A=(1,0) and

O = ((2)(0)A + (1)(-1)B + (1)(-1)C)/(-2)
  = ((2)(0)(1,0) + (1)(-1)(2,0) + (1)(-1)(1,1))/(-2)
  = ((-2,0) + (-1,-1))/(-2)
  = (-3,-1)/(-2)
  = (3/2,1/2)


Real Determinant Method
-----------------------

A classic method for computing the equation of the circumcircle that
goes through the 3 points A, B, C is the following `determinant'
method:

|x^2+y^2   x  y  1|
|Ax^2+Ay^2 Ax Ay 1|
|Bx^2+By^2 Bx By 1| = 0.
|Cx^2+Cy^2 Cx Cy 1|

We notice is that the coefficient of (x^2+y^2) is twice the area of
the triangle (2T).  Thus, the equation is no longer a circle if the
area of the triangle is zero.

We note that the coefficients of x and y are related to the
coordinates of the circumcenter as follows:

Ox = -coeff(x)/(2 coeff(x^2+y^2)) = -coeff(x)/(4T)

Oy = -coeff(y)/(2 coeff(x^2+y^2)) = -coeff(y)/(4T)

So,

           |Ax^2+Ay^2 Ay 1|
-4T Ox = - |Bx^2+By^2 By 1| and
           |Cx^2+Cy^2 Cy 1|

           |Ax^2+Ay^2 Ax 1|
-4T Oy = + |Bx^2+By^2 Bx 1|
           |Cx^2+Cy^2 Cx 1|

Since Ax^2+Ay^2=AA', etc., we can rewrite these expressions as:

           |AA' Ay 1|
-4T Ox = - |BB' By 1| and
           |CC' Cy 1|

           |AA' Ax 1|
-4T Oy = + |BB' Bx 1|
           |CC' Cx 1|

Expanding, we get:


-4T Ox = -BB'Cy+CC'By+AA'Cy-CC'Ay-AA'By+BB'Ay
       = AA'(Cy-By)+BB'(Ay-Cy)+CC'(By-Ay)
       = AA'ay + BB'by + CC'cy

-4T Oy = BB'Cx-CC'Bx-AA'Cx+CC'Ax+AA'Bx-BB'Ax
       = AA'(Bx-Cx)+BB'(Cx-Ax)+CC'(Ax-Bx)
       = AA'(-ax)+BB'(-bx)+CC'(-cx)
       = -AA'ax - BB'bx - CC'cx

So, putting O=Ox+iOy together as a complex number, we get:

-4T O = AA'(ay-iax)+BB'(by-ibx)+CC'(cy-icx)
      = AA'(-ia)+BB'(-ib)+CC'(-ic)
      = -i (AA'a+BB'b+CC'c)

And we finally get:

O = i (AA'a+BB'b+CC'c)/(4T)

For example, if A=(1,0), B=(2,0), C=(1,1), we get

O = i (a+4b+2c)/2
  = i ((C-B)+4(A-C)+2(B-A))/2
  = i (C-B+4A-4C+2B-2A)/2
  = i (2A+B-3C)/2
  = i (2+2-3-3i)/2
  = i (1-3i)/2
  = (3+i)/2
  = (3/2,1/2)


Complex Determinant Method
--------------------------

The equation for a circle in complex numbers is

(z-O)(z-O)'-R^2  = 0
                 = (z-O)(z'-O')-R^2
                 = zz'-O'z-Oz'+(OO'-R^2).

If we compute the determinant

|zz' z z' 1|
|AA' A A' 1|
|BB' B B' 1| = 0,
|CC' C C' 1|

we will get an equation for the circumcircle through the three points
A, B, C.

We notice that the coefficient of zz' is the determinant

|A A' 1|   |A A' 1||1/2 -i/2 0||1  1 0|
|B B' 1| = |B B' 1||1/2  i/2 0||i -i 0| 
|C C' 1|   |C C' 1|| 0    0  1||0  0 1|

           |Ax Ay 1||1  1 0|
         = |Bx By 1||i -i 0| 
           |Cx Cy 1||0  0 1|

         = 2 T (-2i)

         = -4iT

         = BC'-CB'-AC'+CA'+AB'-BA'

         = A'(C-B)+B'(A-C)+C'(B-A)

         = A'a+B'b+C'c

Now, we can compute O from the coefficients of z' and zz' as follows:

O = - coeff(z')/coeff(zz')

      |AA' A 1|
  = - |BB' B 1|/(-4iT)
      |CC' C 1|

  = - (BB'C-CC'B-AA'C+CC'A+AA'B-BB'A)/(-4iT)

  = - (AA'(B-C)+BB'(C-A)+CC'(A-B))/(-4iT)

  = - (AA'(-a)+BB'(-b)+CC'(-c))/(-4iT)

  = (AA'a+BB'b+CC'c)/(-4iT)

  = i (AA'a+BB'b+CC'c)/(4T)

  = (AA'a+BB'b+CC'c)/(A'a+B'b+C'c)

In other words, we get the same result working with complex numbers,
but we obtain it easier than with real numbers.


Computing the Radius of the Circumcircle
----------------------------------------

The circumradius R of the circumcircle is the absolute value of the
difference between the circumcenter O and any one of the vertices A,
B, or C.  First compute O-A:

O-A = (AA'a+BB'b+CC'c)/(A'a+B'b+C'c) - A

    = (AA'a+BB'b+CC'c-A(A'a+B'b+C'c))/(A'a+B'b+C'c)

    = (AA'a+BB'b+CC'c-AA'a-AB'b-AC'c)/(-4iT)

    = (BB'b+CC'c-AB'b-AC'c)/(-4iT)

    = ((B-A)B'b+(C-A)C'c)/(-4iT)

    = (B'bc+(-b)C'c)/(-4iT)

    = (B'bc-C'bc)/(-4iT)

    = ((B'-C')bc)/(-4iT)

    = ((-a')bc)/(-4iT)

    = a'bc/(4iT)     (similarly for O-B and O-C.)

Then

R^2 = (O-A)(O-A)'

    = [a'bc/(4iT)][a'bc/(4iT)]'

    = [a'bc/(4iT)][ab'c'/(-4iT)]

    = (a'bcab'c')/(-16iiTT)

    = (aa'bb'cc')/(16T^2)

and so

R = |a||b||c|/(4T)

as promised.


References
----------

Neumann, Peter M., Stoy, Gabrielle A., and Thompson, Edward C.  Groups
and Geometry.  Oxford University Press, 1994, ISBN 0-19-853451-5.

Pedoe, Dan.  Geometry: A Comprehensive Course.  Dover, New York, 1970.
ISBN 0-486-65812-0.

Schwerdtfeger, Hans.  Geometry of Complex Numbers: Circle Geometry,
Moebius Transformation, Non-Euclidean Geometry.  Dover, New York,
1979.  ISBN 0-486-63830-8.

Thomas, Jr., George B.  Calculus and Analytic Geometry.
Addison-Wesley, Reading, MA, 1960.  Library of Congress No. 60-5015.