In my education as a computer scientist, I once got an assignment where I had to calculate all pairwise intersections of N circles. I spent three hours finding out how to calculate the intersections between two circles, because that was not sufficiently explained anywhere. I intend to solve and explain the solution to this problem because I find it important to not only know how something works, but also why it works.
Subject
The question I intend to answer is the following:
Given the coordinates of the centres of two circles and their ranges, how do we compute the intersections?
I will also show why my solution is correct after I present it.
Required knowledge
Basic vector calculus
Basic geometry
Naming
To be able to effectively talk about this problem, we need to name some components.
Suppose we have two circles $C_1$ and $C_2$.
Centres of the circles: $M_1$ and $M_2$.
Intersection points: $P_1$ and $P_2$.
The coordinates of M_1 and M_2: $(x_1,y_1)$ and $(x_2,y_2)$ respectively.
The distance between $M_1$ and $M_2$: $d$.
The radii of the circles: $r_1$ and $r_2$ respectively.
The line between $M_1$ and $M_2$: $l_1$.
The line between $P_1$ and $P_2$: $l_2$.
The intersection of $l_1$ and $l_2$: $P_0$.
The distance from $M_1$ to $P_0$: $a$.
The distance from $M_2$ to $P_0$: $b$.
The distance from $P_0$ to $P_1$: $h$.
The distance from $P_0$ to $P_2$: $h'$.
an illustration will clarify this:
How to calculate whether two circles intersect
$d \leftarrow \Vert M_2-M_1 \Vert$
return $(d \le r_1 + r_2 ) \wedge (d \ge |r_1 − r_2|)$
This is a very short way of saying: "If the circles are close enough to each other, they intersect"
How to calculate the circles' intersections
This an algorithm to calculate the intersections of two circles.
If $C_1$ = $C_2$ then return $C_1$
If $C_1$ and $C_2$ don't intersect then return $\emptyset$
$d \leftarrow \Vert M_2-M_1 \Vert$
$a \leftarrow \frac{r_1^2-r_2^2+d^2}{2d}$
$x_0 \leftarrow x_1 + \frac{a}{d}(x_2-x_1)$
$y_0 \leftarrow y_1 + \frac{a}{d}(y_2-y_1)$
$h \leftarrow \sqrt{r_{1}^{2} - a^{2}}$
$x_1' \leftarrow x_0 + \frac{h}{d}(y_2-y_1)$
$y_1' \leftarrow y_0 - \frac{h}{d}(x_2-x_1)$
If $a = r_1$ then return $\{(x_1',y_1')\}$
$x_2' \leftarrow x_0 - \frac{h}{d}(y_2-y_1)$
$y_2' \leftarrow y_0 + \frac{h}{d}(x_2-x_1)$
return $\{(x_1',y_1'),(x_2',y_2')\}$
For the explanation of why this is true, read on.
$l_1$ and $l_2$ are perpendicular and $h$ and $h'$ are equal.
The triangles $M_1P_1P_0$ and $M_2P_2P_0$ are equilateral triangles, precisely because $P_1$ and $P_2$ are on the circles. An equilateral triangle can be split into two congruent right triangles. In this case, $M_1P_1P_0$ can be split into $M_1P_1P_0$ and $M_1P_2P_0$ while $M_2P_2P_0$ can be split into $M_2P_1P_0$ and $M_2P_2P_0$.
Because any of those triangles is a right triangle, $l_1$ and $l_2$ are perpendicular.
Because $M_1P_1P_0$ and $M_1P_2P_0$ are congruent triangles, $h$ and $h'$ are equal.
The algorithm is correct.
There are three cases to prove in the algorithm.
If the circles are not close enough, they don't intersect
If the circles touch, they have two equal intersection points
Otherwise, there are two different intersection points
I will only prove the third case. The second case is a special case of the third. The first is trivial.
We now know that the triangle $M_1P_1P_0$ is a right triangle. We can therefore calculate $h$ with Pythagoras.
$$ \left{ \begin{array}{c l r} r_1^2 = a^2 + h^2 & (1)\ r_2^2 = b^2 + h^2 & (2) \end{array} \right. $$
Out of the first equation, we can get the value of $h$.
$$ h \leftarrow \sqrt{r_1^2-a^2} $$
If we subtract equation two from equation one we get the following equation:
$$ \begin{array}{r l} r_1^2 -r_2^2 & = a^2 - b^2\ & = (a-b)(a+b)\ & = d(a-b)\ & = d(a-d+a)\ & = d(2a-d) \end{array} $$
From this equation, we can get the value of $a$.
$$ a = \frac{r_1^2-r_2^2 + d^2}{2d} $$
Now we can get the coordinates $(x_0,y_0)$ of $P_0$ because $P_0$ is located on $l_1$ at a distance of $a$ from $M_1$.
$$ P_0 = M_1 + \frac{a}{d}(M_2-M_1) = M_2 + \frac{b}{d}(M_1-M_2) $$
$$ \begin{bmatrix} P_{0x}\P_{0y}\ \end{bmatrix}
\begin{bmatrix} x_1 + \frac{a}{d}(x_2-x_1)\ y_1 + \frac{a}{d}(y_2-y_1)\ \end{bmatrix}
\begin{bmatrix} x_2 + \frac{a}{d}(x_1-x_2)\ y_2 + \frac{a}{d}(y_1-y_2)\ \end{bmatrix} $$
At last, we can calculate the coordinates of the intersection points from the coordinates of $M_1$, $M_2$ and $P_0$.
$$ \begin{bmatrix} P_x\P_y\ \end{bmatrix}
\begin{bmatrix} x_0 \pm \frac{h}{d}(y_2-y_1)\ y_0 \mp \frac{h}{d}(x_2-x_1) \end{bmatrix} $$
Our assignment, solution and report repository (dutch)
Repository: https://github.com/NorfairKing/TMI-project-2014
Note that you can't use any of our code for school/college/university assignments. Apart from that, refer to the license in the repository to see what you can and can't do with our code.