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(); |
|
0 ignored issues
–
show
Bug
introduced
by
Loading history...
|
|||
49 | 99 | $this->hasNoRotationItems = $items->hasNoRotationItems(); |
|
0 ignored issues
–
show
|
|||
50 | |||
51 | 99 | $this->layerPacker = new LayerPacker($this->box); |
|
0 ignored issues
–
show
|
|||
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 |