将一个大长方体切割成尺寸在一定范围内的随机小长方体
Cut a large cuboid into random small cuboids whose dimensions are within a certain range
我正在尝试将一个尺寸为 (L, W, H) 的大长方体切割成 N 个（N 可以是任意数字，不需要指定）小长方体，其中小长方体的长度和宽度是大长方体的 L 和 W 的 20% 到 50%，而小长方体的高度小于 H 的 30%。小长方体的大小不应该完全相同，理想情况下它们中的每一个都应该与众不同。算法的输入应该是大长方体的 L、W、H，算法的 return 应该是一组按顺序排列的小盒子尺寸，它们可以堆叠回大长方体。
我能想到的一个相关问题是 3D 库存切割问题，虽然在那个问题中你指定了你想要的每个小长方体，但在这里小盒子尺寸可以是随机的，只要它们在一个范围内。任何帮助将不胜感激！
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))))
绘制第一层
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')
首先我们定义一个方法来计算长度和宽度的随机尺寸。
# 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
之后，定义计算高度随机维度数组的方法：
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
所以定义调用上面定义的方法的方法：
# 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)
输出：（每个长方体的尺寸）
[(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.4535804444916994),
(9.171339933891904, 8.858591204536527, 3.4535804444916994),
(7.122890693008742, 8.858591204536527, 3.4535804444916994),
(13.668186924139675, 8.858591204536527, 10.355867083744961),
(10.03758244895968, 8.858591204536527, 10.355867083744961),
(9.171339933891904, 8.858591204536527, 10.355867083744961),
(7.122890693008742, 8.858591204536527, 10.355867083744961)]
我正在尝试将一个尺寸为 (L, W, H) 的大长方体切割成 N 个（N 可以是任意数字，不需要指定）小长方体，其中小长方体的长度和宽度是大长方体的 L 和 W 的 20% 到 50%，而小长方体的高度小于 H 的 30%。小长方体的大小不应该完全相同，理想情况下它们中的每一个都应该与众不同。算法的输入应该是大长方体的 L、W、H，算法的 return 应该是一组按顺序排列的小盒子尺寸，它们可以堆叠回大长方体。
我能想到的一个相关问题是 3D 库存切割问题，虽然在那个问题中你指定了你想要的每个小长方体，但在这里小盒子尺寸可以是随机的，只要它们在一个范围内。任何帮助将不胜感激！
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))))
绘制第一层
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')
首先我们定义一个方法来计算长度和宽度的随机尺寸。
# 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
之后，定义计算高度随机维度数组的方法：
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
所以定义调用上面定义的方法的方法：
# 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)
输出：（每个长方体的尺寸） [(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.4535804444916994), (9.171339933891904, 8.858591204536527, 3.4535804444916994), (7.122890693008742, 8.858591204536527, 3.4535804444916994), (13.668186924139675, 8.858591204536527, 10.355867083744961), (10.03758244895968, 8.858591204536527, 10.355867083744961), (9.171339933891904, 8.858591204536527, 10.355867083744961), (7.122890693008742, 8.858591204536527, 10.355867083744961)]