# Finding closest rectangle to another

how I would find line lengths highlighted with other color (with question marks) on the picture below? I know coordinates and size of these rectangles.

My goal is to find 'the closest' rectangle to the green one, but 'closest' is a quite abstract definition, so I decided that 'closest' would be one with shortest highlighted line on the picture below. Maybe there are other simpler ways to find 'closest' rectangle?

-
"Simple" depends on the way you define closeness. In Analysis, the distance between two sets is defined as the shortest of all the distances between points in one set and points in the other. Your interpration is simpler. To find those lengths you marked, well, there's the theorem of Pythagoras. – Weltschmerz Nov 2 '11 at 13:25

It looks like you are thinking of the distance between the centers of rectangles. If a rectangle has opposite corners $(a,b)$ and $(c,d)$ the center is $(\frac{a+c}{2},\frac{b+d}{2})$. As Weltschmerz says, you can just use the Pythagorean formula between these centers. It is easy to compute. An alternative is the Hausdorff distance. Between your green rectangle and the largest red one, it would give the distance from the upper right corner of the red one to the closest corner of the green one. It is harder to compute, but might be more what you want.

Added after the comment: you can calculate the orange lengths if you want, but they will not meet the usual requirements for a distance. The distance between two squares sharing an edge will be zero, but they are not the same rectangle. The triangle inequality will also fail. If the green rectangle is A and the upper right is B, there is a certain distance between them. If I now put a rectangle C in between which touches the top of A and the bottom of B, the distance from A to C is zero, the distance from C to B is zero, but the distance from A to B is greater than zero.

To calculate the orange distances, you can find the equation of the line going through the centers using the two point form. The line through $(a,b)$ and $(c,d)$ has equation $y-b=\frac{d-b}{c-a}(x-a)$, find the points where it hits the edge of the rectangles, and use Pythagoras.

-
Do you mean the upper right corner of the red one? – TonyK Nov 2 '11 at 14:58
@TonyK: Yes. Fixed – Ross Millikan Nov 2 '11 at 15:17
No, this is the problem. It's easy to calculate distance between the centers of rectangles. I need to find a small piece (highlighted with orange and with question mark) of the distance between the centers of rectangles. The shortest distance between the centers of rectangles doesn't mean that these rectangles are closest. – AlaskaKid Nov 2 '11 at 15:37
As watching on my picture according to my logic the biggest red rectangular from top is closest, but it's not as close as the smallest rectangular. So my method for determination 'the closest rectangular' is wrong. Do you have any ideas on how to determine it? – AlaskaKid Nov 2 '11 at 15:47
@AlaskaKid: You could try summing the distances between corresponding corners (assuming all the rectangles are aligned with the axes). I think this will meet the usual criteria for a distance. Does it do what you want? – Ross Millikan Nov 2 '11 at 15:52

I am not sure why no one has suggested the simple Euclidean distance between 2 points in the plane:

$D(p_1,p_2)=\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$

Once this distance is calculated for each highlighted line, the min. distance can be easily determined.

-

I will assume that you know coordinates of rectangles vertices so you may calculate centers of the rectangles.Let's observe picture below.If you know coordinates of vertices and centers you can easily find equations of black colored lines using two-point form. After you find equations of these lines you can calculate coordinates of intersection points $A,B,C,D,E,F$ by solving systems of two equations with two unknown variables.In order to find distances $\bar{AB} , \bar{CD} , \bar {EF}$ use distance formula.

-

Do you want a metric on rectangles? This means that $d(R_1,R_2)=0$ only if the rectangles $R_1$ and $R_2$ are completely identical (same size and location). Also it means that the triangle inequality is obeyed, $d(R_1,R_2) \le d(R_1,R_3) + d(R_2,R_3)$. If rectangle $R_i$ has corners $(x_i^1,y_i^1)$ and $(x_i^2,y_i^2)$, where $x_i^1<x_i^2$ and $y_i^1<y_i^2$, then the following would give you a metric for any $p\ge1$: $$d_p(R_1,R_2) = \left( \sum_{j=1}^2 |x_1^j-x_2^j|^p + |y_1^j-y_2^j|^p \right)^{1/p}$$ The cases $p=1,2$ might be useful. Also, the limiting case $p\rightarrow \infty$ is a simple metric: $$d_\infty(R_1,R_2) = \max(|x_1^1-x_2^1|,|y_1^1-y_2^1|,|x_1^2-x_2^2|,|y_1^2-y_2^2|)$$

In general you can can a metric from any norm on a 4-d space applied to the vector of differences in coordinates.

Also, if your concern is an algorithm for quickly finding neighbors, that's really a programming question, but look into quadtrees.

-