Circle-circle intersections

Computational geometry
Line-line intersections
9 May 2020 Code on Github

Introduction

Circle-circle intersections are one of the simpler intersection tests because circle are so symmetrical. The test is just a matter of finding the distance between the centres of the two circles and seeing whether it's less than or equal to the sum of their radii.

The distance between two points

The distance between two points is calculated using Pythagoras's theorem. You draw a right-angled triangle by moving horizontally from one point until you reach the x-coordinate of the second point, then move directly up to it. The line connecting the two points then forms the hypotenuse. You can then find the length of the hypotenuse using the lengths of the other two sides.

Intersection test

Say we have one circle, centred at $(x_1, y_1)$ with radius $r_1$, and a second circle centred at $(x_2, y_2)$ with radius $r_2$. The two circles intersect iff:

$\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} \leq r_1 + r2$

Note that the order in which we subtract the values ($x_1 - x_2$ or $x_2 - x_1$) does not matter, because the values are squared.

In code

This is shows how you could write the circle intersection test in Javascript.

function circlesIntersect(c1, c2) {
    const dx = c1.x - c2.x;
    const dy = c1.y - c2.y;
    const d = Math.sqrt(dx * dx + dy * dy);
    return d <= c1.r + c2.r;
}

It expects to take two objects with x, y, and r properties.

const circle1 = { x: 100, y: 50, r: 40 };
const circle2 = { x: 200, y: 80, r: 70 };
const hit = circlesIntersect(circle1, circle2);

Optimisation

Often with collision calculations you are testing hundreds of thousands of possible intersections in each update or a game or simulation, so you want them to be as quick as possible. To make functions faster you want to remove as many calculations as you can, particularly if they involve "complex" calculations.

In this case, the most intensive function is the square root function, which involves a lot of arithmetic behind the scenes. We can remove it by comparing whether the distance between the circle centres squared is less than or equal to the sum of the radii squared.

function circlesIntersect(c1, c2) {
    const dx = c1.x - c2.x;
    const dy = c1.y - c2.y;
    const r = c1.r + c2.r;
    return dx * dx + dy * dy <= r * r;
}

If all the circles you are testing have the same radii (in a particle simulation, say) you can even pre-calculate the squared sum of the radii.

It may also been more efficient to not create the variables dx, dy, and r and just do the whole calculation in one go. But I'm not sure this much more efficient (if at all), and it's definitely less readable.

function circlesIntersect(c1, c2) {
    return (c1.x - c2.x) * (c1.x - c2.x) + (c1.y - c2.y) * (c1.y - c2.y) <= (c1.r + c2.r) * (c1.r + c2.r);
}

Intersection points

Calculating the whether two circles intersect is relatively easy; calculating exactly where they intersect is a bit more tricky.

Unless the circles just touch, they will intersect at two points. The line connecting the two intersection points will be at right angles to a line connecting the two centres of the circles, and be bisected by it. So to calculate where the intersection points are, we can calculate how far along the line between the centres the intersection line is.

If we just concentrate on the triangles formed by the intersection points and the centres of the circles, we can define some variables.

  • $d$: the distance between the centres
  • $h$: half the distance between the intersection points
  • $a$: the distance from one circle centre to the intersection line
a d-a h d r 1 r 2

We can calculate $d$ as described above, so we have two unknowns.

We can get two expressions for these unknowns using Pythagoras's theorem (again):

$\qquad \begin{align} r_1^2 &= a^2 + h^2 \\ r_2^2 &= (d - a)^2 + h^2 \\ \end{align}$

We can rearrange to get expressions in terms of $h^2$ and set them equal to one another.

$\qquad \begin{align} h^2 &= r_1^2 - a^2 \\ h^2 &= r_2^2 - (d - a)^2 \\ r_1^2 - a^2 &= r_2^2 - (d - a)^2 \end{align}$

Then we can expand and get an expression for $a$.

Once we have a value for $a$ we can substitute it into the first expression to get a value for $h$.

$\qquad \begin{align} r_1^2 - a^2 &= r_2^2 - d^2 + 2ad - a^2 \\ r_1^2 &= r_2^2 - d^2 + 2ad \\ r_1^2 - r_2^2 + d^2 &= 2ad \\ a &= \frac{r_1^2 - r_2^2 + d^2}{2d}\\ \end{align}$

In code

Start by calculating the distance between the circle centres as before

function intersectionPoints(c1, c2) {
    let dx = c2.x - c1.x;
    let dy = c2.y - c1.y;
    const d = Math.sqrt(dx * dx + dy * dy);

Then check whether the circles do intersect, otherwise quit now.

// Circles too far apart
if (d > c1.r + c2.r) { return; }
    
// One circle completely inside the other
if (d < Math.abs(c1.r - c2.r)) { return; }

Then get a unit vector from one circle centre to the other in the form (dx, dy).

dx /= d;
dy /= d;

Calculate where the line of intersection crosses the line from one circle to the other

const a = (c1.r * c1.r - c2.r * c2.r + d * d) / (2 * d);
const px = c1.x + a * dx;
const py = c1.y + a * dy;

Calculate the height of the intersection line.

const h = Math.sqrt(c1.r * c1.r - a * a);

Calculate the intersection points by moving h units up and down from p, perpendicular to the line between the circles.

return {
    p1: {
        x: px + h * dy,
        y: py - h * dx
    },
    p2: {
        x: px - h * dy,
        y: py + h * dx
    }
};
Computational geometry
Line-line intersections