CODEWITHSUNDEEP
algorithmmathlanguage-agnosticgeometrycomputational-geometry
HWﾠ
HWﾠ

Reputation: 1

How to check if a box fits into another box (any rotations allowed)

Suppose I have two boxes (each of them is a rectangular cuboid, aka rectangular parallelepiped). I need to write a function that decides if the box with dimensions (a, b, c) can fit into the box with dimensions (A, B, C), assuming any rotations by any angles are allowed (not only by 90°).

The tricky part is the edges of the inner box may be not parallel to corresponding edges of the outer one. For example, a box that is very thin in the dimensions (a, b) but with length 1 < c < √3 can fit into a unit cube (1, 1, 1) if placed along its main diagonal.

I've seen questions [1], [2] but they seem to cover only rotations by 90°.

Upvotes: 10

Views: 9930

Answers (5)

Matheus Lima
Matheus Lima

Reputation: 1

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.

Upvotes: 0

PaulQ
PaulQ

Reputation: 308

You basically have to check several cases, some trivial and some needing minimization searches.

First, there are 4 3-parallel-axis cases. If any of them passes (with @jean's test), you fit. Otherwise, continue to the next test cases:

Next, there are 18 2d diagonal cases, where one axis is parallel and the other two are diagonal, with one angle degree of freedom. Discard a case if the parallel axis doesn't fit; otherwise find the minimum of some "impingement" metric function of the single rotation angle. Then check for any actual impingement at that angle. The impingement metric has to be some continuous measure of how the inner box (4 corners) are staying inside the 2 faces of the outer box, allowing that sometimes they may go outside during the search for the minimum impingement angle. Hopefully a) there are a predictable maximum number of minima, and hopefully b) if there is a possible fit, then a fit is guaranteed at the angle of one of these minima.

If none of those cases passes without impingement, then move on to the larger number of 3d no-parallel-axes cases, where the rotation parameter is now three angles instead of one, and you have to search for a (hopefully limited number of) minima of the impingement metric, and test there for actual impingement.

Not really elegant, I think. This is similar to another thread asking how long of a line of given width can fit inside a 2d box of given dimensions. I didn't consider the parallel-axis case there, but the diagonal case requires solving a quartic equation (much worse than a quadratic equation). You may have a similar problem for your one-parallel-axis cases, if you want to go analytic instead of searching for minima of an impingement metric. The analytic solution for the no-parallel-axis 3d diagonal cases probably involves solving (for the correct root of) an even higher order equation.

Upvotes: 0

jean
jean

Reputation: 4350

Can you get box dimensions? Say a0,a1,a2 are the dimensions of box A ordered by size and b0,b1,b2 are the dimensions of box B ordered by size.

A fits inside B if (a0 <= b0 AND a1 <= b1 AND a2 <= b2)

Upvotes: -2

Ante
Ante

Reputation: 5458

If one box can fit inside the other than it can fit also if boxes have same center. So only rotation is enough to check, translation is not needed to check.

2D case: For boxes X=(2A,2B) and x=(2a,2b) positioned around (0,0). That means corners of X are (+-A, +-B). 

 ---------(A,B)
            |
 -----------(a,b)
(0,0)         |
 -----------(a,-b)
            |
 ---------(A,-B)

Be rotating x around (0,0), corners are always on circle C with radius sqrt(a^2+b^2). If part of circle lie inside box X, and if part inside X has enough arc length to place 2 points on distance 2a or 2b, than x can fit inside X. For that we need to calculate intersection of C with lines x=A and y=B, and calculate distance between these intersection. If distance is equal or grater than 2a or 2b, than x can fit inside X.

3D case: Similar. For boxes X=(2A,2B,2C) and x=(2a,2b,2c) positioned around (0,0,0). Rotating x around (0,0,0), all corners move on sphere with radius sqrt(a^2+b^2+c^2). To see is there enough space on sphere-box intersection part, find intersection of sphere with planes x=A, y=B and z=C, and check is there enough space to fit any of quads (2a,2b), (2a,2c) or (2b,2c) on that sphere part. It is enough to check are points on part border on sufficient distance. For this part I'm not sure about efficient approach, maybe finding 'center' of intersection part and checking it's distance to border can help.

Upvotes: 2

PengOne
PengOne

Reputation: 48398

Not a complete answer, but a good start is to determine the maximum diameter that fits inside the larger box (inscribe the box in a circle) and the minimum diameter needed for the smaller box. That gives a first filter for possibility. This also tells you how to orient the smaller box within the larger one.

Upvotes: 2

Related Questions