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 Psr\Log\LoggerAwareInterface; |
12
|
|
|
use Psr\Log\LoggerInterface; |
13
|
|
|
use Psr\Log\NullLogger; |
14
|
|
|
|
15
|
|
|
use function array_map; |
16
|
|
|
use function count; |
17
|
|
|
use function max; |
18
|
|
|
use function reset; |
19
|
|
|
use function usort; |
20
|
|
|
|
21
|
|
|
/** |
22
|
|
|
* Actual packer. |
23
|
|
|
*/ |
24
|
|
|
class VolumePacker implements LoggerAwareInterface |
25
|
|
|
{ |
26
|
|
|
protected LoggerInterface $logger; |
27
|
|
|
|
28
|
|
|
protected ItemList $items; |
29
|
|
|
|
30
|
|
|
protected bool $singlePassMode = false; |
31
|
|
|
|
32
|
|
|
protected bool $packAcrossWidthOnly = false; |
33
|
|
|
|
34
|
|
|
private readonly LayerPacker $layerPacker; |
35
|
|
|
|
36
|
|
|
protected bool $beStrictAboutItemOrdering = false; |
37
|
|
|
|
38
|
|
|
private readonly bool $hasConstrainedItems; |
39
|
|
|
|
40
|
|
|
private readonly bool $hasNoRotationItems; |
41
|
|
|
|
42
|
99 |
|
public function __construct(protected Box $box, ItemList $items) |
43
|
|
|
{ |
44
|
99 |
|
$this->items = clone $items; |
45
|
|
|
|
46
|
99 |
|
$this->logger = new NullLogger(); |
47
|
|
|
|
48
|
99 |
|
$this->hasConstrainedItems = $items->hasConstrainedItems(); |
|
|
|
|
49
|
99 |
|
$this->hasNoRotationItems = $items->hasNoRotationItems(); |
|
|
|
|
50
|
|
|
|
51
|
99 |
|
$this->layerPacker = new LayerPacker($this->box); |
|
|
|
|
52
|
99 |
|
$this->layerPacker->setLogger($this->logger); |
53
|
|
|
} |
54
|
|
|
|
55
|
|
|
/** |
56
|
|
|
* Sets a logger. |
57
|
|
|
*/ |
58
|
47 |
|
public function setLogger(LoggerInterface $logger): void |
59
|
|
|
{ |
60
|
47 |
|
$this->logger = $logger; |
61
|
47 |
|
$this->layerPacker->setLogger($logger); |
62
|
|
|
} |
63
|
|
|
|
64
|
1 |
|
public function packAcrossWidthOnly(): void |
65
|
|
|
{ |
66
|
1 |
|
$this->packAcrossWidthOnly = true; |
67
|
|
|
} |
68
|
|
|
|
69
|
40 |
|
public function beStrictAboutItemOrdering(bool $beStrict): void |
70
|
|
|
{ |
71
|
40 |
|
$this->beStrictAboutItemOrdering = $beStrict; |
72
|
40 |
|
$this->layerPacker->beStrictAboutItemOrdering($beStrict); |
73
|
|
|
} |
74
|
|
|
|
75
|
|
|
/** |
76
|
|
|
* @internal |
77
|
|
|
*/ |
78
|
19 |
|
public function setSinglePassMode(bool $singlePassMode): void |
79
|
|
|
{ |
80
|
19 |
|
$this->singlePassMode = $singlePassMode; |
81
|
19 |
|
if ($singlePassMode) { |
82
|
19 |
|
$this->packAcrossWidthOnly = true; |
83
|
|
|
} |
84
|
19 |
|
$this->layerPacker->setSinglePassMode($singlePassMode); |
85
|
|
|
} |
86
|
|
|
|
87
|
|
|
/** |
88
|
|
|
* Pack as many items as possible into specific given box. |
89
|
|
|
* |
90
|
|
|
* @return PackedBox packed box |
91
|
|
|
*/ |
92
|
99 |
|
public function pack(): PackedBox |
93
|
|
|
{ |
94
|
99 |
|
$orientatedItemFactory = new OrientatedItemFactory($this->box); |
95
|
99 |
|
$orientatedItemFactory->setLogger($this->logger); |
96
|
99 |
|
$this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}", ['box' => $this->box]); |
97
|
|
|
|
98
|
|
|
// Sometimes "space available" decisions depend on orientation of the box, so try both ways |
99
|
99 |
|
$rotationsToTest = [false]; |
100
|
99 |
|
if (!$this->packAcrossWidthOnly && !$this->hasNoRotationItems) { |
101
|
99 |
|
$rotationsToTest[] = true; |
102
|
|
|
} |
103
|
|
|
|
104
|
|
|
// The orientation of the first item can have an outsized effect on the rest of the placement, so special-case |
105
|
|
|
// that and try everything |
106
|
|
|
|
107
|
99 |
|
$boxPermutations = []; |
108
|
99 |
|
foreach ($rotationsToTest as $rotation) { |
109
|
99 |
|
if ($rotation) { |
110
|
32 |
|
$boxWidth = $this->box->getInnerLength(); |
111
|
32 |
|
$boxLength = $this->box->getInnerWidth(); |
112
|
|
|
} else { |
113
|
99 |
|
$boxWidth = $this->box->getInnerWidth(); |
114
|
99 |
|
$boxLength = $this->box->getInnerLength(); |
115
|
|
|
} |
116
|
|
|
|
117
|
99 |
|
$specialFirstItemOrientations = [null]; |
118
|
99 |
|
if (!$this->singlePassMode) { |
119
|
99 |
|
$specialFirstItemOrientations = $orientatedItemFactory->getPossibleOrientations($this->items->top(), null, $boxWidth, $boxLength, $this->box->getInnerDepth(), 0, 0, 0, new PackedItemList()) ?: [null]; |
120
|
|
|
} |
121
|
|
|
|
122
|
99 |
|
foreach ($specialFirstItemOrientations as $firstItemOrientation) { |
123
|
99 |
|
$boxPermutation = $this->packRotation($boxWidth, $boxLength, $firstItemOrientation); |
124
|
99 |
|
if ($boxPermutation->items->count() === $this->items->count()) { |
125
|
84 |
|
return $boxPermutation; |
126
|
|
|
} |
127
|
|
|
|
128
|
53 |
|
$boxPermutations[] = $boxPermutation; |
129
|
|
|
} |
130
|
|
|
} |
131
|
|
|
|
132
|
46 |
|
usort($boxPermutations, static fn (PackedBox $a, PackedBox $b) => $b->getVolumeUtilisation() <=> $a->getVolumeUtilisation()); |
133
|
|
|
|
134
|
46 |
|
return reset($boxPermutations); |
135
|
|
|
} |
136
|
|
|
|
137
|
|
|
/** |
138
|
|
|
* Pack as many items as possible into specific given box. |
139
|
|
|
* |
140
|
|
|
* @return PackedBox packed box |
141
|
|
|
*/ |
142
|
99 |
|
private function packRotation(int $boxWidth, int $boxLength, ?OrientatedItem $firstItemOrientation): PackedBox |
143
|
|
|
{ |
144
|
99 |
|
$this->logger->debug("[EVALUATING ROTATION] {$this->box->getReference()}", ['width' => $boxWidth, 'length' => $boxLength]); |
145
|
99 |
|
$this->layerPacker->setBoxIsRotated($this->box->getInnerWidth() !== $boxWidth); |
146
|
|
|
|
147
|
99 |
|
$layers = []; |
148
|
99 |
|
$items = clone $this->items; |
149
|
|
|
|
150
|
99 |
|
while ($items->count() > 0) { |
151
|
99 |
|
$layerStartDepth = self::getCurrentPackedDepth($layers); |
152
|
99 |
|
$packedItemList = $this->getPackedItemList($layers); |
153
|
|
|
|
154
|
99 |
|
if ($packedItemList->count() > 0) { |
155
|
71 |
|
$firstItemOrientation = null; |
156
|
|
|
} |
157
|
|
|
|
158
|
|
|
// do a preliminary layer pack to get the depth used |
159
|
99 |
|
$preliminaryItems = clone $items; |
160
|
99 |
|
$preliminaryLayer = $this->layerPacker->packLayer($preliminaryItems, clone $packedItemList, 0, 0, $layerStartDepth, $boxWidth, $boxLength, $this->box->getInnerDepth() - $layerStartDepth, 0, true, $firstItemOrientation); |
161
|
99 |
|
if (count($preliminaryLayer->getItems()) === 0) { |
162
|
49 |
|
break; |
163
|
|
|
} |
164
|
|
|
|
165
|
96 |
|
$preliminaryLayerDepth = $preliminaryLayer->getDepth(); |
166
|
96 |
|
if ($preliminaryLayerDepth === $preliminaryLayer->getItems()[0]->depth) { // preliminary === final |
167
|
93 |
|
$layers[] = $preliminaryLayer; |
168
|
93 |
|
$items = $preliminaryItems; |
169
|
|
|
} else { // redo with now-known-depth so that we can stack to that height from the first item |
170
|
15 |
|
$layers[] = $this->layerPacker->packLayer($items, $packedItemList, 0, 0, $layerStartDepth, $boxWidth, $boxLength, $this->box->getInnerDepth() - $layerStartDepth, $preliminaryLayerDepth, true, $firstItemOrientation); |
171
|
|
|
} |
172
|
|
|
} |
173
|
|
|
|
174
|
99 |
|
if (!$this->singlePassMode && $layers) { |
175
|
96 |
|
$layers = $this->stabiliseLayers($layers); |
176
|
|
|
|
177
|
|
|
// having packed layers, there may be tall, narrow gaps at the ends that can be utilised |
178
|
96 |
|
$maxLayerWidth = max(array_map(static fn (PackedLayer $layer) => $layer->getEndX(), $layers)); |
179
|
96 |
|
$layers[] = $this->layerPacker->packLayer($items, $this->getPackedItemList($layers), $maxLayerWidth, 0, 0, $boxWidth, $boxLength, $this->box->getInnerDepth(), $this->box->getInnerDepth(), false, null); |
180
|
|
|
|
181
|
96 |
|
$maxLayerLength = max(array_map(static fn (PackedLayer $layer) => $layer->getEndY(), $layers)); |
182
|
96 |
|
$layers[] = $this->layerPacker->packLayer($items, $this->getPackedItemList($layers), 0, $maxLayerLength, 0, $boxWidth, $boxLength, $this->box->getInnerDepth(), $this->box->getInnerDepth(), false, null); |
183
|
|
|
} |
184
|
|
|
|
185
|
99 |
|
$layers = $this->correctLayerRotation($layers, $boxWidth); |
186
|
|
|
|
187
|
99 |
|
return new PackedBox($this->box, $this->getPackedItemList($layers)); |
188
|
|
|
} |
189
|
|
|
|
190
|
|
|
/** |
191
|
|
|
* During packing, it is quite possible that layers have been created that aren't physically stable |
192
|
|
|
* i.e. they overhang the ones below. |
193
|
|
|
* |
194
|
|
|
* This function reorders them so that the ones with the greatest surface area are placed at the bottom |
195
|
|
|
* |
196
|
|
|
* @param PackedLayer[] $oldLayers |
197
|
|
|
* @return PackedLayer[] |
198
|
|
|
*/ |
199
|
96 |
|
private function stabiliseLayers(array $oldLayers): array |
200
|
|
|
{ |
201
|
96 |
|
if ($this->hasConstrainedItems || $this->beStrictAboutItemOrdering) { // constraints include position, so cannot change |
202
|
3 |
|
return $oldLayers; |
203
|
|
|
} |
204
|
|
|
|
205
|
95 |
|
$stabiliser = new LayerStabiliser(); |
206
|
|
|
|
207
|
95 |
|
return $stabiliser->stabilise($oldLayers); |
208
|
|
|
} |
209
|
|
|
|
210
|
|
|
/** |
211
|
|
|
* Swap back width/length of the packed items to match orientation of the box if needed. |
212
|
|
|
* |
213
|
|
|
* @param PackedLayer[] $oldLayers |
214
|
|
|
* |
215
|
|
|
* @return PackedLayer[] |
216
|
|
|
*/ |
217
|
99 |
|
private function correctLayerRotation(array $oldLayers, int $boxWidth): array |
218
|
|
|
{ |
219
|
99 |
|
if ($this->box->getInnerWidth() === $boxWidth) { |
220
|
99 |
|
return $oldLayers; |
221
|
|
|
} |
222
|
|
|
|
223
|
7 |
|
$newLayers = []; |
224
|
7 |
|
foreach ($oldLayers as $originalLayer) { |
225
|
7 |
|
$newLayer = new PackedLayer(); |
226
|
7 |
|
foreach ($originalLayer->getItems() as $item) { |
227
|
7 |
|
$packedItem = new PackedItem($item->item, $item->y, $item->x, $item->z, $item->length, $item->width, $item->depth); |
228
|
7 |
|
$newLayer->insert($packedItem); |
229
|
|
|
} |
230
|
7 |
|
$newLayers[] = $newLayer; |
231
|
|
|
} |
232
|
|
|
|
233
|
7 |
|
return $newLayers; |
234
|
|
|
} |
235
|
|
|
|
236
|
|
|
/** |
237
|
|
|
* Generate a single list of items packed. |
238
|
|
|
* @param PackedLayer[] $layers |
239
|
|
|
*/ |
240
|
99 |
|
private function getPackedItemList(array $layers): PackedItemList |
241
|
|
|
{ |
242
|
99 |
|
$packedItemList = new PackedItemList(); |
243
|
99 |
|
foreach ($layers as $layer) { |
244
|
96 |
|
foreach ($layer->getItems() as $packedItem) { |
245
|
96 |
|
$packedItemList->insert($packedItem); |
246
|
|
|
} |
247
|
|
|
} |
248
|
|
|
|
249
|
99 |
|
return $packedItemList; |
250
|
|
|
} |
251
|
|
|
|
252
|
|
|
/** |
253
|
|
|
* Return the current packed depth. |
254
|
|
|
* |
255
|
|
|
* @param PackedLayer[] $layers |
256
|
|
|
*/ |
257
|
99 |
|
private static function getCurrentPackedDepth(array $layers): int |
258
|
|
|
{ |
259
|
99 |
|
$depth = 0; |
260
|
99 |
|
foreach ($layers as $layer) { |
261
|
71 |
|
$depth += $layer->getDepth(); |
262
|
|
|
} |
263
|
|
|
|
264
|
99 |
|
return $depth; |
265
|
|
|
} |
266
|
|
|
} |
267
|
|
|
|