Detect if one rect can be put into another rect

Question

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?

Ammerman

the one in the lower diagram is too big :P – Nakamura

Answer 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:

Moneymaker

I am amazed and feel rather silly with my formulas below. +1 for very useful formula. However, it would be nice to know WHY this is true. – Shearwater

After finding that I actually do have access to the quoted article, I would like to quote part of its second page (in image form): link (This is followed by several pages of proof.) This formula is even more concise than the one above. (Feel free to use the formula and/or image, as they are not of my making.) – Shearwater

@Shearwater Thanks, I added that to the answer. – Moneymaker

In some cases, the code doesn't work. Here is a fixed version: q <= b && (p <= a || b * (p*p+q*q) >= (2*p*q*a + (p*p-q*q)*sqrt(p*p+q*q-a*a))) – Dupaix

@Dupaix is right, the second condition must include the q <= b part as well (note that q <= b is included in both (a) and (b) conditions of Carver's theorem). It is easy to see that, as is, the second condition is not correct: if you take p = q, it incorrectly allows fitting a square p × p into any smaller square a × a. – Postremogeniture

Those pictures are very difficult to read in the dark theme. Even in the light one the upper bar of the square root sign is barely seen. – Maximamaximal

Answer 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?

Shearwater

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

Broomrape

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

Bivalve