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_filter; |
||
16 | use function count; |
||
17 | use function usort; |
||
18 | |||
19 | /** |
||
20 | * Figure out orientations for an item and a given set of dimensions. |
||
21 | * @internal |
||
22 | */ |
||
23 | class OrientatedItemFactory implements LoggerAwareInterface |
||
24 | { |
||
25 | protected LoggerInterface $logger; |
||
26 | |||
27 | protected bool $singlePassMode = false; |
||
28 | |||
29 | protected bool $boxIsRotated = false; |
||
30 | |||
31 | /** |
||
32 | * @var array<string, bool> |
||
33 | */ |
||
34 | protected static array $emptyBoxStableItemOrientationCache = []; |
||
35 | |||
36 | 102 | public function __construct(protected Box $box) |
|
37 | { |
||
38 | 102 | $this->logger = new NullLogger(); |
|
39 | } |
||
40 | |||
41 | 99 | public function setLogger(LoggerInterface $logger): void |
|
42 | { |
||
43 | 99 | $this->logger = $logger; |
|
44 | } |
||
45 | |||
46 | 19 | public function setSinglePassMode(bool $singlePassMode): void |
|
47 | { |
||
48 | 19 | $this->singlePassMode = $singlePassMode; |
|
49 | } |
||
50 | |||
51 | 99 | public function setBoxIsRotated(bool $boxIsRotated): void |
|
52 | { |
||
53 | 99 | $this->boxIsRotated = $boxIsRotated; |
|
54 | } |
||
55 | |||
56 | /** |
||
57 | * Get the best orientation for an item. |
||
58 | */ |
||
59 | 92 | public function getBestOrientation( |
|
60 | Item $item, |
||
61 | ?OrientatedItem $prevItem, |
||
62 | ItemList $nextItems, |
||
63 | int $widthLeft, |
||
64 | int $lengthLeft, |
||
65 | int $depthLeft, |
||
66 | int $rowLength, |
||
67 | int $x, |
||
68 | int $y, |
||
69 | int $z, |
||
70 | PackedItemList $prevPackedItemList, |
||
71 | bool $considerStability |
||
72 | ): ?OrientatedItem { |
||
73 | 92 | $this->logger->debug( |
|
74 | 92 | "evaluating item {$item->getDescription()} for fit", |
|
75 | 92 | [ |
|
76 | 92 | 'item' => $item, |
|
77 | 92 | 'space' => [ |
|
78 | 92 | 'widthLeft' => $widthLeft, |
|
79 | 92 | 'lengthLeft' => $lengthLeft, |
|
80 | 92 | 'depthLeft' => $depthLeft, |
|
81 | 92 | ], |
|
82 | 92 | 'position' => [ |
|
83 | 92 | 'x' => $x, |
|
84 | 92 | 'y' => $y, |
|
85 | 92 | 'z' => $z, |
|
86 | 92 | ], |
|
87 | 92 | ] |
|
88 | 92 | ); |
|
89 | |||
90 | 92 | $possibleOrientations = $this->getPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft, $x, $y, $z, $prevPackedItemList); |
|
91 | 92 | $usableOrientations = $considerStability ? $this->getUsableOrientations($item, $possibleOrientations) : $possibleOrientations; |
|
92 | |||
93 | 92 | if (empty($usableOrientations)) { |
|
94 | 92 | return null; |
|
95 | } |
||
96 | |||
97 | 84 | $sorter = new OrientatedItemSorter($this, $this->singlePassMode, $widthLeft, $lengthLeft, $depthLeft, $nextItems, $rowLength, $x, $y, $z, $prevPackedItemList, $this->logger); |
|
98 | 84 | usort($usableOrientations, $sorter); |
|
99 | |||
100 | 84 | $this->logger->debug('Selected best fit orientation', ['orientation' => $usableOrientations[0]]); |
|
101 | |||
102 | 84 | return $usableOrientations[0]; |
|
103 | } |
||
104 | |||
105 | /** |
||
106 | * Find all possible orientations for an item. |
||
107 | * |
||
108 | * @return OrientatedItem[] |
||
109 | */ |
||
110 | 102 | public function getPossibleOrientations( |
|
111 | Item $item, |
||
112 | ?OrientatedItem $prevItem, |
||
113 | int $widthLeft, |
||
114 | int $lengthLeft, |
||
115 | int $depthLeft, |
||
116 | int $x, |
||
117 | int $y, |
||
118 | int $z, |
||
119 | PackedItemList $prevPackedItemList |
||
120 | ): array { |
||
121 | 102 | $permutations = $this->generatePermutations($item, $prevItem); |
|
122 | |||
123 | // remove any that simply don't fit |
||
124 | 102 | $orientations = []; |
|
125 | 102 | foreach ($permutations as $dimensions) { |
|
126 | 102 | if ($dimensions[0] <= $widthLeft && $dimensions[1] <= $lengthLeft && $dimensions[2] <= $depthLeft) { |
|
127 | 99 | $orientations[] = new OrientatedItem($item, $dimensions[0], $dimensions[1], $dimensions[2]); |
|
128 | } |
||
129 | } |
||
130 | |||
131 | 102 | if ($item instanceof ConstrainedPlacementItem && !$this->box instanceof WorkingVolume) { |
|
132 | 3 | $orientations = array_filter($orientations, function (OrientatedItem $i) use ($x, $y, $z, $prevPackedItemList): bool { |
|
133 | /** @var ConstrainedPlacementItem $constrainedItem */ |
||
134 | 3 | $constrainedItem = $i->item; |
|
135 | |||
136 | 3 | if ($this->boxIsRotated) { |
|
137 | 2 | $rotatedPrevPackedItemList = new PackedItemList(); |
|
138 | 2 | foreach ($prevPackedItemList as $prevPackedItem) { |
|
139 | 2 | $rotatedPrevPackedItemList->insert(new PackedItem($prevPackedItem->item, $prevPackedItem->y, $prevPackedItem->x, $prevPackedItem->z, $prevPackedItem->length, $prevPackedItem->width, $prevPackedItem->depth)); |
|
140 | } |
||
141 | |||
142 | 2 | return $constrainedItem->canBePacked(new PackedBox($this->box, $rotatedPrevPackedItemList), $y, $x, $z, $i->length, $i->width, $i->depth); |
|
143 | } else { |
||
144 | 3 | return $constrainedItem->canBePacked(new PackedBox($this->box, $prevPackedItemList), $x, $y, $z, $i->width, $i->length, $i->depth); |
|
145 | } |
||
146 | 3 | }); |
|
147 | } |
||
148 | |||
149 | 102 | return $orientations; |
|
150 | } |
||
151 | |||
152 | /** |
||
153 | * @param OrientatedItem[] $possibleOrientations |
||
154 | * @return OrientatedItem[] |
||
155 | */ |
||
156 | 92 | protected function getUsableOrientations( |
|
157 | Item $item, |
||
158 | array $possibleOrientations |
||
159 | ): array { |
||
160 | 92 | $stableOrientations = $unstableOrientations = []; |
|
161 | |||
162 | // Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity) |
||
163 | 92 | foreach ($possibleOrientations as $orientation) { |
|
164 | 84 | if ($orientation->isStable() || $this->box->getInnerDepth() === $orientation->depth) { |
|
165 | 82 | $stableOrientations[] = $orientation; |
|
166 | } else { |
||
167 | 12 | $unstableOrientations[] = $orientation; |
|
168 | } |
||
169 | } |
||
170 | |||
171 | /* |
||
172 | * We prefer to use stable orientations only, but allow unstable ones if |
||
173 | * the item doesn't fit in the box any other way |
||
174 | */ |
||
175 | 92 | if (count($stableOrientations) > 0) { |
|
176 | 82 | return $stableOrientations; |
|
177 | } |
||
178 | |||
179 | 92 | if ((count($unstableOrientations) > 0) && !$this->hasStableOrientationsInEmptyBox($item)) { |
|
180 | 5 | return $unstableOrientations; |
|
181 | } |
||
182 | |||
183 | 92 | return []; |
|
184 | } |
||
185 | |||
186 | /** |
||
187 | * Return the orientations for this item if it were to be placed into the box with nothing else. |
||
188 | */ |
||
189 | 10 | protected function hasStableOrientationsInEmptyBox(Item $item): bool |
|
190 | { |
||
191 | 10 | $cacheKey = $item->getWidth() . |
|
192 | 10 | '|' . |
|
193 | 10 | $item->getLength() . |
|
194 | 10 | '|' . |
|
195 | 10 | $item->getDepth() . |
|
196 | 10 | '|' . |
|
197 | 10 | $item->getAllowedRotation()->name . |
|
0 ignored issues
–
show
Bug
introduced
by
Loading history...
|
|||
198 | 10 | '|' . |
|
199 | 10 | $this->box->getInnerWidth() . |
|
200 | 10 | '|' . |
|
201 | 10 | $this->box->getInnerLength() . |
|
202 | 10 | '|' . |
|
203 | 10 | $this->box->getInnerDepth(); |
|
204 | |||
205 | 10 | if (isset(static::$emptyBoxStableItemOrientationCache[$cacheKey])) { |
|
206 | 9 | return static::$emptyBoxStableItemOrientationCache[$cacheKey]; |
|
207 | } |
||
208 | |||
209 | 10 | $orientations = $this->getPossibleOrientations( |
|
210 | 10 | $item, |
|
211 | 10 | null, |
|
212 | 10 | $this->box->getInnerWidth(), |
|
213 | 10 | $this->box->getInnerLength(), |
|
214 | 10 | $this->box->getInnerDepth(), |
|
215 | 10 | 0, |
|
216 | 10 | 0, |
|
217 | 10 | 0, |
|
218 | 10 | new PackedItemList() |
|
219 | 10 | ); |
|
220 | |||
221 | 10 | $stableOrientations = array_filter( |
|
222 | 10 | $orientations, |
|
223 | 10 | static fn (OrientatedItem $orientation) => $orientation->isStable() |
|
224 | 10 | ); |
|
225 | 10 | static::$emptyBoxStableItemOrientationCache[$cacheKey] = count($stableOrientations) > 0; |
|
226 | |||
227 | 10 | return static::$emptyBoxStableItemOrientationCache[$cacheKey]; |
|
228 | } |
||
229 | |||
230 | /** |
||
231 | * @return array<array<int>> |
||
232 | */ |
||
233 | 102 | private function generatePermutations(Item $item, ?OrientatedItem $prevItem): array |
|
234 | { |
||
235 | // Special case items that are the same as what we just packed - keep orientation |
||
236 | 102 | if ($prevItem && $prevItem->isSameDimensions($item)) { |
|
237 | 73 | return [[$prevItem->width, $prevItem->length, $prevItem->depth]]; |
|
238 | } |
||
239 | |||
240 | 102 | $permutations = []; |
|
241 | 102 | $w = $item->getWidth(); |
|
242 | 102 | $l = $item->getLength(); |
|
243 | 102 | $d = $item->getDepth(); |
|
244 | |||
245 | 102 | $permutations[$w . '|' . $l . '|' . $d] = [$w, $l, $d]; |
|
246 | |||
247 | 102 | if ($item->getAllowedRotation() !== Rotation::Never) { // simple 2D rotation |
|
248 | 101 | $permutations[$l . '|' . $w . '|' . $d] = [$l, $w, $d]; |
|
249 | } |
||
250 | |||
251 | 102 | if ($item->getAllowedRotation() === Rotation::BestFit) { // add 3D rotation if we're allowed |
|
252 | 70 | $permutations[$w . '|' . $d . '|' . $l] = [$w, $d, $l]; |
|
253 | 70 | $permutations[$l . '|' . $d . '|' . $w] = [$l, $d, $w]; |
|
254 | 70 | $permutations[$d . '|' . $w . '|' . $l] = [$d, $w, $l]; |
|
255 | 70 | $permutations[$d . '|' . $l . '|' . $w] = [$d, $l, $w]; |
|
256 | } |
||
257 | |||
258 | 102 | return $permutations; |
|
259 | } |
||
260 | } |
||
261 |