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.