Algorithm to find length of a segment that connects center of two rectangles

Question

Ok, here is the story : I found this problem in one of the pizza boxes a few weeks ago. It said if you can solve this before you could finish the pizza, you would get hired at tripadviser. Though I am not looking to get hired, this problem got my eyes and spoiled my focus on pizza and dinner. I worked out something but with some assumptions. Here is the question :

Assume we know P,Q R and S. There is the line connecting centers of each rectangle. We need to find out points C and D. I am not sure if there is some other variable that we should know to solve this.

EDIT

Looking for a programmatic or psudo-code explanation- no need to move to maxthexchange.

Any suggestions ?

Answer 1

It's pretty simple to do step-by-step:

1. Compute A = (P + Q) / 2 and B = R + S / 2 (component-by-component)
2. An equation for the line between A and B is L(t) = t * A + (1 - t) * (B - A). Just solve this linear equation for a t* such that L(t*).y = Q.y to get C = L(t*). Do a similar thing with L(t).y = R.y to get D.

You can also use the values of t* that you get when solving for C and D to determine pathological cases like overlapping rectangles.

Answer 2

You actually don't need to find the points C and D to find the distance.

I assume you already know the coordinates of the rectangle. It's trivial to compute the coordinates of the center points and the lenghts of the edges.

Now, imagine a vertical line passing through A and a horizontal line passing through B. They intersect at a point, call it X. Also, imagine a vertical line passing through C and call its intersection point with the top edge of rectangle RS - C'.

You can trivially compute the length of AX. But the length of AX is half the height of RS + half the height of PQ (both of which you know) + the length of CC'.

So now you know the length of CC' (call it x).

You can also compute the angle (call it n) that AB makes with CC' from A and B's coordinates, since you know CC' is vertical.

Ergo, the length of the segment CD is x * cos(n).