Detect if one rect can be put into another rect

问题:

This problem is different from testing if one rect is in another rect.

Known information is the sides length of two rects.

How to calculate if one rect can be put into another rect?

回答1:

This is a great question! If and only if one of these conditions is satisfied does a smaller rectangle with sides p and q (p >= q) fit completely into a larger rectangle with sides a and b (a >= b):

or

See this for reference.

---

So if we had variables a, b, p, q, we could check if such a rectangle arrangement would be possible by evaluating:

(p <= a && q <= b) || (p > a &&
                        b >= (2*p*q*a + (p*p-q*q)*sqrt(p*p+q*q-a*a)) / (p*p+q*q))

---

EDIT: Thanks to @amulware for posting this alternate version in his comment:

回答2:

The first check one would do is of course whether the rectangle fits inside the other in either of the axis aligned orientations.

If not, the only option for it to fit is diagonally, but there might actually be many angles for which it fits, the difficulty is, not just guessing but indeed calculating a possible angle, if one exists.

Now, notice that if the inner rectangle does indeed fit diagonally, then you can rotate it until two if its opposite corners touch either both the top and bottom edge of the outer rectangle, or the left and right. (In your diagram more or less the first.)

In that case you already know that you have fit it inside in that one dimension(in the example, the y-axis). You then have to calculate the bounding width of the inner rectangle in the other dimension and check that against the width of the outer box.

There might be a smarter algorithm out there for this, but I am 100% sure that what I describe works. Let me know if you can figure out the math for this yourself(if you think this is a good solution), if not, I might have a go at it later. I wonder if my algorithm can be implemented completely without trig functions...

EDIT: Ok now, I could not resist...

Here is the math I did to solve the problem as outlined above: (Sorry, only in image form, I hope my handwriting is readable.) I would be happy if someone could check my math. I do not see anything wrong with any of the steps right now, but it is always better to have someone else check. (And of course: Use this at your own risk.)

If anyone finds anything wrong with this algorithm, please let me know and I will fix it as soon as possible.

Also I would be highly interested to see if anyone has a better solution, involving less complicated math. Maybe a vector based approach?

回答3:

Well, it looks like A.R.S. solution is true, still I'll try to post my solution, it's harder, but it'll let you to build a concrete embedding of one rectangle into another (if possible).

Let us suppose that a>b and p > q. Solution is obvious if a > p and b > q. The problem can also be solved if a<p and b>q. Take a look at the attached photo, in it you'll need only last system of inequalities (if you interested you can look how it was derived)

All you need is to make sure that last system of inequalities has a solution lying between 0 and 1. To do it you need to solve each inequality as equation (as usual quadratic equation). If there are no solution (that's improbable) the solution of inequality is whole real line. If equation has two (maybe equal) solutions t_1 and t_2 the solution of inequality is segment [-infinity, t_1] united with [t_2, infinity]. After you got solutions of both inequalities you should intersect them. Now we should recollect that t is cos of an angle (between 0 and pi/2), so inequality should have solutions between 0 and 1. In that case second rectangle can be embedded into first one. And if you take e.g. t_1 (smaller root of equations) you can build a concreate embedding of rectangles.

回答4:

You can weed out the two simple cases fairly easily:

1. If the larger dimension of the second is smaller than the larger dimension of the first, and if the same is true for the smaller dimensions, then the second fits inside.
2. If the larger dimension of the second is greater than the hypotenuse of the first, then the second will not fit in the first.

The hard part is working out whether it can fit in at an angle such as in your sketch. I don't know of a simple formula -- it probably requires a plug-and-chug solution.

Might be a good question for the Mathematics Stack Exchange site.

Added: I'm not 100% sure if this, but I think that if the hypotenuse of the second is smaller than the hypotenuse of the first then it will fit.

Oops: Nope -- I'll take that back. But if the hypotenuse of the second is larger than the hypotenuse of the first it won't fit.