3
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Are the squares the same size? \$\endgroup\$ – Alexandre Vaillancourt Feb 7 '18 at 1:48
  • \$\begingroup\$ @AlexandreVaillancourt No, but I would appreciate an optimisation in the case that they did happen to be the same size. \$\endgroup\$ – Max Feb 7 '18 at 20:59
5
\$\begingroup\$

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.

diagram

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:

negative width

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the great explanation! While not substantially faster it is a nice enough improvement. \$\endgroup\$ – Max Feb 7 '18 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.