The Circumcircle of Three Points

The question for this post: given three unique points A, B and C on the 2D plane, can a circle be found that contains all three points? The short answer: yes. The long answer comprises the remainder of this post, and it's a lot of algebra.

The concept we will employ to find our circle is straightforward in principle. We saw in an earlier post how to find the bisector line between two points, using the property that points on the line are the same distance away from both points. Stated slightly differently, any point on the bisector line between points A and B must be equidistant from A and B. This is true three ways: points on the bisector line between points B and C are equidistant from B and C, and points on the bisector line between points C and A are equidistant from C and A. If we take any two of those lines, and find their point of intersection P, then that point must be equidistant from all three points A, B and C. This intersection point turns out to be the center of the circle that we seek.

In practice, it's going to take some messy algebra to get an expression for this center point P. We begin with the bisector line equations we derived a few posts back:

X = [(A_x + B_x) / 2] - [t / 2(A_x - B_x)]
Y = [(A_y + B_y) / 2] + [t / 2(A_y - B_y)]

To begin, we define a shorthand notation that will make the equations easier to work with. Let Sx_AB = A_x + B_x, and let Dx_AB = A_x - B_x, and equivalent expressions for y. We will also multiply through by 2. Our bisector equations become:

2X = Sx_AB - t / Dx_AB
2Y = Sy_AB + t / Dy_AB

These are the equations for the bisector of points A and B. We will need a second bisector. Either one will do, so I flipped a coin and it came up heads for the bisector of B and C:

2X = Sx_BC - u / Dx_BC
2Y = Sy_BC + u / Dy_BC

I use parameter u instead of t because the parameters for the two equations are independent and not necessarily equal. Now we have two equations each giving the value of 2X and 2Y, so we can set them equal to one another. This will let us solve for one of the two parameters:

SxAB - t / DxAB = SxBC - u / DxBC t / DxAB - SxAB = u / DxBC - SxBC t / DxAB = u / DxBC + SxAB - SxBC t / DxAB = u / DxBC + DxAC t = (DxAB / DxBC)u + DxACDxAB

SyAB + t / DyAB = SyBC + u / DyBC t / DyAB = u / DyBC + SyBC - SyAB t / DyAB = u / DyBC + DyCA t = (DyAB / DyBC)u + DyCADyAB

We can then smush these two equations together and solve for the other parameter:

(Dx_AB / Dx_BC)u + Dx_ACDx_AB = (Dy_AB / Dy_BC)u + Dy_CADy_AB
(Dx_AB / Dx_BC - Dy_AB / Dy_BC)u = Dy_CADy_AB - Dx_ACDx_AB
[(Dx_ABDy_BC - Dx_BCDy_AB) / Dx_BCDy_BC]u = Dy_CADy_AB - Dx_ACDx_AB
u = Dx_BCDy_BC(Dy_CADy_AB - Dx_ACDx_AB) / (Dx_ABDy_BC - Dx_BCDy_AB)

Let G equal the denominator of that monster expression, Dx_ABDy_BC - Dx_BCDy_AB, just for shorthand. We can then sub in this expression for u into the bisector equations whence it came:

2GX = Sx_BCG - Dy_BC(Dy_CADy_AB - Dx_ACDx_AB)
2GY = Sy_BCG + Dx_BC(Dy_CADy_AB - Dx_ACDx_AB)

Are we done? Only if you are happy with part marks: there is likely opportunity to simplify these expressions more. Before we do that, though, the denominator G bears some investigation. Observe that Dx_AB = - Dx_BA, so we can rewrite this as:

G = Dx_CBDy_AB - Dx_ABDy_CB

We've seen this expression before: it is the test for colinearity that we derived in the first post of this series! Since we have to divide by this quantity in order to find the value for X and Y, this observation has an important consequence: we can find a circle containing three distinct points if, and only if, they are not colinear.

Now we will simplify the expressions. They are getting a bit unwieldy, so we will tackle them one at a time, starting with the expression for X:

2GX = Sx_BCG - Dy_BC(Dy_CADy_AB - Dx_ACDx_AB)
2GX = Sx_BCG + Dy_BCDx_ACDx_AB - Dy_ABDy_BCDy_CA
2GX = Sx_BCG + Dy_BCDx_ACDx_AB + Dy_ACDy_CBDy_BA

I will break down each of the three products individually:

SxBCG = (Bx + Cx)[Ax(By - Cy) + Bx(Cy - Ay) + Cx(Ay - By)] = AxBx(By - Cy) + Bx2(Cy - Ay) + BxCx(Ay - By) + AxCx(By - Cy) + BxCx(Cy - Ay) + Cx2(Ay - By) = (By - Cy)(AxBx + AxCx) + BxCx(Ay - By + Cy - Ay) + Bx2(Cy - Ay) + Cx2(Ay - By) = (By - Cy)(AxBx + AxCx) + BxCx(Cy - By) + Bx2(Cy - Ay) + Cx2(Ay - By) = (AxBx - BxCx + CxAx)(By - Cy) + Bx2(Cy - Ay) + Cx2(Ay - By)

DyBCDxACDxAB = (By - Cy)(Ax - Cx)(Ax - Bx) = (By - Cy)(Ax2 - AxBx - AxCx + BxCx) = Ax2(By - Cy) - (AxBx - BxCx + CxAx)(By - Cy)

DyACDyCBDyBA = (Ay - Cy)(Cy - By)(By - Ay) = (Ay - Cy)(ByCy - By2 - AyCy + AyBy) = AyByCy - AyBy2 - Ay2Cy + Ay2By - ByCy2 + By2Cy + AyCy2 - AyByCy = Ay2By - Ay2Cy + By2Cy - AyBy2 + AyCy2 - ByCy2 = Ay2(By - Cy) + By2(Cy - Ay) + Cy2(Ay - By)

Note the cancellation of terms between the first and second products.

Next, we simplify the expression for Y using a similar approach:

2GY = Sy_BCG + Dx_BC(Dy_CADy_AB - Dx_ACDx_AB)
2GY = Sy_BCG + Dx_BCDy_CADy_AB - Dx_BCDx_ACDx_AB
2GY = Sy_BCG + Dx_BCDy_CADy_AB + Dx_BCDx_CADx_AB

And again, I will break down each product individually:

SyBCG = (By + Cy)[Cy(Bx - Ax) + By(Ax - Cx) + Ay(Cx - Bx)] = ByCy(Bx - Ax) + By2(Ax - Cx) + AyBy(Cx - Bx) + Cy2(Bx - Ax) + ByCy(Ax - Cx) + AyCy(Cx - Bx) = ByCy(Bx - Ax + Ax - Cx) + (AyBy + AyCy)(Cx - Bx) + By2(Ax - Cx) + Cy2(Bx - Ax) = (AyBy - ByCy + CyAy)(Cx - Bx) + By2(Ax - Cx) + Cy2(Bx - Ax)

DxBCDyCADyAB = (Bx - Cx)(Cy - Ay)(Ay - By) = (Cx - Bx)(Ay - Cy)(Ay - By) = (Cx - Bx)(Ay2 - AyBy - AyCy + ByCy) = Ay2(Cx - Bx) - (AyBy - ByCy + CyAy)(Cx - Bx)

DxBCDxCADxAB = (Bx - Cx)(Cx - Ax)(Ax - Bx) = (Bx - Cx)(AxCx - BxCx - Ax2 + AxBx) = AxBxCx - Bx2Cx - Ax2Bx + AxBx2 - AxCx2 + BxCx2 + Ax2Cx - AxBxCx = Ax2Cx - Ax2Bx + AxBx2 - Bx2Cx + BxCx2 - AxCx2 = Cx2(Bx - Ax) + Bx2(Ax - Cx) + Ax2(Cx - Bx)

Here, as in the case for the X-coordinate, there is some cancellation between the first and second product.

---

To summarize (because there's been enough algebra to warrant it): given three distinct, non-colinear points A, B and C, there exists a unique circle containing all three points, and its center is given by the following equations:

G = det(

Ax	Ay	1
Bx	By	1
Cx	Cy	1

)

X = [(A_x² + A_y²)(B_y - C_y) + (B_x² + B_y²)(C_y - A_y) + (C_x² + C_y²)(A_y - B_y)] / 2G
Y = [(C_x² + C_y²)(B_x - A_x) + (B_x² + B_y²)(A_x - C_x) + (A_x² + A_y²)(C_x - B_y)] / 2G

There are two particular expressions of G which have a pleasing symmetry with these two equations:

G_x = A_x(B_y - C_y) + B_x(C_y - A_y) + C_x(A_y - B_y)
G_y = C_y(B_x - A_x) + B_y(A_x - C_x) + A_y(C_x - B_x)