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 function max; |
12
|
|
|
use Psr\Log\LoggerAwareInterface; |
13
|
|
|
use Psr\Log\LoggerInterface; |
14
|
|
|
use Psr\Log\NullLogger; |
15
|
|
|
|
16
|
|
|
/** |
17
|
|
|
* Layer packer. |
18
|
|
|
* |
19
|
|
|
* @internal |
20
|
|
|
* @author Doug Wright |
21
|
|
|
*/ |
22
|
|
|
class LayerPacker implements LoggerAwareInterface |
23
|
|
|
{ |
24
|
|
|
/** |
25
|
|
|
* The logger instance. |
26
|
|
|
* |
27
|
|
|
* @var LoggerInterface |
28
|
|
|
*/ |
29
|
|
|
private $logger; |
30
|
|
|
|
31
|
|
|
/** |
32
|
|
|
* Box to pack items into. |
33
|
|
|
* |
34
|
|
|
* @var Box |
35
|
|
|
*/ |
36
|
|
|
private $box; |
37
|
|
|
|
38
|
|
|
/** |
39
|
|
|
* Whether the packer is in single-pass mode. |
40
|
|
|
* |
41
|
|
|
* @var bool |
42
|
|
|
*/ |
43
|
|
|
private $singlePassMode = false; |
44
|
|
|
|
45
|
|
|
/** |
46
|
|
|
* @var OrientatedItemFactory |
47
|
|
|
*/ |
48
|
|
|
private $orientatedItemFactory; |
49
|
|
|
|
50
|
|
|
/** |
51
|
|
|
* Constructor. |
52
|
|
|
*/ |
53
|
68 |
|
public function __construct(Box $box) |
54
|
|
|
{ |
55
|
68 |
|
$this->box = $box; |
56
|
68 |
|
$this->logger = new NullLogger(); |
57
|
|
|
|
58
|
68 |
|
$this->orientatedItemFactory = new OrientatedItemFactory($this->box); |
59
|
68 |
|
$this->orientatedItemFactory->setLogger($this->logger); |
60
|
68 |
|
} |
61
|
|
|
|
62
|
|
|
/** |
63
|
|
|
* Sets a logger. |
64
|
|
|
*/ |
65
|
68 |
|
public function setLogger(LoggerInterface $logger): void |
66
|
|
|
{ |
67
|
68 |
|
$this->logger = $logger; |
68
|
68 |
|
$this->orientatedItemFactory->setLogger($logger); |
69
|
68 |
|
} |
70
|
|
|
|
71
|
56 |
|
public function setSinglePassMode(bool $singlePassMode): void |
72
|
|
|
{ |
73
|
56 |
|
$this->singlePassMode = $singlePassMode; |
74
|
56 |
|
$this->orientatedItemFactory->setSinglePassMode($singlePassMode); |
75
|
56 |
|
} |
76
|
|
|
|
77
|
|
|
/** |
78
|
|
|
* Pack items into an individual vertical layer. |
79
|
|
|
*/ |
80
|
68 |
|
public function packLayer(ItemList &$items, PackedItemList $packedItemList, int $startX, int $startY, int $startZ, int $widthForLayer, int $lengthForLayer, int $depthForLayer, int $guidelineLayerDepth, bool $considerStability): PackedLayer |
81
|
|
|
{ |
82
|
68 |
|
$layer = new PackedLayer(); |
83
|
68 |
|
$x = $startX; |
84
|
68 |
|
$y = $startY; |
85
|
68 |
|
$z = $startZ; |
86
|
68 |
|
$lengthLeft = $lengthForLayer; |
87
|
68 |
|
$rowLength = 0; |
88
|
68 |
|
$prevItem = null; |
89
|
68 |
|
$skippedItems = []; |
90
|
68 |
|
$remainingWeightAllowed = $this->box->getMaxWeight() - $this->box->getEmptyWeight() - $packedItemList->getWeight(); |
91
|
|
|
|
92
|
68 |
|
while ($items->count() > 0) { |
93
|
68 |
|
$itemToPack = $items->extract(); |
94
|
|
|
|
95
|
|
|
//skip items that will never fit e.g. too heavy |
96
|
68 |
|
if ($itemToPack->getWeight() > $remainingWeightAllowed) { |
97
|
8 |
|
continue; |
98
|
|
|
} |
99
|
|
|
|
100
|
68 |
|
$orientatedItem = $this->orientatedItemFactory->getBestOrientation($itemToPack, $prevItem, $items, $widthForLayer - $x, $lengthLeft, $depthForLayer, $rowLength, $x, $y, $z, $packedItemList, $considerStability); |
101
|
|
|
|
102
|
68 |
|
if ($orientatedItem instanceof OrientatedItem) { |
103
|
68 |
|
$packedItem = PackedItem::fromOrientatedItem($orientatedItem, $x, $y, $z); |
104
|
68 |
|
$layer->insert($packedItem); |
105
|
68 |
|
$remainingWeightAllowed -= $itemToPack->getWeight(); |
106
|
68 |
|
$packedItemList->insert($packedItem); |
107
|
|
|
|
108
|
68 |
|
$rowLength = max($rowLength, $packedItem->getLength()); |
109
|
|
|
|
110
|
|
|
//Figure out if we can stack the next item vertically on top of this rather than side by side |
111
|
|
|
//e.g. when we've packed a tall item, and have just put a shorter one next to it. |
112
|
68 |
|
$this->packVerticallyInsideItemFootprint($layer, $packedItem, $packedItemList, $items, $remainingWeightAllowed, $guidelineLayerDepth, $rowLength, $x, $y, $z, $considerStability); |
113
|
|
|
|
114
|
68 |
|
$prevItem = $orientatedItem; |
115
|
|
|
|
116
|
|
|
//Having now placed an item, there is space *within the same row* along the length. Pack into that. |
117
|
68 |
|
if (!$this->singlePassMode && $rowLength - $orientatedItem->getLength() > 0) { |
118
|
18 |
|
$layer->merge($this->packLayer($items, $packedItemList, $x, $y + $orientatedItem->getLength(), $z, $widthForLayer, $rowLength - $orientatedItem->getLength(), $depthForLayer, $layer->getDepth(), $considerStability)); |
119
|
|
|
} |
120
|
|
|
|
121
|
68 |
|
$x += $packedItem->getWidth(); |
122
|
|
|
|
123
|
68 |
|
if ($items->count() === 0 && $skippedItems) { |
|
|
|
|
124
|
10 |
|
$items = ItemList::fromArray(array_merge($skippedItems, iterator_to_array($items)), true); |
125
|
10 |
|
$skippedItems = []; |
126
|
|
|
} |
127
|
68 |
|
continue; |
128
|
|
|
} |
129
|
|
|
|
130
|
60 |
|
if ($items->count() > 0) { // skip for now, move on to the next item |
131
|
50 |
|
$this->logger->debug("doesn't fit, skipping for now"); |
132
|
50 |
|
$skippedItems[] = $itemToPack; |
133
|
|
|
// abandon here if next item is the same, no point trying to keep going. Last time is not skipped, need that to trigger appropriate reset logic |
134
|
50 |
|
while ($items->count() > 1 && static::isSameDimensions($itemToPack, $items->top())) { |
135
|
36 |
|
$skippedItems[] = $items->extract(); |
136
|
|
|
} |
137
|
50 |
|
continue; |
138
|
|
|
} |
139
|
|
|
|
140
|
60 |
|
if ($x > $startX) { |
141
|
60 |
|
$this->logger->debug('No more fit in width wise, resetting for new row'); |
142
|
60 |
|
$lengthLeft -= $rowLength; |
143
|
60 |
|
$y += $rowLength; |
144
|
60 |
|
$x = $startX; |
145
|
60 |
|
$rowLength = 0; |
146
|
60 |
|
$skippedItems[] = $itemToPack; |
147
|
60 |
|
$items = ItemList::fromArray($skippedItems, true); |
148
|
60 |
|
$skippedItems = []; |
149
|
60 |
|
$prevItem = null; |
150
|
60 |
|
continue; |
151
|
|
|
} |
152
|
|
|
|
153
|
52 |
|
$this->logger->debug('no items fit, so starting next vertical layer'); |
154
|
52 |
|
$skippedItems[] = $itemToPack; |
155
|
|
|
|
156
|
52 |
|
$items = ItemList::fromArray(array_merge($skippedItems, iterator_to_array($items)), true); |
157
|
|
|
|
158
|
52 |
|
return $layer; |
159
|
|
|
} |
160
|
|
|
|
161
|
68 |
|
return $layer; |
162
|
|
|
} |
163
|
|
|
|
164
|
68 |
|
private function packVerticallyInsideItemFootprint(PackedLayer $layer, PackedItem $packedItem, PackedItemList $packedItemList, ItemList &$items, int &$remainingWeightAllowed, int $guidelineLayerDepth, int $rowLength, int $x, int $y, int $z, bool $considerStability): void |
165
|
|
|
{ |
166
|
68 |
|
$stackableDepth = ($guidelineLayerDepth ?: $layer->getDepth()) - $packedItem->getDepth(); |
167
|
68 |
|
$stackedZ = $z + $packedItem->getDepth(); |
168
|
68 |
|
$stackSkippedItems = []; |
169
|
68 |
|
$stackedItem = $packedItem->toOrientatedItem(); |
170
|
68 |
|
while ($stackableDepth > 0 && $items->count() > 0) { |
171
|
28 |
|
$itemToTryStacking = $items->extract(); |
172
|
|
|
|
173
|
|
|
//skip items that will never fit |
174
|
28 |
|
if ($itemToTryStacking->getWeight() > $remainingWeightAllowed) { |
175
|
|
|
continue; |
176
|
|
|
} |
177
|
|
|
|
178
|
28 |
|
$stackedItem = $this->orientatedItemFactory->getBestOrientation($itemToTryStacking, $stackedItem, $items, $packedItem->getWidth(), $packedItem->getLength(), $stackableDepth, $rowLength, $x, $y, $stackedZ, $packedItemList, $considerStability); |
179
|
28 |
|
if ($stackedItem) { |
180
|
18 |
|
$packedStackedItem = PackedItem::fromOrientatedItem($stackedItem, $x, $y, $stackedZ); |
181
|
18 |
|
$layer->insert($packedStackedItem); |
182
|
18 |
|
$remainingWeightAllowed -= $itemToTryStacking->getWeight(); |
183
|
18 |
|
$packedItemList->insert($packedStackedItem); |
184
|
18 |
|
$stackableDepth -= $stackedItem->getDepth(); |
185
|
18 |
|
$stackedZ += $stackedItem->getDepth(); |
186
|
18 |
|
continue; |
187
|
|
|
} |
188
|
|
|
|
189
|
24 |
|
$stackSkippedItems[] = $itemToTryStacking; |
190
|
|
|
// abandon here if next item is the same, no point trying to keep going |
191
|
24 |
|
while ($items->count() > 0 && static::isSameDimensions($itemToTryStacking, $items->top())) { |
192
|
16 |
|
$stackSkippedItems[] = $items->extract(); |
193
|
|
|
} |
194
|
|
|
} |
195
|
68 |
|
if ($stackSkippedItems) { |
196
|
24 |
|
$items = ItemList::fromArray(array_merge($stackSkippedItems, iterator_to_array($items)), true); |
197
|
|
|
} |
198
|
68 |
|
} |
199
|
|
|
|
200
|
|
|
private function checkNonDimensionalConstraints(Item $itemToPack, int $remainingWeightAllowed, PackedItemList $packedItemList): bool |
|
|
|
|
201
|
|
|
{ |
202
|
|
|
$customConstraintsOK = true; |
203
|
|
|
if ($itemToPack instanceof ConstrainedItem && !$this->box instanceof WorkingVolume) { |
|
|
|
|
204
|
|
|
$customConstraintsOK = $itemToPack->canBePackedInBox($packedItemList, $this->box); |
|
|
|
|
205
|
|
|
} |
206
|
|
|
|
207
|
|
|
return $customConstraintsOK && $itemToPack->getWeight() <= $remainingWeightAllowed; |
208
|
|
|
} |
209
|
|
|
|
210
|
|
|
/** |
211
|
|
|
* Compare two items to see if they have same dimensions. |
212
|
|
|
*/ |
213
|
46 |
|
private static function isSameDimensions(Item $itemA, Item $itemB): bool |
214
|
|
|
{ |
215
|
46 |
|
if ($itemA === $itemB) { |
216
|
32 |
|
return true; |
217
|
|
|
} |
218
|
22 |
|
$itemADimensions = [$itemA->getWidth(), $itemA->getLength(), $itemA->getDepth()]; |
219
|
22 |
|
$itemBDimensions = [$itemB->getWidth(), $itemB->getLength(), $itemB->getDepth()]; |
220
|
22 |
|
sort($itemADimensions); |
221
|
22 |
|
sort($itemBDimensions); |
222
|
|
|
|
223
|
22 |
|
return $itemADimensions === $itemBDimensions; |
224
|
|
|
} |
225
|
|
|
} |
226
|
|
|
|
This check marks implicit conversions of arrays to boolean values in a comparison. While in PHP an empty array is considered to be equal (but not identical) to false, this is not always apparent.
Consider making the comparison explicit by using
empty(..)
or! empty(...)
instead.