Page 1 of 1
find if one rectangle fits into another
Posted: Sun Sep 14, 2003 6:55 am
by abductor
Can anyone please explain to me how to find out if one rectangle can fit into another(rotation is possible) given length and width of each?
thank you
Posted: Sun Sep 14, 2003 11:52 am
by Ivor
r1 fits into r2 if:
w1 < w2 and h1 < h2
or
w1 < h2 and h1 < w2
Is this what you want?
Posted: Sun Sep 14, 2003 2:19 pm
by makbet
You have to notice, that there are
only 2 possibilities to fit it.
One is that the two rectangles' sides are parallel to each other,
and this case is easy. The other
one is a bit complicated:
You have to rotate the smaller rectangle, so that two opposite
corners touch the bottom and top side of the bigger rectangle, and then see if the other corners are inside or outside. This also divides into 2 cases (the big rectangle can be vertical or horizontal), so the whole thing can be checked in constant time.