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:
http://home.pipeline.com/~hbaker1/FAQ-circumcircle.txt
(Please email any comments or corrections to hbaker1@pipeline.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 A0 and B0 and C