28
$\begingroup$

How could I calculate if a rectangular cuboid fits in an other rectangular cuboid, it may rotate or be placed in any way inside the bigger one.

For example would, (650,220,55) fit in (590,290,160), they are all mm.

$\endgroup$
  • 5
    $\begingroup$ (1, 1, 12) definitely can be hidden in (9, 9, 9) box. $\endgroup$ – Denis T. Sep 27 '17 at 15:47
  • $\begingroup$ Someone claims if $\min_{dim} A < \min_{dim} B$ and $\max_{dim} A < \max_{dim} B$ and $median_{dim} A < median_{dim} B$ then $A$ fits within $B$ (stackoverflow.com/questions/16703854/…) but I'm skeptical and would like to see a proof, especially because the median is not well defined in this case. $\endgroup$ – David G. Stork Sep 27 '17 at 16:58
  • 3
    $\begingroup$ Related: How to check if a box fits into another box (any rotations allowed) $\endgroup$ – jeq Sep 27 '17 at 17:37
  • 1
    $\begingroup$ Perhaps see The Art of Mathematics: Coffee Time in Memphis, Béla Bollobás, Cambridge UP, on "Airline Luggage": books.google.ca/… $\endgroup$ – jeq Sep 27 '17 at 17:52
  • 5
    $\begingroup$ See also "Seven Puzzles You Think You Must Not Have Heard Correctly", Peter Winkler, math.dartmouth.edu//~pw/solutions.pdf $\endgroup$ – jeq Sep 27 '17 at 18:03
27
$\begingroup$

There are several algorithms in polynomial time to decide if a convex polytope contains another polytope, see e.g. for Martin, Stephenson, "Containment algorithms for objects in rectangular boxes" (1989).

Let me invoke @Joseph O'Rourke, a regular contributor to mathoverflow, and also the author of one of these algorithms. He will probably show up soon and give a definitive answer for the case at hand.

$\endgroup$
  • 5
    $\begingroup$ Actually, I would cite the same algorithm. I don't know that anyone has published box in box, so convex polyhedron in box may be the best bet. I wrote a paper on the minimum volume containing box, but that seems irrelevant to just deciding containment. $\endgroup$ – Joseph O'Rourke Sep 27 '17 at 19:11
  • 1
    $\begingroup$ @JosephO'Rourke Very naïve: One of the comments to the question holds a link that leads to the observation that if one box can be contained in another, then it can also be contained when the centers of the two boxes coincide. So without loss of generality, let the outer box and inner box have center $(0,0,0)$, and the outer box has a fixed orientation (say edges parallel to coordinate axes). Then try to rotate the inner box and see if all vertices of the inner box can fit inside the outer box. But I do not know the best way to try all (needed) rotations. $\endgroup$ – Jeppe Stig Nielsen Oct 2 '17 at 23:00
  • 2
    $\begingroup$ @JeppeStigNielsen: If $A$ fits in $B$ and no vertex of $A$ touches $B$, then you could rotate $A$ so that a vertex hits. If only one vertex of $A$ touches $B$, then you could rotate until two vertices hit. So one would only need look at those orientations of $A$ for which two vertices lie on faces of $B$. $\endgroup$ – Joseph O'Rourke Oct 2 '17 at 23:18
22
$\begingroup$

A (trivial) necessary condition is that the diagonal of the inner one is not longer than the diagonal of the outer one.

So if $(a,b,c)$ is supposed to fit in $(x,y,z)$, then we should have $$a^2+b^2+c^2 \leq x^2+y^2+z^2$$

But in your example we have

$$650^2+220^2 + 55^2 = 473925 > 457800 = 590^2+290^2+160^2$$

So the answer to your example is: No, it would not fit.

$\endgroup$
  • 3
    $\begingroup$ Ah! Monotonicity of the diameter, well done! I tried the intrinsic volumes $a+b+c$, $ab+bc+ca$ and $abc$ which are also monotone but this does not succeed in this example. $\endgroup$ – coudy Sep 28 '17 at 7:49
  • 4
    $\begingroup$ Nice, and this answers the particular example from the question. However, your necessary condition is not sufficient, so there will be other cases where your method does not lead to any answer. For example user Mamuka Jibladze (written as მამუკა ჯიბლაძე) gives a case in a comment to another answer where you take a cube $(1,1,1)$ of space diagonal $\sqrt{3}$ and try to put it in a box of type $(2,\epsilon,\epsilon)$ where $\epsilon$ is very small. The space diagonals say it is OK, but the latter box is a very thin rod that cannot contain a unit cube. $\endgroup$ – Jeppe Stig Nielsen Sep 28 '17 at 10:36
  • $\begingroup$ @JeppeStigNielsen sure! $\endgroup$ – Moritz Firsching Sep 28 '17 at 10:40
  • $\begingroup$ @MoritzFirsching your answer works in all the cases I have tested. The user MatheusLima's answer works in some cases but does not work for box A with dimensions (30 20 10) and box B with dimensions (10 25 20), i.e. every bi is not less than or equal to every ai with i=1,2,3 yet box B can be put into box A as shown by the formula in your necessary condition. $\endgroup$ – Black Panther Jan 8 '20 at 19:05
7
$\begingroup$

This could also be solved by quantifier elimination, and perhaps someone with more knowledge of quantifier elimination can see how to do it feasibly.

A box of side lengths $(a,b,c)$ fits inside a box of side lengths $(x,y,z)$ iff there are vectors $(\mathbf{t},\mathbf u,\mathbf{v})$ for the sides satisfying: \begin{gather*} \begin{aligned} \mathbf{t}\cdot\mathbf{t}=a^2,&& & \mathbf{u}\cdot\mathbf{u}=b^2,&& \mathbf{v}\cdot\mathbf{v}=c^2, \\ \mathbf{t}\cdot\mathbf{u}=0,&&& \mathbf{u}\cdot\mathbf{v}=0,&& \mathbf{v}\cdot\mathbf{t}=0, \end{aligned} \\ \pm\mathbf{t} \pm \mathbf{u} \pm \mathbf{v} \le (x,y,z) \end{gather*} where the last line represents three coordinate inequalities for each choice of signs. In other words, we are checking a statement of the form $\exists t_i t_j t_k u_i u_j u_k v_i v_j v_k\ \phi$, where $\phi$ is the conjunction of 6 equalities and 24 inequalities in those 9 bound variables and in $a$, $b$, $c$, $x$, $y$, $z$.

Quantifier elimination should then provide some list of polynomial inequalities in $a$, $b$, $c$, $x$, $y$, $z$ which together are equivalent to the small box fitting inside the large box.

Update: This works in the 2-d case, with interesting results. Assuming that $0<a<b$ and $0<x<y$, the $a\times b$ rectangle can fit inside the $x\times y$ rectangle iff either: $$a \le x$$ $$b \le y$$ or: $$a \le x$$ $$\phantom{(ax+by)^2+}(b^2-a^2)^2 \le (ax-by)^2+(ay-bx)^2$$

$\endgroup$
1
$\begingroup$

Given an inner box $(x_1, y_1, z_1)$ and an outer box $(x_2, y_2, z_2)$, there are four tests you could do.

First, if $x_1y_1z_1 \gt x_2y_2z_2$, the inner box will not fit in the outer box.

Second, if $x_1\le y_1\le z_1$ and $x_2\le y_2\le z_2$ and $x_1\le x_2$ and $y_1\le y_2$ and $z_1\le z_2$, the inner box will fit in the outer box.

Third, if the inner box can be rotated along an axis such that its side orthogonal to the axis fits within the corresponding side of the outer box and its length along the axis is less than or equal to the corresponding length of the outer box, it will fit in the outer box. So for the third test, you look at the $xy$, $xz$ and $yz$ planes individually and reduce the problem to two dimensions. In the 2-D case, an inner rectangle $(x_1, y_1)$ can be rotated within an outer rectangle $(x_2, y_2)$ if $x_1 + y_1 \le \sqrt{x_2^2+y_2^2}$.

Fourth, if $x_1+y_1+z_1 \le \sqrt{x_2^2+y_2^2+z_2^2}$, the inner box will fit in the outer box.

Here is a working example in Python.

import numpy as np

def fit(inner_dims, outer_dims):
    inner_dims.sort()
    outer_dims.sort()
    x1, y1, z1 = inner_dims
    x2, y2, z2 = outer_dims
    
    # Volume Test
    
    inner_volume = x1 * y1 * z1
    outer_volume = x2 * y2 * z2    
    if inner_volume > outer_volume:
        return False
        
    # Edge Test
    
    diffs = np.greater_equal(outer_dims, inner_dims)
    if np.all(diffs):
        return True

    # Rotation Test
    
    inner_perms = [(x1, y1, z1), (x1, z1, y1), (z1, y1, x1)]
    outer_perms = [(x2, y2, z2), (x2, z2, y2), (z2, y2, x2)]
    
    for i, j in zip(inner_perms, outer_perms):
        if rotation_test(i, j):
            return True

    # Diagonal Test
    
    diag = np.sqrt(x2**2 + y2**2 + z2**2)
    if x1 + y1 + z1 <= diag:
        return True
                
    return False

def rotation_test(inner_dims, outer_dims):
    x1, y1, z1 = inner_dims
    x2, y2, z2 = outer_dims
    diag = np.sqrt(x2**2 + y2**2)
    if x1 + y1 <= diag and z1 <= z2:
        return True
    else:
        return False
```
$\endgroup$
  • 1
    $\begingroup$ Firsching said it is a necessary condition, not sufficient. $\endgroup$ – Ben McKay Jul 10 '20 at 19:33
  • 2
    $\begingroup$ Yes, Firsching was giving what we call around here a partial answer to the question (which is generally considered acceptable -- sometimes a complete answer is not available, so it's better than nothing). I think we can go ahead and treat your own answer also as partial, pointing out that his condition is not sufficient. But if you can make greater headway on the question itself, that would be great. $\endgroup$ – Todd Trimble Jul 10 '20 at 20:31
  • $\begingroup$ In MathJax, $\le$ $\le$ looks better than $<=$ $<=$. I have edited accordingly. $\endgroup$ – LSpice Jul 13 '20 at 23:44
  • 1
    $\begingroup$ @LSpice Awesome, thanks! $\endgroup$ – R.G. Jul 13 '20 at 23:49
-2
$\begingroup$

In fact, any box A with dimensions (a1, a2, a3) can fit in an other box B with dimensions (b1, b2, b3), in the following conditions:

i) Every ai is less than or equal to every bi with i = 1. 2. 3;

ii) Any ai has to be less than or equal to sqrt(b1^2+b2^2+b3^2), the main diagonal of B (diagB). Any box A with one of its dimensions equal to diagB, has the other two dimensions equal to 0, since any plane orthogonal to it would extend outside the box B.

iii) The sum of a1, a2 and a3 must be less than or equal to diagB.

From these, we can see that the greatest dimension ai of a box A for it to fit box B, given ai > bi, should lie in the interval (bi, diagB). Thus, any box with one dimension bigger than any dimension of a box containing it will necessarily placed along the latter's main diagonal.

Put it simply: A(a1, a2, a3) fits in B(b1, b2, b3) iff a1+a2+a3 <= diagB.

$\endgroup$
  • 5
    $\begingroup$ No you cannot fit A(1,1,1) in B(3,0,0) $\endgroup$ – მამუკა ჯიბლაძე Sep 27 '17 at 23:05
  • $\begingroup$ Not a good example since here condition 1 is violated and thus shouldn't fit. $\endgroup$ – Philipp Sep 28 '17 at 12:17
  • $\begingroup$ @Philipp Which condition 1? If you mean i) it is obviously (sufficient but) not necessary. I thought the last statement was meant to be unconditional. $\endgroup$ – მამუკა ჯიბლაძე Sep 28 '17 at 14:05
  • $\begingroup$ I'm just saying that the conditions require that $a_i <= b_j \qquad j=1,2,3$ But I assumed that your example wanted to show a case where all conditions are met but still you couldn't fit to the box (thus showing that the conditions are insufficient). But for $a_2$ you find that it's bigger than $b_2$ and $b_3$ and thus in this case his conditions determine correctly that the box A doesn't fit into box B. $\endgroup$ – Philipp Sep 28 '17 at 14:19
  • $\begingroup$ @Philipp There can be no example satisfying i) since if $a_i\leqslant b_j$ for all $i,j$ then the box trivially fits. The condition i) is a sufficient condition which is not necessary. It is not true that if the box fits then i) holds. $\endgroup$ – მამუკა ჯიბლაძე Sep 28 '17 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.