Introduction

In computational geometry, determining the center of a circle that passes through three given non-collinear points is a fundamental problem. It appears in computer graphics, geographic information systems, robotics, and mesh generation. The solution uses the concept of perpendicular bisectors: the center of the circle (circumcenter) lies at the intersection of the perpendicular bisectors of any two sides of the triangle formed by the three points.

Conceptual Overview

Given three non-collinear points $A(x_1, y_1)$, $B(x_2, y_2)$, and $C(x_3, y_3)$, these points define a unique circle called the circumcircle. The center of this circle, the circumcenter, is equidistant from all three points. The key geometric property is that the perpendicular bisector of a chord always passes through the center of the circle, so the intersection of any two perpendicular bisectors gives us the circumcenter.

Algorithm Steps

1. Calculate midpoints of two sides of the triangle.
2. Determine slopes of those two sides.
3. Compute perpendicular slopes (negative reciprocal of each side's slope).
4. Write equations of the perpendicular bisectors using point-slope form.
5. Solve the system of two linear equations to find the intersection point (the circumcenter).

Step-by-Step Example

Given points: $A(1, 2)$, $B(4, 6)$, $C(5, 1)$.

Step 1: Midpoints

The midpoint formula is:

$$M_{XY} = \left(\frac{x_1 + x_2}{2}, \frac{y_1 + y_2}{2}\right)$$

• Midpoint of $AB$: $M_{AB} = \left(\frac{1+4}{2}, \frac{2+6}{2}\right) = (2.5, 4)$
• Midpoint of $BC$: $M_{BC} = \left(\frac{4+5}{2}, \frac{6+1}{2}\right) = (4.5, 3.5)$

Step 2: Slopes of the Sides

The slope formula is:

$$m = \frac{y_2 - y_1}{x_2 - x_1}$$

• Slope of $AB$: $m_{AB} = \frac{6 - 2}{4 - 1} = \frac{4}{3}$
• Slope of $BC$: $m_{BC} = \frac{1 - 6}{5 - 4} = -5$

Step 3: Perpendicular Slopes

The perpendicular slope is the negative reciprocal:

$$m_{\perp} = -\frac{1}{m}$$

• Perpendicular to $AB$: $m_{\perp AB} = -\frac{3}{4}$
• Perpendicular to $BC$: $m_{\perp BC} = \frac{1}{5}$

Step 4: Equations of Perpendicular Bisectors

Using point-slope form $(y - y_0) = m(x - x_0)$:

Bisector of $AB$ through $M_{AB}(2.5, 4)$:

$$y - 4 = -\frac{3}{4}(x - 2.5)$$

$$y = -\frac{3}{4}x + \frac{15}{8} + 4 = -\frac{3}{4}x + \frac{47}{8}$$

Bisector of $BC$ through $M_{BC}(4.5, 3.5)$:

$$y - 3.5 = \frac{1}{5}(x - 4.5)$$

$$y = \frac{1}{5}x - \frac{9}{10} + \frac{7}{2} = \frac{1}{5}x + \frac{13}{5}$$

Step 5: Solve for Intersection

Setting the two equations equal:

$$-\frac{3}{4}x + \frac{47}{8} = \frac{1}{5}x + \frac{13}{5}$$

Multiply through by 40 to clear fractions:

$$-30x + 235 = 8x + 104$$

$$38x = 131$$

$$x = \frac{131}{38} \approx 3.447$$

Substituting back:

$$y = \frac{1}{5} \cdot \frac{131}{38} + \frac{13}{5} = \frac{131}{190} + \frac{494}{190} = \frac{625}{190} \approx 3.289$$

The circumcenter is at approximately $(3.45, 3.29)$.

Direct Formula (Determinant Method)

For implementation, a more robust approach avoids slope calculations (which fail for vertical lines) by solving the system directly. The circumcenter $(h, k)$ satisfies:

$$(x_1 - h)^2 + (y_1 - k)^2 = (x_2 - h)^2 + (y_2 - k)^2 = (x_3 - h)^2 + (y_3 - k)^2$$

Expanding and rearranging yields a linear system that can be solved with:

1def circumcenter(x1, y1, x2, y2, x3, y3):
2    ax, ay = x1 - x3, y1 - y3
3    bx, by = x2 - x3, y2 - y3
4
5    D = 2 * (ax * by - ay * bx)
6    if abs(D) < 1e-10:
7        raise ValueError("Points are collinear")
8
9    ux = (by * (ax**2 + ay**2) - ay * (bx**2 + by**2)) / D
10    uy = (ax * (bx**2 + by**2) - bx * (ax**2 + ay**2)) / D
11
12    return (ux + x3, uy + y3)

This method is numerically stable and handles all non-degenerate cases.

Key Formulas Summary

Edge Cases

• Collinear points: If all three points lie on a straight line, no unique circle exists. The determinant $D$ in the formula above will be zero (or near zero). Your implementation should detect this and handle it as an error.
• Vertical or horizontal sides: The slope-based approach fails when a side is vertical (undefined slope). The determinant method avoids this problem entirely.
• Nearly collinear points: When points are close to collinear, the circumradius becomes very large and numerical precision suffers. Consider using higher-precision arithmetic for such cases.

Summary

Finding the center of a circle through three points reduces to finding the intersection of two perpendicular bisectors. While the geometric approach (midpoints, slopes, bisectors) is intuitive, the determinant-based formula is more robust for implementation since it avoids division-by-zero issues with vertical lines. The algorithm runs in $O(1)$ time and is a building block for larger geometric algorithms like Delaunay triangulation and Voronoi diagrams.