Improving Closeness algorithm by precomputing R

This post is a continuation of a previous post where I talked about how you can check if two points are closer than a distance. This improves it by adding the possibility to precompute R.

Why precompute R

As discussed in the previous post one of the slowest parts of working out if two points are closer than R is squaring R. For many cases you have a constant R which means R squared is also a constant.

For cases where you are performing collision detection you will have a fixed distance that two objects will collide. This means that if we precompute the distance squared we save time we we only have to do it once rather than N times. Where N is the number of times the algorithm is called.

Changing our function to accept R squared

Our current function is reproduced below.

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));
}

We can add a sixth parameter to the call which can be used to pass in the precomputed value. This then changes our function to be the following.

function arePointsCloserThanR2(x1, y1, x2, y2, r, r2) {
    //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 = r2 || 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));
}

Above in JavaScript if the sixth parameter is not passed in it will be undefined. So our line to calculate R squared becomes.

var rSquared = r2 || Math.pow(r, 2);

This will use the value of r2 as rSquared if it has been passed in, or do the computation inline. This allows us to optionally pass in the value of R squared, with little change to the function.

Summary

By providing an option to pass in the value of R squared this can be precomputed and passed in.

By doing this for anything that is repeatedly used as R you can improve the speed of the function by a decent factor.

If the distance checking function is slow and you repeatedly use a fixed R it is recommended to implement this additional function parameter and precompute R squared.