1 | <?php |
||
2 | /** |
||
3 | * Box packing (3D bin packing, knapsack problem). |
||
4 | * |
||
5 | * @author Doug Wright |
||
6 | */ |
||
7 | declare(strict_types=1); |
||
8 | |||
9 | namespace DVDoug\BoxPacker; |
||
10 | |||
11 | use JsonSerializable; |
||
12 | |||
13 | use function iterator_to_array; |
||
14 | use function json_encode; |
||
15 | use function max; |
||
16 | use function round; |
||
17 | use function is_iterable; |
||
18 | use function count; |
||
19 | use function array_pop; |
||
20 | use function assert; |
||
21 | use function array_map; |
||
22 | use function spl_object_id; |
||
23 | |||
24 | use const JSON_THROW_ON_ERROR; |
||
25 | use const JSON_NUMERIC_CHECK; |
||
26 | use const JSON_UNESCAPED_UNICODE; |
||
27 | use const JSON_UNESCAPED_SLASHES; |
||
28 | |||
29 | /** |
||
30 | * A "box" with items. |
||
31 | */ |
||
32 | readonly class PackedBox implements JsonSerializable |
||
33 | { |
||
34 | protected int $itemWeight; |
||
35 | |||
36 | protected float $volumeUtilisation; |
||
37 | |||
38 | /** |
||
39 | * Get packed weight. |
||
40 | * |
||
41 | * @return int weight in grams |
||
42 | */ |
||
43 | 13 | public function getWeight(): int |
|
44 | { |
||
45 | 13 | return $this->box->getEmptyWeight() + $this->getItemWeight(); |
|
46 | } |
||
47 | |||
48 | /** |
||
49 | * Get packed weight of the items only. |
||
50 | * |
||
51 | * @return int weight in grams |
||
52 | */ |
||
53 | 14 | public function getItemWeight(): int |
|
54 | { |
||
55 | 14 | if (!isset($this->itemWeight)) { |
|
56 | 14 | $itemWeight = 0; |
|
57 | 14 | foreach ($this->items as $item) { |
|
58 | 14 | $itemWeight += $item->item->getWeight(); |
|
59 | } |
||
60 | 14 | $this->itemWeight = $itemWeight; |
|
61 | } |
||
62 | |||
63 | 14 | return $this->itemWeight; |
|
64 | } |
||
65 | |||
66 | /** |
||
67 | * Get remaining width inside box for another item. |
||
68 | */ |
||
69 | 1 | public function getRemainingWidth(): int |
|
70 | { |
||
71 | 1 | return $this->box->getInnerWidth() - $this->getUsedWidth(); |
|
72 | } |
||
73 | |||
74 | /** |
||
75 | * Get remaining length inside box for another item. |
||
76 | */ |
||
77 | 1 | public function getRemainingLength(): int |
|
78 | { |
||
79 | 1 | return $this->box->getInnerLength() - $this->getUsedLength(); |
|
80 | } |
||
81 | |||
82 | /** |
||
83 | * Get remaining depth inside box for another item. |
||
84 | */ |
||
85 | 1 | public function getRemainingDepth(): int |
|
86 | { |
||
87 | 1 | return $this->box->getInnerDepth() - $this->getUsedDepth(); |
|
88 | } |
||
89 | |||
90 | /** |
||
91 | * Used width inside box for packing items. |
||
92 | */ |
||
93 | 5 | public function getUsedWidth(): int |
|
94 | { |
||
95 | 5 | $maxWidth = 0; |
|
96 | |||
97 | 5 | foreach ($this->items as $item) { |
|
98 | 5 | $maxWidth = max($maxWidth, $item->x + $item->width); |
|
99 | } |
||
100 | |||
101 | 5 | return $maxWidth; |
|
102 | } |
||
103 | |||
104 | /** |
||
105 | * Used length inside box for packing items. |
||
106 | */ |
||
107 | 5 | public function getUsedLength(): int |
|
108 | { |
||
109 | 5 | $maxLength = 0; |
|
110 | |||
111 | 5 | foreach ($this->items as $item) { |
|
112 | 5 | $maxLength = max($maxLength, $item->y + $item->length); |
|
113 | } |
||
114 | |||
115 | 5 | return $maxLength; |
|
116 | } |
||
117 | |||
118 | /** |
||
119 | * Used depth inside box for packing items. |
||
120 | */ |
||
121 | 5 | public function getUsedDepth(): int |
|
122 | { |
||
123 | 5 | $maxDepth = 0; |
|
124 | |||
125 | 5 | foreach ($this->items as $item) { |
|
126 | 5 | $maxDepth = max($maxDepth, $item->z + $item->depth); |
|
127 | } |
||
128 | |||
129 | 5 | return $maxDepth; |
|
130 | } |
||
131 | |||
132 | /** |
||
133 | * Get remaining weight inside box for another item. |
||
134 | */ |
||
135 | 1 | public function getRemainingWeight(): int |
|
136 | { |
||
137 | 1 | return $this->box->getMaxWeight() - $this->getWeight(); |
|
138 | } |
||
139 | |||
140 | 32 | public function getInnerVolume(): int |
|
141 | { |
||
142 | 32 | return $this->box->getInnerWidth() * $this->box->getInnerLength() * $this->box->getInnerDepth(); |
|
143 | } |
||
144 | |||
145 | /** |
||
146 | * Get used volume of the packed box. |
||
147 | */ |
||
148 | 31 | public function getUsedVolume(): int |
|
149 | { |
||
150 | 31 | return $this->items->getVolume(); |
|
151 | } |
||
152 | |||
153 | /** |
||
154 | * Get unused volume of the packed box. |
||
155 | */ |
||
156 | 1 | public function getUnusedVolume(): int |
|
157 | { |
||
158 | 1 | return $this->getInnerVolume() - $this->getUsedVolume(); |
|
159 | } |
||
160 | |||
161 | /** |
||
162 | * Get volume utilisation of the packed box. |
||
163 | */ |
||
164 | 31 | public function getVolumeUtilisation(): float |
|
165 | { |
||
166 | 31 | if (!isset($this->volumeUtilisation)) { |
|
167 | 31 | $this->volumeUtilisation = round($this->getUsedVolume() / ($this->getInnerVolume() ?: 1) * 100, 1); |
|
168 | } |
||
169 | |||
170 | 31 | return $this->volumeUtilisation; |
|
171 | } |
||
172 | |||
173 | /** |
||
174 | * Create a custom website visualiser URL for this packing. |
||
175 | */ |
||
176 | 1 | public function generateVisualisationURL(): string |
|
177 | { |
||
178 | 1 | $dedupedItems = $splIdToIntMap = []; |
|
179 | 1 | $splIdIndex = 0; |
|
180 | 1 | foreach ($this->items->asItemArray() as $item) { |
|
181 | 1 | if (!isset($splIdToIntMap[spl_object_id($item)])) { |
|
182 | 1 | $splIdToIntMap[spl_object_id($item)] = $splIdIndex++; |
|
183 | } |
||
184 | 1 | $dedupedItems[$splIdToIntMap[spl_object_id($item)]] = $item; |
|
185 | } |
||
186 | |||
187 | 1 | foreach ($dedupedItems as $item) { |
|
188 | 1 | $data['items'][$splIdToIntMap[spl_object_id($item)]] = [$item->getDescription(), $item->getWidth(), $item->getLength(), $item->getDepth()]; |
|
189 | } |
||
190 | |||
191 | 1 | $data['boxes'][] = [ |
|
192 | 1 | $this->box->getReference(), |
|
193 | 1 | $this->box->getInnerWidth(), |
|
194 | 1 | $this->box->getInnerLength(), |
|
195 | 1 | $this->box->getInnerDepth(), |
|
196 | 1 | array_map( |
|
197 | 1 | fn (PackedItem $item) => [$splIdToIntMap[spl_object_id($item->item)], $item->x, $item->y, $item->z, $item->width, $item->length, $item->depth], |
|
198 | 1 | iterator_to_array($this->items) |
|
199 | 1 | ), |
|
200 | 1 | ]; |
|
201 | |||
202 | 1 | return 'https://boxpacker.io/en/master/visualiser.html?packing=' . json_encode($data, flags: JSON_THROW_ON_ERROR | JSON_NUMERIC_CHECK | JSON_UNESCAPED_UNICODE | JSON_UNESCAPED_SLASHES); |
|
0 ignored issues
–
show
Comprehensibility
Best Practice
introduced
by
Loading history...
|
|||
203 | } |
||
204 | |||
205 | public function __construct(public Box $box, public PackedItemList $items) |
||
206 | { |
||
207 | assert($this->assertPackingCompliesWithRealWorld()); |
||
208 | } |
||
209 | |||
210 | 3 | public function jsonSerialize(): array |
|
211 | { |
||
212 | 3 | $userValues = []; |
|
213 | |||
214 | 3 | if ($this->box instanceof JsonSerializable) { |
|
215 | 2 | $userSerialisation = $this->box->jsonSerialize(); |
|
216 | 2 | if (is_iterable($userSerialisation)) { |
|
217 | 1 | $userValues = $userSerialisation; |
|
218 | } else { |
||
219 | 1 | $userValues = ['extra' => $userSerialisation]; |
|
220 | } |
||
221 | } |
||
222 | |||
223 | 3 | return [ |
|
224 | 3 | 'box' => [ |
|
225 | 3 | ...$userValues, |
|
226 | 3 | 'reference' => $this->box->getReference(), |
|
227 | 3 | 'innerWidth' => $this->box->getInnerWidth(), |
|
228 | 3 | 'innerLength' => $this->box->getInnerLength(), |
|
229 | 3 | 'innerDepth' => $this->box->getInnerDepth(), |
|
230 | 3 | ], |
|
231 | 3 | 'items' => iterator_to_array($this->items), |
|
232 | 3 | ]; |
|
233 | } |
||
234 | |||
235 | /** |
||
236 | * Validate that all items are placed solely within the confines of the box, and that no two items are placed |
||
237 | * into the same physical space. |
||
238 | */ |
||
239 | private function assertPackingCompliesWithRealWorld(): true |
||
240 | { |
||
241 | /** @var PackedItem[] $itemsToCheck */ |
||
242 | $itemsToCheck = iterator_to_array($this->items); |
||
243 | while (count($itemsToCheck) > 0) { |
||
244 | $itemToCheck = array_pop($itemsToCheck); |
||
245 | |||
246 | assert($itemToCheck->x >= 0); |
||
247 | assert($itemToCheck->x + $itemToCheck->width <= $this->box->getInnerWidth()); |
||
248 | assert($itemToCheck->y >= 0); |
||
249 | assert($itemToCheck->y + $itemToCheck->length <= $this->box->getInnerLength()); |
||
250 | assert($itemToCheck->z >= 0); |
||
251 | assert($itemToCheck->z + $itemToCheck->depth <= $this->box->getInnerDepth()); |
||
252 | |||
253 | foreach ($itemsToCheck as $otherItem) { |
||
254 | $hasXOverlap = $itemToCheck->x < ($otherItem->x + $otherItem->width) && $otherItem->x < ($itemToCheck->x + $itemToCheck->width); |
||
255 | $hasYOverlap = $itemToCheck->y < ($otherItem->y + $otherItem->length) && $otherItem->y < ($itemToCheck->y + $itemToCheck->length); |
||
256 | $hasZOverlap = $itemToCheck->z < ($otherItem->z + $otherItem->depth) && $otherItem->z < ($itemToCheck->z + $itemToCheck->depth); |
||
257 | |||
258 | $hasOverlap = $hasXOverlap && $hasYOverlap && $hasZOverlap; |
||
259 | assert(!$hasOverlap); |
||
260 | } |
||
261 | } |
||
262 | |||
263 | return true; |
||
264 | } |
||
265 | } |
||
266 |