10
$\begingroup$

let there be three points in $\mathbb{R}^2$, $(x_1,y_1)$, $(x_2,y_2)$, and $(x_3,y_3)$. I want to find the area of the circle that passes through all three points?

I can find the circle by: $$ \begin{cases} (x_1 - x_c)^2 + (y_1 - y_c)^2 - r^2\\ (x_2 - x_c)^2 + (y_2 - y_c)^2 - r^2 \\ (x_3 - x_c)^2 + (y_3 - y_c)^2 - r^2 \end{cases} $$

isolate $y_c$ and $x_c$ as a function of the isolated $y_c$:

$$\begin{cases} (x_2 - x_c)^2 - (x_1 - x_c)^2 + (y_2 - y_c)^2 - (y_1 - y_c)^2 = 0\\ (x_3 - x_c)^2 - (x_1 - x_c)^2 + (y_3 - y_c)^2 - (y_1 - y_c)^2 = 0 \end{cases}$$

$$\begin{cases} x_2^2 - 2x_2x_c + x_c^2 - x_1^2 + 2x_1x_c- x_c^2 + (y_2 - y_c)^2 - (y_1 - y_c)^2 = 0\\ x_3^2 - 2x_3x_c + x_c^2 - x_1^2 + 2x_1x_c- x_c^2 + (y_3 - y_c)^2 - (y_1 - y_c)^2 = 0 \end{cases}$$

$$\begin{cases} x_c = \frac{(y_1 - y_c)^2 - (y_2 - y_c)^2 - (x_2^2 - x_1^2)}{2(x_1 - x_2)}\\ x_c = \frac{(y_1 - y_c)^2 - (y_3 - y_c)^2 - (x_3^2 - x_1^2)}{2(x_1 - x_3)} \end{cases}$$

$$ y_c= \frac{(x_3x_1 + y_2^2)(x_1 - x_3) + (x_1x_2 + y_3^2)(x_2 - x_1) + (x_2x_3 + y_1^2)(x_3 - x_2)}{2[(y_1 - y_3)(x_1 - x_2) - (y_1 - y_2)(x_1 - x_3)]} $$

From here, we can calculate $x_c$, $y_c$, and $r^2$. Then, the area of the circle $S$ is given by $S=\pi r^2$.

I am going to implement this in a program and I am mainly aiming for runtime optimization. What would be the fastest way to calculate the area $S$ from the three points?

$\endgroup$

2 Answers 2

15
$\begingroup$

The circumradius is the length from the center of the circle to the vertex of the triangle. $R = \frac{ a b c }{\sqrt{ ( a + b + c ) ( b + c − a ) ( c + a − b ) ( a + b − c ) }}$, where a,b, and c are lengths of the sides of the triangle (see here). I leave it to you as an exercise to find the area of the circumcircle once you know the circumradius. Note that the expression in the denominator (up to a factor of 4) is Heron's formula for the area of the triangle.

$\endgroup$
5
  • $\begingroup$ I was not familiar with circumradiuses. Thanks. After reading about it, and if I understand correctly, Isn't this simply the radius of the circle I am looking for? That is, isn't the area given simply by $\pi R^2$ where $R$ is the circumradius? If so, where is the exercise? I feel like I am missing something. $\endgroup$
    – havakok
    Commented Apr 9 at 13:10
  • 12
    $\begingroup$ That was a joke (the exercise was to use the formula $\pi R^2$ :-) $\endgroup$ Commented Apr 9 at 13:14
  • $\begingroup$ Other than the Heron/Brahmagupta formula for area of a triangle, we can also evaluate it using the determinant form populated by 6 coordinates. $\endgroup$
    – Narasimham
    Commented Apr 10 at 13:28
  • 1
    $\begingroup$ Heron was in 70 AD whereas Brahmagupta was in the 7th century. @Narasimham $\endgroup$ Commented Apr 10 at 13:47
  • $\begingroup$ Not quite the Heron's formula, but Heron's formula multiplied by 4 (you're basically using the fact that $abc = 4R\Delta$. $\endgroup$
    – D S
    Commented Apr 10 at 17:43
4
$\begingroup$

For any two points $A,B$ on the circle the center is located on the line perpendicular to the segment $AB$ and passing through the middle point of $AB.$ For three points $A,B$ and $C$ we determine the two lines corresponding to $AB$ and $AC$ and the point $O$ of their intersection. These steps require linear equations. Once you got the center $O$ you calculate the square of the radius by determining $OA^2.$ There are no square roots on the way. The only approximation step comes at the very end when you multiply by $\pi.$

Remark Assume the coordinates of all three points are rational numbers. Then all quantities in the procedure are rational numbers, including the square of the radius. The multiplication by $\pi$ is the only exception. So the exact calculations, by hand, can be performed up to penultimate step.

$\endgroup$
9
  • 1
    $\begingroup$ You can also compute the derivative of a polynomial by using the limit definition of the derivative :-) But why do that if you have a ready-made formula? $\endgroup$ Commented Apr 9 at 12:59
  • 1
    $\begingroup$ @MikhailKatz There are no square roots in the procedure, unlike in the formula, where there are three of them. In this way it is easier to implement this procedure. That's was the aim of the asker. $\endgroup$ Commented Apr 9 at 13:15
  • 1
    $\begingroup$ It would be interesting to compare the computational complexity of the two approaches. To use the formula, one needs to evaluate three square roots. To use the midpoint perpendiculars, one needs several more steps involving linear procedures only, including finding slopes. It is hard for me to tell which would be more efficient. $\endgroup$ Commented Apr 9 at 13:21
  • 2
    $\begingroup$ @MikhailKatz There are more steps, all of them linear, except for the last one, but no approximation required for calculating square roots. $\endgroup$ Commented Apr 9 at 13:24
  • 1
    $\begingroup$ I don't really understand your point about not needing approximation. Any calculation implemented on the computer will necessarily involve approximation. Do you mean to say that your approach will result in an exact formula in terms of the parameters of the original problem (namely coordinates of the points)? $\endgroup$ Commented Apr 9 at 13:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .