Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

like image 592
HWᅠ Avatar asked Nov 30 '13 23:11

HWᅠ


2 Answers

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.

like image 82
PengOne Avatar answered Oct 19 '22 18:10

PengOne


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.

like image 21
Ante Avatar answered Oct 19 '22 20:10

Ante