1
|
|
|
<?php |
2
|
|
|
/** |
3
|
|
|
* Box packing (3D bin packing, knapsack problem) |
4
|
|
|
* @package BoxPacker |
5
|
|
|
* @author Doug Wright |
6
|
|
|
*/ |
7
|
|
|
declare(strict_types=1); |
8
|
|
|
namespace DVDoug\BoxPacker; |
9
|
|
|
|
10
|
|
|
use Psr\Log\LoggerAwareInterface; |
11
|
|
|
use Psr\Log\LoggerAwareTrait; |
12
|
|
|
use Psr\Log\LoggerInterface; |
13
|
|
|
use Psr\Log\NullLogger; |
14
|
|
|
|
15
|
|
|
/** |
16
|
|
|
* Actual packer |
17
|
|
|
* @author Doug Wright |
18
|
|
|
* @package BoxPacker |
19
|
|
|
*/ |
20
|
|
|
class VolumePacker implements LoggerAwareInterface |
21
|
|
|
{ |
22
|
|
|
use LoggerAwareTrait; |
23
|
|
|
|
24
|
|
|
/** |
25
|
|
|
* Box to pack items into |
26
|
|
|
* @var Box |
27
|
|
|
*/ |
28
|
|
|
protected $box; |
29
|
|
|
|
30
|
|
|
/** |
31
|
|
|
* @var int |
32
|
|
|
*/ |
33
|
|
|
protected $boxWidth; |
34
|
|
|
|
35
|
|
|
/** |
36
|
|
|
* @var int |
37
|
|
|
*/ |
38
|
|
|
protected $boxLength; |
39
|
|
|
|
40
|
|
|
/** |
41
|
|
|
* List of items to be packed |
42
|
|
|
* @var ItemList |
43
|
|
|
*/ |
44
|
|
|
protected $items; |
45
|
|
|
|
46
|
|
|
/** |
47
|
|
|
* List of items to be packed |
48
|
|
|
* @var ItemList |
49
|
|
|
*/ |
50
|
|
|
protected $skippedItems; |
51
|
|
|
|
52
|
|
|
/** |
53
|
|
|
* Remaining weight capacity of the box |
54
|
|
|
* @var int |
55
|
|
|
*/ |
56
|
|
|
protected $remainingWeight; |
57
|
|
|
|
58
|
|
|
/** |
59
|
|
|
* Whether the box was rotated for packing |
60
|
|
|
* @var bool |
61
|
|
|
*/ |
62
|
|
|
protected $boxRotated = false; |
63
|
|
|
|
64
|
|
|
/** |
65
|
|
|
* Constructor |
66
|
|
|
* |
67
|
|
|
* @param Box $box |
68
|
|
|
* @param ItemList $items |
69
|
|
|
*/ |
70
|
36 |
|
public function __construct(Box $box, ItemList $items) |
71
|
|
|
{ |
72
|
36 |
|
$this->box = $box; |
73
|
36 |
|
$this->items = $items; |
74
|
|
|
|
75
|
36 |
|
$this->boxWidth = max($this->box->getInnerWidth(), $this->box->getInnerLength()); |
76
|
36 |
|
$this->boxLength = min($this->box->getInnerWidth(), $this->box->getInnerLength()); |
77
|
36 |
|
$this->remainingWeight = $this->box->getMaxWeight() - $this->box->getEmptyWeight(); |
78
|
36 |
|
$this->skippedItems = new ItemList(); |
79
|
36 |
|
$this->logger = new NullLogger(); |
80
|
|
|
|
81
|
|
|
// we may have just rotated the box for packing purposes, record if we did |
82
|
36 |
|
if ($this->box->getInnerWidth() != $this->boxWidth || $this->box->getInnerLength() != $this->boxLength) { |
83
|
9 |
|
$this->boxRotated = true; |
84
|
|
|
} |
85
|
|
|
|
86
|
|
|
} |
87
|
|
|
|
88
|
|
|
/** |
89
|
|
|
* Pack as many items as possible into specific given box |
90
|
|
|
* |
91
|
|
|
* @return PackedBox packed box |
92
|
|
|
*/ |
93
|
36 |
|
public function pack(): PackedBox |
94
|
|
|
{ |
95
|
36 |
|
$this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}"); |
96
|
|
|
|
97
|
36 |
|
$packedItems = new PackedItemList; |
98
|
36 |
|
$prevItem = null; |
99
|
|
|
|
100
|
36 |
|
$x = $y = $z = $rowWidth = $rowLength = $layerWidth = $layerLength = $layerDepth = 0; |
101
|
|
|
|
102
|
36 |
|
$packingWidthLeft = $this->boxWidth; |
103
|
36 |
|
$packingLengthLeft = $this->boxLength; |
104
|
36 |
|
$packingDepthLeft = $this->box->getInnerDepth(); |
105
|
|
|
|
106
|
36 |
|
while (count($this->items) > 0) { |
107
|
36 |
|
$itemToPack = $this->items->extract(); |
108
|
36 |
|
$isLastItem = count($this->skippedItems) === 0 && count($this->items) === 0; |
109
|
|
|
|
110
|
|
|
//skip items that are simply too heavy or too large |
111
|
36 |
|
if (!$this->checkConstraints($itemToPack, $packedItems)) { |
112
|
10 |
|
$this->rebuildItemList(); |
113
|
10 |
|
continue; |
114
|
|
|
} |
115
|
|
|
|
116
|
36 |
|
$orientatedItem = $this->getOrientationForItem($itemToPack, $prevItem, $isLastItem, $packingWidthLeft, $packingLengthLeft, $packingDepthLeft); |
117
|
|
|
|
118
|
36 |
|
if ($orientatedItem instanceof OrientatedItem) { |
119
|
36 |
|
$packedItem = PackedItem::fromOrientatedItem($orientatedItem, $x, $y, $z); |
120
|
36 |
|
$packedItems->insert($packedItem); |
121
|
36 |
|
$this->remainingWeight -= $orientatedItem->getItem()->getWeight(); |
122
|
36 |
|
$packingWidthLeft -= $orientatedItem->getWidth(); |
123
|
|
|
|
124
|
36 |
|
$rowWidth += $orientatedItem->getWidth(); |
125
|
36 |
|
$rowLength = max($rowLength, $orientatedItem->getLength()); |
126
|
36 |
|
$layerDepth = max($layerDepth, $orientatedItem->getDepth()); |
127
|
|
|
|
128
|
|
|
//allow items to be stacked in place within the same footprint up to current layer depth |
129
|
36 |
|
$stackableDepth = $layerDepth - $orientatedItem->getDepth(); |
130
|
36 |
|
$this->tryAndStackItemsIntoSpace($packedItems, $prevItem, $orientatedItem->getWidth(), $orientatedItem->getLength(), $stackableDepth, $x, $y, $z + $orientatedItem->getDepth()); |
131
|
36 |
|
$x += $orientatedItem->getWidth(); |
132
|
|
|
|
133
|
36 |
|
$prevItem = $packedItem; |
134
|
|
|
|
135
|
36 |
|
$this->rebuildItemList(); |
136
|
|
|
} else { |
137
|
24 |
|
if ($layerWidth == 0 && $layerDepth == 0) { // zero items on layer |
138
|
4 |
|
$this->logger->debug("doesn't fit on layer even when empty, skipping for good"); |
139
|
4 |
|
$prevItem = null; |
140
|
4 |
|
continue; |
141
|
24 |
|
} elseif (count($this->items) > 0) { // skip for now, move on to the next item |
142
|
21 |
|
$this->logger->debug("doesn't fit, skipping for now"); |
143
|
21 |
|
$this->skippedItems->insert($itemToPack); |
144
|
24 |
|
} elseif ($x > 0 && $packingLengthLeft >= min($itemToPack->getWidth(), $itemToPack->getLength())) { |
145
|
24 |
|
$this->logger->debug("No more fit in width wise, resetting for new row"); |
146
|
24 |
|
$layerWidth = max($layerWidth, $rowWidth); |
147
|
24 |
|
$layerLength += $rowLength; |
148
|
24 |
|
$packingWidthLeft += $rowWidth; |
149
|
24 |
|
$packingLengthLeft -= $rowLength; |
150
|
24 |
|
$y += $rowLength; |
151
|
24 |
|
$x = $rowWidth = $rowLength = 0; |
152
|
24 |
|
$this->rebuildItemList(); |
153
|
24 |
|
$this->items->insert($itemToPack); |
154
|
24 |
|
$prevItem = null; |
155
|
24 |
|
continue; |
156
|
|
|
} else { |
157
|
19 |
|
$this->logger->debug("no items fit, so starting next vertical layer"); |
158
|
|
|
|
159
|
19 |
|
$layerWidth = max($layerWidth, $rowWidth); |
160
|
19 |
|
$layerLength += $rowLength; |
161
|
19 |
|
$packingWidthLeft = $rowWidth ? min(intval($layerWidth * 1.1), $this->boxWidth) : $this->boxWidth; |
162
|
19 |
|
$packingLengthLeft = $rowLength ? min(intval($layerLength * 1.1), $this->boxLength) : $this->boxLength; |
163
|
19 |
|
$packingDepthLeft -= $layerDepth; |
164
|
|
|
|
165
|
19 |
|
$z += $layerDepth; |
166
|
19 |
|
$x = $y = $rowWidth = $rowLength = $layerWidth = $layerLength = $layerDepth = 0; |
167
|
|
|
|
168
|
19 |
|
$this->rebuildItemList(); |
169
|
19 |
|
$this->items->insert($itemToPack); |
170
|
19 |
|
$prevItem = null; |
171
|
|
|
} |
172
|
|
|
} |
173
|
|
|
} |
174
|
36 |
|
$this->logger->debug("done with this box"); |
175
|
36 |
|
return $this->createPackedBox($packedItems); |
176
|
|
|
} |
177
|
|
|
|
178
|
|
|
/** |
179
|
|
|
* @param Item $itemToPack |
180
|
|
|
* @param ?PackedItem $prevItem |
|
|
|
|
181
|
|
|
* @param bool $isLastItem |
182
|
|
|
* @param int $maxWidth |
183
|
|
|
* @param int $maxLength |
184
|
|
|
* @param int $maxDepth |
185
|
|
|
* |
186
|
|
|
* @return ?OrientatedItem |
|
|
|
|
187
|
|
|
*/ |
188
|
36 |
|
protected function getOrientationForItem( |
|
|
|
|
189
|
|
|
Item $itemToPack, |
190
|
|
|
?PackedItem $prevItem, |
191
|
|
|
bool $isLastItem, |
192
|
|
|
int $maxWidth, |
193
|
|
|
int $maxLength, |
194
|
|
|
int $maxDepth |
195
|
|
|
): ?OrientatedItem { |
196
|
36 |
|
$this->logger->debug( |
197
|
36 |
|
"evaluating item {$itemToPack->getDescription()} for fit", |
198
|
|
|
[ |
199
|
36 |
|
'item' => $itemToPack, |
200
|
|
|
'space' => [ |
201
|
36 |
|
'maxWidth' => $maxWidth, |
202
|
36 |
|
'maxLength' => $maxLength, |
203
|
36 |
|
'maxDepth' => $maxDepth, |
204
|
|
|
], |
205
|
|
|
] |
206
|
|
|
); |
207
|
|
|
|
208
|
36 |
|
$orientatedItemFactory = new OrientatedItemFactory(); |
209
|
36 |
|
$orientatedItemFactory->setLogger($this->logger); |
210
|
36 |
|
$orientatedItem = $orientatedItemFactory->getBestOrientation($this->box, $itemToPack, $prevItem, $isLastItem, $maxWidth, $maxLength, $maxDepth); |
211
|
|
|
|
212
|
36 |
|
return $orientatedItem; |
213
|
|
|
} |
214
|
|
|
|
215
|
|
|
/** |
216
|
|
|
* Figure out if we can stack the next item vertically on top of this rather than side by side |
217
|
|
|
* Used when we've packed a tall item, and have just put a shorter one next to it |
218
|
|
|
* |
219
|
|
|
* @param PackedItemList $packedItems |
220
|
|
|
* @param ?PackedItem $prevItem |
|
|
|
|
221
|
|
|
* @param int $maxWidth |
222
|
|
|
* @param int $maxLength |
223
|
|
|
* @param int $maxDepth |
224
|
|
|
* @param int $x |
225
|
|
|
* @param int $y |
226
|
|
|
* @param int $z |
227
|
|
|
*/ |
228
|
36 |
|
protected function tryAndStackItemsIntoSpace( |
229
|
|
|
PackedItemList $packedItems, |
230
|
|
|
?PackedItem $prevItem, |
231
|
|
|
int $maxWidth, |
232
|
|
|
int $maxLength, |
233
|
|
|
int $maxDepth, |
234
|
|
|
int $x, |
235
|
|
|
int $y, |
236
|
|
|
int $z |
237
|
|
|
): void { |
238
|
36 |
|
while (count($this->items) > 0 && $this->checkNonDimensionalConstraints($this->items->top(), $packedItems)) { |
239
|
32 |
|
$stackedItem = $this->getOrientationForItem( |
240
|
32 |
|
$this->items->top(), |
241
|
32 |
|
$prevItem, |
242
|
32 |
|
$this->items->count() === 1, |
243
|
32 |
|
$maxWidth, |
244
|
32 |
|
$maxLength, |
245
|
32 |
|
$maxDepth |
246
|
|
|
); |
247
|
32 |
|
if ($stackedItem) { |
248
|
3 |
|
$this->remainingWeight -= $this->items->top()->getWeight(); |
249
|
3 |
|
$packedItems->insert(PackedItem::fromOrientatedItem($stackedItem, $x, $y, $z)); |
250
|
3 |
|
$this->items->extract(); |
251
|
3 |
|
$maxDepth -= $stackedItem->getDepth(); |
252
|
3 |
|
$z += $stackedItem->getDepth(); |
253
|
|
|
} else { |
254
|
|
|
break; |
255
|
|
|
} |
256
|
|
|
} |
257
|
|
|
} |
258
|
|
|
|
259
|
|
|
/** |
260
|
|
|
* Check item generally fits into box |
261
|
|
|
* |
262
|
|
|
* @param Item $itemToPack |
263
|
|
|
* @param PackedItemList $packedItems |
264
|
|
|
* |
265
|
|
|
* @return bool |
266
|
|
|
*/ |
267
|
36 |
|
protected function checkConstraints( |
268
|
|
|
Item $itemToPack, |
269
|
|
|
PackedItemList $packedItems |
270
|
|
|
): bool { |
271
|
36 |
|
return $this->checkNonDimensionalConstraints($itemToPack, $packedItems) && |
272
|
36 |
|
$this->checkDimensionalConstraints($itemToPack); |
273
|
|
|
} |
274
|
|
|
|
275
|
|
|
/** |
276
|
|
|
* As well as purely dimensional constraints, there are other constraints that need to be met |
277
|
|
|
* e.g. weight limits or item-specific restrictions (e.g. max <x> batteries per box) |
278
|
|
|
* |
279
|
|
|
* @param Item $itemToPack |
280
|
|
|
* @param PackedItemList $packedItems |
281
|
|
|
* |
282
|
|
|
* @return bool |
283
|
|
|
*/ |
284
|
36 |
|
protected function checkNonDimensionalConstraints(Item $itemToPack, PackedItemList $packedItems): bool |
285
|
|
|
{ |
286
|
36 |
|
$weightOK = $itemToPack->getWeight() <= $this->remainingWeight; |
287
|
|
|
|
288
|
36 |
|
if ($itemToPack instanceof ConstrainedItem) { |
289
|
1 |
|
return $weightOK && $itemToPack->canBePackedInBox($packedItems, $this->box); |
290
|
|
|
} |
291
|
|
|
|
292
|
|
|
return $weightOK; |
293
|
|
|
} |
294
|
|
|
|
295
|
|
|
/** |
296
|
|
|
* Check the item physically fits in the box (at all) |
297
|
|
|
* |
298
|
|
|
* @param Item $itemToPack |
299
|
|
|
* |
300
|
|
|
* @return bool |
301
|
|
|
*/ |
302
|
36 |
|
protected function checkDimensionalConstraints(Item $itemToPack): bool |
303
|
|
|
{ |
304
|
36 |
|
$orientatedItemFactory = new OrientatedItemFactory(); |
305
|
36 |
|
$orientatedItemFactory->setLogger($this->logger); |
306
|
36 |
|
return !!$orientatedItemFactory->getPossibleOrientationsInEmptyBox($itemToPack, $this->box); |
307
|
|
|
} |
308
|
|
|
|
309
|
|
|
/** |
310
|
|
|
* Reintegrate skipped items into main list when nothing left to process |
311
|
|
|
*/ |
312
|
36 |
|
protected function rebuildItemList(): void { |
313
|
36 |
|
if (count($this->items) === 0) { |
314
|
36 |
|
$this->items = $this->skippedItems; |
315
|
36 |
|
$this->skippedItems = new ItemList(); |
316
|
|
|
} |
317
|
|
|
} |
318
|
|
|
|
319
|
|
|
/** |
320
|
|
|
* @param PackedItemList $packedItems |
321
|
|
|
* |
322
|
|
|
* @return PackedBox |
323
|
|
|
*/ |
324
|
36 |
|
protected function createPackedBox(PackedItemList $packedItems): PackedBox |
325
|
|
|
{ |
326
|
|
|
//if we rotated the box for packing, need to swap back width/length of the packed items |
327
|
36 |
|
if ($this->boxRotated) { |
328
|
9 |
|
$items = iterator_to_array($packedItems, false); |
329
|
9 |
|
$packedItems = new PackedItemList(); |
330
|
|
|
/** @var PackedItem $item */ |
331
|
9 |
|
foreach($items as $item) { |
332
|
9 |
|
$packedItems->insert( |
333
|
9 |
|
new PackedItem( |
334
|
9 |
|
$item->getItem(), |
335
|
9 |
|
$item->getY(), |
336
|
9 |
|
$item->getX(), |
337
|
9 |
|
$item->getZ(), |
338
|
9 |
|
$item->getLength(), |
339
|
9 |
|
$item->getWidth(), |
340
|
9 |
|
$item->getDepth() |
341
|
|
|
) |
342
|
|
|
); |
343
|
|
|
} |
344
|
|
|
} |
345
|
|
|
|
346
|
36 |
|
return new PackedBox($this->box, $packedItems); |
347
|
|
|
} |
348
|
|
|
} |
349
|
|
|
|
This check marks PHPDoc comments that could not be parsed by our parser. To see which comment annotations we can parse, please refer to our documentation on supported doc-types.