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.
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityHow 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.
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.
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.
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$$
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
```
$\le$
looks better than $<=$ $<=$
. I have edited accordingly.
$\endgroup$
– LSpice
Jul 13 '20 at 23:44
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.