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?