Cut a large cuboid into random small cuboids whose dimensions are within a certain range

Question

I am trying to cut a large cuboid of dimension (L, W, H) into N (N can be an arbitrary number and doesn't need to be specified) small cuboids where length and width of the small cuboids are 20% to 50% of the L and W of the large cuboid, and that the height of the small cuboids are smaller than 30% of the H. The size of the small cuboids should not be all same and ideally each of them should be different. The input of the algorithm should be the L,W,H of the large cuboid and the return of the algorithm should be a set of small box dimensions in a sequence that they can be stacked back into the large cuboid.

One related problem I could think of is the 3D stock-cutting problem, although in that problem you specify each small cuboid you want but in here the small box dimension can be random as long as they are in a range. Any help will be greatly appreciated!

Answer 1

rng = np.random.default_rng(0)
def split_dimension(length, low, high):
    '''
    Attempt to partition a segment of the given length in segments
    of length between low and high
    '''
    acc = 0
    while length - acc > high:
        assert length - acc >= low, \
          'Failed to get a solution, maybe it was bad luck, maybe there is no solution'
        # of course this choice could be made in a more clever way
        v = rng.uniform(low, high)
        yield acc, v
        acc += v
    yield acc, length - acc

def split_hypercuboid(dimension, dim_ranges):
    '''
    Attempt to split a given cuboid in sub cuboids with dimensions
    
    '''
    low, high = dim_ranges[-1]
    length = dimension[-1] 
    if len(dimension) == 1:
        for c,v in split_dimension(length, low, high):
            yield (c,), (v,)
    else:
        for c,v in split_dimension(length, low, high):
            for corner, size in split_hypercuboid(dimension[:-1], dim_ranges[:-1]):
                yield corner + (c,), size + (v,)
def solve(L, W, H):
    ''' Apply it to the original question '''
    return list(split_hypercuboid((L, W, H), ((0.2*L, 0.5*L), (0.2*W, 0.5*W), (0.0, 0.3*H))))

Plot the first layer

plt.figure(figsize=(5,5))
for (z, x, y), (l, w, h) in solve(100, 100, 100):
    if z == 0:
        plt.plot([x, x, x+w, x+w, x], [y, y+h, y+h, y, y], '-k')

Answer 2

first we define a method that calculates random dimensions for length and width.

# method returns array of random dimensions. Applicable for width and length.
import numpy as np
from math import fsum

def matrix_r(d): # d: dimension of width or legth
    r = np.random.rand(2) * d * 0.3 + 0.2 * d # r initializes with 2 cells
     # tests if the last cell is viable (dimension greater than 20% d)
    while fsum(r) > 0.8 * d:
         # not viable last cell, penultimate is changed to a viable value
         r[1] = np.random.rand(1) * (0.3 * d) + 0.2 * d
     # tests if the solution must have only one or more cells.
    if fsum(r) >= 0.6 * d:
        r = np.append(r, d - fsum(r)) # one cell solves
    else:
         # two cells solve
        r = np.append(r, np.random.rand(1) * d * 0.1 + 0.2 * d)
        r = np.append(r, d - fsum(r))
    return r

After, define method that calculate array of random dimensions for height:

def m_he(he):
# method returns array of heights
    hea = np.random.rand(20) * he * 0.3 # initializes with random numbers
     # tailor the array so that the sum is equal to the intended height
    for i in range(3, 20):
        if fsum(hea[0:i]) >= he:
            hea[i - 1] = he - fsum(hea[0: i - 1])
            hea = hea[0: i]
            break
    return hea

So define the method that calls methods defined above:

 # method initializes values and calls methods! Return array of cuboid dimensions
def sm_cub(le, wi, he):
    matrix_he = m_he(he)
    matrix_wi = matrix_r(wi)
    matrix_le = matrix_r(le)
    return [(wii, lei, hei) for lei in matrix_le for hei in matrix_he for wii in matrix_wi]

# main
length, width, height = 30, 40, 50
sm_cub(length, width, height)

Output: (dimensions of each cuboid) [(13.668186924139675, 14.507492472517196, 5.867028673417488), (10.03758244895968, 14.507492472517196, 5.867028673417488), (9.171339933891904, 14.507492472517196, 5.867028673417488), (7.122890693008742, 14.507492472517196, 5.867028673417488), (13.668186924139675, 14.507492472517196, 6.474284500168095), (10.03758244895968, 14.507492472517196, 6.474284500168095), (9.171339933891904, 14.507492472517196, 6.474284500168095), (7.122890693008742, 14.507492472517196, 6.474284500168095), (13.668186924139675, 14.507492472517196, 11.442336884028546), (10.03758244895968, 14.507492472517196, 11.442336884028546), (9.171339933891904, 14.507492472517196, 11.442336884028546), (7.122890693008742, 14.507492472517196, 11.442336884028546), (13.668186924139675, 14.507492472517196, 12.406902413723916), (10.03758244895968, 14.507492472517196, 12.406902413723916), (9.171339933891904, 14.507492472517196, 12.406902413723916), (7.122890693008742, 14.507492472517196, 12.406902413723916), (13.668186924139675, 14.507492472517196, 3.453580444916994), (10.03758244895968, 14.507492472517196, 3.453580444916994), (9.171339933891904, 14.507492472517196, 3.453580444916994), (7.122890693008742, 14.507492472517196, 3.453580444916994), (13.668186924139675, 14.507492472517196, 10.355867083744961), (10.03758244895968, 14.507492472517196, 10.355867083744961), (9.171339933891904, 14.507492472517196, 10.355867083744961), (7.122890693008742, 14.507492472517196, 10.355867083744961), (13.668186924139675, 6.633916322946278, 5.867028673417488), (10.03758244895968, 6.633916322946278, 5.867028673417488), (9.171339933891904, 6.633916322946278, 5.867028673417488), (7.122890693008742, 6.633916322946278, 5.867028673417488), (13.668186924139675, 6.633916322946278, 6.474284500168095), (10.03758244895968, 6.633916322946278, 6.474284500168095), (9.171339933891904, 6.633916322946278, 6.474284500168095), (7.122890693008742, 6.633916322946278, 6.474284500168095), (13.668186924139675, 6.633916322946278, 11.442336884028546), (10.03758244895968, 6.633916322946278, 11.442336884028546), (9.171339933891904, 6.633916322946278, 11.442336884028546), (7.122890693008742, 6.633916322946278, 11.442336884028546), (13.668186924139675, 6.633916322946278, 12.406902413723916), (10.03758244895968, 6.633916322946278, 12.406902413723916), (9.171339933891904, 6.633916322946278, 12.406902413723916), (7.122890693008742, 6.633916322946278, 12.406902413723916), (13.668186924139675, 6.633916322946278, 3.453580444916994), (10.03758244895968, 6.633916322946278, 3.453580444916994), (9.171339933891904, 6.633916322946278, 3.453580444916994), (7.122890693008742, 6.633916322946278, 3.453580444916994), (13.668186924139675, 6.633916322946278, 10.355867083744961), (10.03758244895968, 6.633916322946278, 10.355867083744961), (9.171339933891904, 6.633916322946278, 10.355867083744961), (7.122890693008742, 6.633916322946278, 10.355867083744961), (13.668186924139675, 8.858591204536527, 5.867028673417488), (10.03758244895968, 8.858591204536527, 5.867028673417488), (9.171339933891904, 8.858591204536527, 5.867028673417488), (7.122890693008742, 8.858591204536527, 5.867028673417488), (13.668186924139675, 8.858591204536527, 6.474284500168095), (10.03758244895968, 8.858591204536527, 6.474284500168095), (9.171339933891904, 8.858591204536527, 6.474284500168095), (7.122890693008742, 8.858591204536527, 6.474284500168095), (13.668186924139675, 8.858591204536527, 11.442336884028546), (10.03758244895968, 8.858591204536527, 11.442336884028546), (9.171339933891904, 8.858591204536527, 11.442336884028546), (7.122890693008742, 8.858591204536527, 11.442336884028546), (13.668186924139675, 8.858591204536527, 12.406902413723916), (10.03758244895968, 8.858591204536527, 12.406902413723916), (9.171339933891904, 8.858591204536527, 12.406902413723916), (7.122890693008742, 8.858591204536527, 12.406902413723916), (13.668186924139675, 8.858591204536527, 3.453580444916994), (10.03758244895968, 8.858591204536527, 3.453580444916994), (9.171339933891904, 8.858591204536527, 3.453580444916994), (7.122890693008742, 8.858591204536527, 3.453580444916994), (13.668186924139675, 8.858591204536527, 10.355867083744961), (10.03758244895968, 8.858591204536527, 10.355867083744961), (9.171339933891904, 8.858591204536527, 10.355867083744961), (7.122890693008742, 8.858591204536527, 10.355867083744961)]