-
Notifications
You must be signed in to change notification settings - Fork 23
/
box_packer.rb
129 lines (114 loc) · 3.99 KB
/
box_packer.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
module BoxPacker
class << self
def pack(container:, items:)
packings = []
items.each do |item|
# If the item is just too big for the container lets give up on this
raise 'Item is too heavy for container' if item[:weight].to_f > container[:weight_limit].to_f
# Need a bool so we can break out nested loops once it's been packed
item_has_been_packed = false
packings.each do |packing|
# If this packings going to be too big with this
# item as well then skip on to the next packing
next if packing[:weight].to_f + item[:weight].to_f > container[:weight_limit].to_f
packing[:spaces].each do |space|
# Try placing the item in this space,
# if it doesn't fit skip on the next space
next unless placement = place(item, space)
# Add the item to the packing and
# break up the surrounding spaces
packing[:placements] += [placement]
packing[:weight] += item[:weight].to_f
packing[:spaces] -= [space]
packing[:spaces] += break_up_space(space, placement)
item_has_been_packed = true
break
end
break if item_has_been_packed
end
next if item_has_been_packed
# Can't fit in any of the spaces for the current packings
# so lets try a new space the size of the container
space = {
dimensions: container[:dimensions].sort.reverse,
position: [0, 0, 0]
}
placement = place(item, space)
# If it can't be placed in this space, then it's just
# too big for the container and we should abandon hope
raise 'Item cannot be placed in container' unless placement
# Otherwise lets put the item in a new packing
# and break up the remaing free space around it
packings += [{
placements: [placement],
weight: item[:weight].to_f,
spaces: break_up_space(space, placement)
}]
end
packings
end
def place(item, space)
item_width, item_height, item_length = item[:dimensions].sort.reverse
permutations = [
[item_width, item_height, item_length],
[item_width, item_length, item_height],
[item_height, item_width, item_length],
[item_height, item_length, item_width],
[item_length, item_width, item_height],
[item_length, item_height, item_width]
]
permutations.each do |perm|
# Skip if the item does not fit with this orientation
next unless perm[0] <= space[:dimensions][0] &&
perm[1] <= space[:dimensions][1] &&
perm[2] <= space[:dimensions][2]
return {
dimensions: perm,
position: space[:position],
weight: item[:weight].to_f
}
end
return nil
end
def break_up_space(space, placement)
[
{
dimensions: [
space[:dimensions][0] - placement[:dimensions][0],
space[:dimensions][1],
space[:dimensions][2]
],
position: [
space[:position][0] + placement[:dimensions][0],
space[:position][1],
space[:position][2]
]
},
{
dimensions: [
placement[:dimensions][0],
space[:dimensions][1] - placement[:dimensions][1],
space[:dimensions][2]
],
position: [
space[:position][0],
space[:position][1] + placement[:dimensions][1],
space[:position][2]
]
},
{
dimensions: [
placement[:dimensions][0],
placement[:dimensions][1],
space[:dimensions][2] - placement[:dimensions][2]
],
position: [
space[:position][0],
space[:position][1],
space[:position][2] + placement[:dimensions][2]
]
}
]
end
end
end