Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
It is possible that the rectangles are rotated so it is not sufficient to check the bounds defined by the minimum and maximum values of x and y.
We can use a concept called the Minkowski Sum to determine if our rectangles overlap.
For our purpose, we want to take polygon A + -polygon B, so for convenience I will call this the Minkowski difference.
If we take every point in polygon A and subtract every point in polygon B we get a new polygon. If this polygon contains the origin then A and B overlap.
In this example we would end up with 16 points.
There is a generalized algorithm for finding if our new polygon contains the origin, but since we are dealing with rectangles we can us a trick to simplify the process.
We find an additional point by taking the Minkowski difference of the centers of the rectangles. Lets call this Mc and the vector from Mc to the origin as Mc->O.
We can use dot product of the Mc->O, and the vector defined by Mc and each point in our Minkowski difference to determine the distance of each point. to the origin, in the direction of Mc->O.
If the any of distance to any of our points is greater than the magnitude of Mc->O then our rectangles overlap.
We can, actually, speed this up by taking the maximum of the dot product of each point in A with Mc->0 plus the maximum of the dot product of each point of B with O->Mc and comparing this to the length of Mc->0. This cuts the number of dot products in half.
Here's a clean solution.
Rect 1 say represented in points Xi, Yi (get equation of all four lines in form Y=mx +c)
for each line in rectangle 1
{
for each point in rectangle 2
{
check if any point lies on different sides of two opposite lines pairwise.
if it does then it is an interior point in the rectangle;
break;
}
}
a point is on different sides of a line can be found easily as follows.
put the point on the line equation. of L1 and L2 if they give result in same sign (+ or -) they lie on same side, else they are on diff side
I hope the above would work
- Anirudh Kumar June 16, 2013