Efficient minimum distance between two axis aligned squares?

Question

I have two 2D arbitrarily-positioned axis-aligned squares.

I need to find the minimum distance between those squares – i.e. if you were to draw them, what's the length of the shortest line you could draw that would touch both?

Now, I have an algorithm that works. The problem is it's quite slow. Here it is:

function min_distance(a_left, a_right, a_top, a_bottom, b_left, b_right, b_top, b_bottom) {
    if (a_left <= b_right && a_right >= b_left && a_top >= b_bottom && a_bottom <= b_top) {
        return 0;
    } else if (a_left <= b_right && a_right >= b_left && a_top >= b_bottom/* && a_bottom <= b_top*/) {
        return a_bottom - b_top;
    } else if (a_left <= b_right && a_right >= b_left/* && a_top >= b_bottom*/ && a_bottom <= b_top) {
        return b_bottom - a_top;
    } else if (a_left <= b_right/* && a_right >= b_left*/ && a_top >= b_bottom && a_bottom <= b_top) {
        return b_left - a_right;
    } else if (/*a_left <= b_right && */a_right >= b_left && a_top >= b_bottom && a_bottom <= b_top) {
        return a_left - b_right;
    } else if (/*a_left <= b_right && */a_right >= b_left/* && a_top >= b_bottom*/ && a_bottom <= b_top) {
        let a = a_left - b_right;
        let b = b_bottom - a_top;
        return Math.sqrt(a*a+b*b);
    } else if (a_left <= b_right/* && a_right >= b_left && a_top >= b_bottom*/ && a_bottom <= b_top) {
        let a = b_left - a_right;
        let b = b_bottom - a_top;
        return Math.sqrt(a*a+b*b);
    } else if (a_left <= b_right/* && a_right >= b_left*/ && a_top >= b_bottom/* && a_bottom <= b_top*/) {
        let a = b_left - a_right;
        let b = a_bottom - b_top;
        return Math.sqrt(a*a+b*b);
    } else if (/*a_left <= b_right && */a_right >= b_left && a_top >= b_bottom/* && a_bottom <= b_top*/) {
        let a = a_left - b_right;
        let b = a_bottom - b_top;
        return Math.sqrt(a*a+b*b);
    } else if (a_left <= b_right/* && a_right >= b_left && a_top >= b_bottom && a_bottom <= b_top*/) {
        return b_right - a_left;
    } else if (/*a_left <= b_right && a_right >= b_left && a_top >= b_bottom && */a_bottom <= b_top) {
        return b_top - a_bottom;
    } else if (/*a_left <= b_right && a_right >= b_left && */a_top >= b_bottom/* && a_bottom <= b_top*/) {
        return a_top - b_bottom;
    } else if (/*a_left <= b_right && */a_right >= b_left/* && a_top >= b_bottom && a_bottom <= b_top*/) {
        return a_right - b_left;
    } else { unreachable() }
}

This can also handle rectangles, whereas I only need squares.

Are there any known algorithmic tricks to calculate this substantially faster?

Answer 1

By far the slowest part of this algorithm would be the square root. Try to avoid it if you can, and deal with the squared distance directly. For example, if you're comparing distances, the results will be the same if you compare squared distances.

Having said that, here's an alternate formulation of the distance function.

Suppose we have two squares sitting some distance apart, shown in red and blue. The shortest distance is equivalent to the length of the diagonal in the inner rectangle. This rectangle can be found by taking the outer rectangle (the smallest rectangle that covers both squares) and subtracting its dimensions by that of both squares. For our purposes, it doesn't matter where the inner rectangle is positioned, so we could just represent it as a pair of width and height.

So the pseudocode is:

Given square_a, square_b
rect_outer = (
    min(square_a.left, square_b.left),
    min(square_a.top, square_b.top),
    max(square_a.right, square_b.right),
    max(square_a.bottom, square_b.bottom)
)
inner_width = rect_outer.width - square_a.width - square_b.width
inner_height = rect_outer.height - square_a.height - square_b.height
min_distance = sqrt(inner_width^2 + inner_height^2)

Note that there are special cases, where the inner rectangle happens to have negative width, height, or both. Then we don't care about that dimension, and set it to zero. For example, given this arrangement:

The inner_width will come out negative after the calculation. In this case the min distance is just inner_height. So we can deal with this by clamping the inner_width to 0 and greater. Similarly we do the same thing with inner_height. This conveniently handles the cases where the two squares overlap.

Given square_a, square_b
rect_outer = (
    min(square_a.left, square_b.left),
    min(square_a.top, square_b.top),
    max(square_a.right, square_b.right),
    max(square_a.bottom, square_b.bottom)
)
inner_width = max(0, rect_outer.width - square_a.width - square_b.width)
inner_height = max(0, rect_outer.height - square_a.height - square_b.height)
min_distance = sqrt(inner_width^2 + inner_height^2)

This code is a bit easier to read than yours, but I don't think it's substantially faster, as it's doing the same calculations and checks.