Checking if two points are closer than a distance

This blog post talks about how you can quickly check if two point are closer than a specific distance.

How to calculate the distance between two points

To calculate the distance between two points you can use Pythagoras Theorem.

This states that for a right angled triangle you can find the distance of the longest side, by summing the square of the horizontal and vertical sides and then taking the square root.

If two points have an x and y position you can use this formula to calculate the distance between them. Once you know the distance its a simple comparison between your and the calculated distance.

Applying this principle to our two points, we arrive at the above formulae. In JavaScript this distance can be calculated as.

Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow((y1 - y2), 2))

Once you know the distance, you can quickly work out if the two points are closer than a value.

return distance > Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow((y1 - y2), 2))

This will return true if the two points are closer than the given distance.

Optimising this by removing the square root

Currently this algorithm requires performing the following mathematical operations:

• 2x power of two
• 1x addition
• 1x square root
• 1x comparison

We can change it to instead of performing a square root, perform an additional power of two calculation. Typically this will be faster than the square root. This changes the maths to the following algorithm.

return Math.pow(distance, 2) > (Math.pow(x1 - x2, 2) + Math.pow((y1 - y2), 2))

Instead of performing the square root and comparing it, you square the distance and compare the two.

Speeding it up for cases where the two points are far away

The complexity of the above algorithm is that the two points are not always on the same x or y axis. This means you need to calculate the diagonal distance between the two using the above algorithm.

However, if you know that the difference between either the x or y axis points is larger than the the distance you are checking then it will always be further away than the search distance.

Above is a diagram which shows this principle. Inside the green circle are all points where the central point is closer than the search distance. The red area is all points within the distance in either the x or y axis.

All points outside the red square are those which have an x or y difference
greater than our search distance. To check if it is outside the square we can run the following check:

if(Math.abs(x1 - x2) > r || Math.abs(y1 - y2) > r) {
    return false;
}

Here, if the absolute distance between the x or y points is greater than r, our search distance, the points must be further away than r.

Putting this all together

If you combine all of these you get a relatively efficient algorithm for checking if two points are closer than a specific distance.

function arePointsCloserThanR(x1, y1, x2, y2, r) {
    //Shortcut for the maths. This creates a box region where we know anything
    // that lies outside the box definitely isn't closer than R. If this
    //is true then return false and we don't have to do complex (slow) maths.
    if(Math.abs(x1 - x2) > r || Math.abs(y1 - y2) > r) {
        return false;
    }

    //We need to do maths, Lets cheat and square R instead of a slower sqrt
    var rSquared = Math.pow(r, 2);

    //If R Squared is bigger then the two distances squared, then return
    // true as the points are closer
    return rSquared > (Math.pow(x1 - x2, 2) + Math.pow((y1 - y2), 2));
}

Here we first perform the box check, which will remove the need for performing the more complex power operation in some cases. If this determines the second point might be within the search distance we use Pythagoras theorem to calculate the distance and compare it. This uses the distance squared, rather than using square root for performance reasons.

I used this code in my D3.js Herd Immunity and Vaccination visualisation to calculate if two people were close enough to pass an infection.