Intersections of Circles

Date 2014-08-09

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:

An illustration of two intersecting circles with all these names in the right place

How to calculate whether two circles intersect

  1. $d \leftarrow \Vert M_2-M_1 \Vert$

  2. 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.

  1. If $C_1$ = $C_2$ then return $C_1$

  2. If $C_1$ and $C_2$ don't intersect then return $\emptyset$

  3. $d \leftarrow \Vert M_2-M_1 \Vert$

  4. $a \leftarrow \frac{r_1^2-r_2^2+d^2}{2d}$

  5. $x_0 \leftarrow x_1 + \frac{a}{d}(x_2-x_1)$

  6. $y_0 \leftarrow y_1 + \frac{a}{d}(y_2-y_1)$

  7. $h \leftarrow \sqrt{r_{1}^{2} - a^{2}}$

  8. $x_1' \leftarrow x_0 + \frac{h}{d}(y_2-y_1)$

  9. $y_1' \leftarrow y_0 - \frac{h}{d}(x_2-x_1)$

  10. If $a = r_1$ then return $\{(x_1',y_1')\}$

  11. $x_2' \leftarrow x_0 - \frac{h}{d}(y_2-y_1)$

  12. $y_2' \leftarrow y_0 + \frac{h}{d}(x_2-x_1)$

  13. 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.

Previous
Obsessed is just a word the lazy use to describe the dedicated. - Russel Warren

Looking for a lead engineer?

Hire me
Next
The magic of getting up early