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')