Search code examples
algorithmlinecentersegment

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

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. enter image description here

EDIT

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

Any suggestions ?

Solution

  • 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.