Which is the best distance measure to find the closest rectangle?

Question

Problem:

Given a random generated set of rectangles inside a plane with (X,Y) axis, after randomly picking one of them as source rectangle, I need to find which is the closest rectangle among the others. The algorithm simply computes the distance with all the other rectangles and then pick the one which minimize the distance. I need find the best distance measure in order to always find the closest. By "closest" it is intended the rectangle which has a point on the perimeter nearest to the source rectangle center we could say.

Assumptions:

1. There's always a source rectangle as starting object (in the below example A).
2. All rectangles are orthogonal to the (X,Y) axis.
3. There can be overlaps. So for instance A and D can collide or I can be totally included inside A.

At first I tried using the euclidean distance between the centers. $$\sqrt{(x_2−x_1)^2 + (y_2−y_1)^2}$$ This is incorrect because I could have a much bigger rectangle which is closer but computes a distance greater than a smaller and farther one. Example: B and E.

So I opted for a "clear spacing" distance as described here: Finding the clear spacing distance between two rectangles. Being $w_i$ and $h_i$ the width and the height of a generic rectangle respectively. $$max(|x_1−x_2|−\frac{(w_1+w_2)}{2},|y_1−y_2|−\frac{(h_1+h_2)}{2})$$ This is more robust and it gets negative if the rectangles are overlapped. But for example, taking the F and G rectangle there's no way to decide which is the closest since they have the same vertical spacing distance.

Which could be a better distance measure to use for this problem? Maybe an hybrid of this two distance definitions? Can't really grasp a precise formalization but I'm not quite sure anyway.

Answer 1

I'll give you a possible solution, but you'll have to check for yourself if it is efficient enough for your needs. First I'll show you my thought process and then in the end I'll write the conclusion, if that's the only part you're looking for.

How I got the idea?

Let's first denote a center of the "source" rectangle as $(c_1,c_2)$ and an arbitrary point on the other rectangle (whose distance to the center of the source rectangle where trying to find) as $(x_1,y_1)$. You need to find the minimum distance between $(c_1,c_2)$ and $(x_1,y_1)$.

If you see the image $(3)$, clearly the segment from $(c_1,c_2)$ to $(x_1,y_1)$ intersects one of the sides of the rectangle. As such we can certainly say that this segment won't have the minimum length possible if $(x_1,y_1)$ is on this side of the rectangle that it's on in $(3)$. So we'll say the point $(x_1,y_1)$ is definitely not on this side. Similarly for the most upper side of the rectangle. Essentially if a segment intersects any of the other sides of the rectangle then it certainly isn't the minimum distance.

In conclusion that we have two sides left that can have $(x_1,y_1)$ on them, the ones that $(x_1,y_1)$ is one in pictures $(1)$ and $(2)$ (at least in this specific example). Now we can define two functions, one for each of the sides. Generally you'll have to define one, two or three functions, depending on how many sides can $(x_1,y_1)$ be on (check previous paragraph). For example, I'll define a function, $f(x)$, of distance between $(c_1,c_2)$ and $(x_1,y_1)$ in the picture $(2)$ (Keep in mind that for picture $(1)$ you'll have to define a function as a function of $y$ and not $x$, I'll call it $g(y)$). The domain of this function will a set of all $x_1$ on the side on which $(x_1,y_1)$ is on in $(2)$. $y_1$ is fixed. So the function of distance is $f(x)=\sqrt{(c_1-x)^2+(c_2-y_1)^2}$. If we take the derivative of $f(x)$, we get $f'(x)=-\frac{c_1-x}{\sqrt{(c_1-x)^2+(c_2-y_2)^2}}$. So either a minimimum or maximum would be at the point at which $x=c_1$. But because of the side on which $(x_1,y_1)$ is located it will be maximum. Similarly you can show for the function $g(y)$, or some third function if you had it. But the problem is that you'll get, for example, $f'(x)=0$ only if you can make a perpendicular segment from $(c_1,c_2)$ to the line on which $(x_1,y_1)$ is, which more commonly than not, won't be the case. If this isn't the case then the the minimum of $f(x)$ will be at one of the tips of the side we're looking, which stems from the fact that $f(x)$ is a monotonic function.

Conclusion

I'll denote the "source" rectangle as $A$ and the other one as $B$. From the previously written we can conclude the following:

1. If you pull a line parallel to the x-axis through the point $(c_1,c_2)$ and it intersects the $B$ rectangle then the minimum distance will be from $(c_1,c_2)$ to the intersection of rectangle $B$ and that line. Since there will be two intersections you need to check which side of the rectangle is closer to source rectangle before calculating the distance. Note that you don't necessarily need to pull the aforementioned line you can just check if c_2 could be the y-coordinate of a rectangle
2. If the 1. condition isn't satisfied, similarly you could check if line parallel to the y-axis through the point $(c_1,c_2)$ intersects the rectangle.
3. Finally if neither 1. nor 2. are satisfied, the closest point to $(c_1,c_2)$ will be one of the tips of the rectangle.