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\LoggerAwareTrait; |
||
13 | use function array_filter; |
||
14 | use function count; |
||
15 | use function min; |
||
16 | use function reset; |
||
17 | use function sort; |
||
18 | use function usort; |
||
19 | |||
20 | /** |
||
21 | * Figure out orientations for an item and a given set of dimensions. |
||
22 | * |
||
23 | * @author Doug Wright |
||
24 | */ |
||
25 | class OrientatedItemFactory implements LoggerAwareInterface |
||
26 | { |
||
27 | use LoggerAwareTrait; |
||
28 | |||
29 | /** @var Item */ |
||
30 | protected $item; |
||
31 | |||
32 | /** @var Box */ |
||
33 | protected $box; |
||
34 | |||
35 | /** |
||
36 | * @var OrientatedItem[] |
||
37 | */ |
||
38 | protected static $emptyBoxCache = []; |
||
39 | |||
40 | 22 | public function __construct(Item $item, Box $box) |
|
41 | { |
||
42 | 22 | $this->item = $item; |
|
43 | 22 | $this->box = $box; |
|
44 | 22 | } |
|
45 | |||
46 | /** |
||
47 | * Get the best orientation for an item. |
||
48 | * |
||
49 | * @param OrientatedItem|null $prevItem |
||
50 | * @param Item|null $nextItem |
||
51 | * @param bool $isLastItem |
||
52 | * @param int $widthLeft |
||
53 | * @param int $lengthLeft |
||
54 | * @param int $depthLeft |
||
55 | * |
||
56 | * @return OrientatedItem|null |
||
57 | */ |
||
58 | 21 | public function getBestOrientation( |
|
59 | ?OrientatedItem $prevItem, |
||
60 | ?Item $nextItem, |
||
61 | bool $isLastItem, |
||
62 | int $widthLeft, |
||
63 | int $lengthLeft, |
||
64 | int $depthLeft |
||
65 | ): ?OrientatedItem { |
||
66 | 21 | $possibleOrientations = $this->getPossibleOrientations($this->item, $prevItem, $widthLeft, $lengthLeft, $depthLeft); |
|
67 | 21 | $usableOrientations = $this->getUsableOrientations($possibleOrientations, $isLastItem); |
|
68 | |||
69 | 21 | if (empty($usableOrientations)) { |
|
70 | 20 | return null; |
|
71 | } |
||
72 | |||
73 | usort($usableOrientations, function (OrientatedItem $a, OrientatedItem $b) use ($widthLeft, $lengthLeft, $depthLeft, $nextItem) { |
||
74 | 21 | $orientationAWidthLeft = $widthLeft - $a->getWidth(); |
|
75 | 21 | $orientationALengthLeft = $lengthLeft - $a->getLength(); |
|
76 | 21 | $orientationBWidthLeft = $widthLeft - $b->getWidth(); |
|
77 | 21 | $orientationBLengthLeft = $lengthLeft - $b->getLength(); |
|
78 | |||
79 | 21 | $orientationAMinGap = min($orientationAWidthLeft, $orientationALengthLeft); |
|
80 | 21 | $orientationBMinGap = min($orientationBWidthLeft, $orientationBLengthLeft); |
|
81 | |||
82 | 21 | if ($orientationAMinGap === 0 && $orientationBMinGap !== 0) { // prefer A if it leaves no gap |
|
83 | return -1; |
||
84 | 21 | } elseif ($orientationBMinGap === 0 && $orientationAMinGap !== 0) { // prefer B if it leaves no gap |
|
85 | 1 | return 1; |
|
86 | } else { // prefer leaving room for next item in current row |
||
87 | 20 | if ($nextItem) { |
|
88 | 19 | $nextItemFitA = count($this->getPossibleOrientations($nextItem, $a, $orientationAWidthLeft, $orientationALengthLeft, $depthLeft)); |
|
89 | 19 | $nextItemFitB = count($this->getPossibleOrientations($nextItem, $b, $orientationBWidthLeft, $orientationBLengthLeft, $depthLeft)); |
|
90 | 19 | if ($nextItemFitA && !$nextItemFitB) { |
|
91 | return -1; |
||
92 | 19 | } elseif ($nextItemFitB && !$nextItemFitA) { |
|
93 | 1 | return 1; |
|
94 | } |
||
95 | } |
||
96 | // otherwise prefer leaving minimum possible gap, or the greatest footprint |
||
97 | 19 | return $orientationAMinGap <=> $orientationBMinGap ?: $a->getSurfaceFootprint() <=> $b->getSurfaceFootprint(); |
|
98 | } |
||
99 | 21 | }); |
|
100 | |||
101 | 21 | $bestFit = reset($usableOrientations); |
|
102 | 21 | $this->logger->debug('Selected best fit orientation', ['orientation' => $bestFit]); |
|
103 | |||
104 | 21 | return $bestFit; |
|
105 | } |
||
106 | |||
107 | /** |
||
108 | * Find all possible orientations for an item. |
||
109 | * |
||
110 | * @param Item $item |
||
111 | * @param OrientatedItem|null $prevItem |
||
112 | * @param int $widthLeft |
||
113 | * @param int $lengthLeft |
||
114 | * @param int $depthLeft |
||
115 | * |
||
116 | * @return OrientatedItem[] |
||
117 | */ |
||
118 | 21 | public function getPossibleOrientations( |
|
119 | Item $item, |
||
120 | ?OrientatedItem $prevItem, |
||
121 | int $widthLeft, |
||
122 | int $lengthLeft, |
||
123 | int $depthLeft |
||
124 | ): array { |
||
125 | 21 | $orientations = []; |
|
126 | |||
127 | //Special case items that are the same as what we just packed - keep orientation |
||
128 | 21 | if ($prevItem && $this->isSameDimensions($prevItem->getItem(), $item)) { |
|
129 | 17 | $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth()); |
|
130 | } else { |
||
131 | |||
132 | //simple 2D rotation |
||
133 | 21 | $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth()); |
|
134 | 21 | $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth()); |
|
135 | |||
136 | //add 3D rotation if we're allowed |
||
137 | 21 | if (!$item->getKeepFlat()) { |
|
138 | 13 | $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength()); |
|
139 | 13 | $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth()); |
|
140 | 13 | $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength()); |
|
141 | 13 | $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth()); |
|
142 | } |
||
143 | } |
||
144 | |||
145 | //remove any that simply don't fit |
||
146 | return array_filter($orientations, function (OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) { |
||
147 | 21 | return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft; |
|
148 | 21 | }); |
|
149 | } |
||
150 | |||
151 | /** |
||
152 | * @return OrientatedItem[] |
||
153 | */ |
||
154 | 22 | public function getPossibleOrientationsInEmptyBox(): array |
|
155 | { |
||
156 | 22 | $cacheKey = $this->item->getWidth(). |
|
157 | 22 | '|'. |
|
158 | 22 | $this->item->getLength(). |
|
159 | 22 | '|'. |
|
160 | 22 | $this->item->getDepth(). |
|
161 | 22 | '|'. |
|
162 | 22 | ($this->item->getKeepFlat() ? '2D' : '3D'). |
|
163 | 22 | '|'. |
|
164 | 22 | $this->box->getInnerWidth(). |
|
165 | 22 | '|'. |
|
166 | 22 | $this->box->getInnerLength(). |
|
167 | 22 | '|'. |
|
168 | 22 | $this->box->getInnerDepth(); |
|
169 | |||
170 | 22 | if (isset(static::$emptyBoxCache[$cacheKey])) { |
|
171 | 22 | $orientations = static::$emptyBoxCache[$cacheKey]; |
|
172 | } else { |
||
173 | 20 | $orientations = $this->getPossibleOrientations( |
|
174 | 20 | $this->item, |
|
175 | 20 | null, |
|
176 | 20 | $this->box->getInnerWidth(), |
|
177 | 20 | $this->box->getInnerLength(), |
|
178 | 20 | $this->box->getInnerDepth() |
|
179 | ); |
||
180 | 20 | static::$emptyBoxCache[$cacheKey] = $orientations; |
|
181 | } |
||
182 | |||
183 | 22 | return $orientations; |
|
1 ignored issue
–
show
Bug
Best Practice
introduced
by
Loading history...
|
|||
184 | } |
||
185 | |||
186 | /** |
||
187 | * @param OrientatedItem[] $possibleOrientations |
||
188 | * @param bool $isLastItem |
||
189 | * |
||
190 | * @return OrientatedItem[] |
||
191 | */ |
||
192 | 21 | protected function getUsableOrientations( |
|
193 | $possibleOrientations, |
||
194 | bool $isLastItem |
||
195 | ): array { |
||
196 | 21 | $orientationsToUse = $stableOrientations = $unstableOrientations = []; |
|
197 | |||
198 | // Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity) |
||
199 | 21 | foreach ($possibleOrientations as $orientation) { |
|
200 | 21 | if ($orientation->isStable()) { |
|
201 | 21 | $stableOrientations[] = $orientation; |
|
202 | } else { |
||
203 | 21 | $unstableOrientations[] = $orientation; |
|
204 | } |
||
205 | } |
||
206 | |||
207 | /* |
||
208 | * We prefer to use stable orientations only, but allow unstable ones if either |
||
209 | * the item is the last one left to pack OR |
||
210 | * the item doesn't fit in the box any other way |
||
211 | */ |
||
212 | 21 | if (count($stableOrientations) > 0) { |
|
213 | 21 | $orientationsToUse = $stableOrientations; |
|
214 | 20 | } elseif (count($unstableOrientations) > 0) { |
|
215 | $stableOrientationsInEmptyBox = $this->getStableOrientationsInEmptyBox(); |
||
216 | |||
217 | if ($isLastItem || count($stableOrientationsInEmptyBox) == 0) { |
||
218 | $orientationsToUse = $unstableOrientations; |
||
219 | } |
||
220 | } |
||
221 | |||
222 | 21 | return $orientationsToUse; |
|
223 | } |
||
224 | |||
225 | /** |
||
226 | * Return the orientations for this item if it were to be placed into the box with nothing else. |
||
227 | * |
||
228 | * @return array |
||
229 | */ |
||
230 | protected function getStableOrientationsInEmptyBox(): array |
||
231 | { |
||
232 | $orientationsInEmptyBox = $this->getPossibleOrientationsInEmptyBox(); |
||
233 | |||
234 | return array_filter( |
||
235 | $orientationsInEmptyBox, |
||
236 | function (OrientatedItem $orientation) { |
||
237 | return $orientation->isStable(); |
||
238 | } |
||
239 | ); |
||
240 | } |
||
241 | |||
242 | /** |
||
243 | * Compare two items to see if they have same dimensions. |
||
244 | * |
||
245 | * @param Item $itemA |
||
246 | * @param Item $itemB |
||
247 | * |
||
248 | * @return bool |
||
249 | */ |
||
250 | 20 | protected function isSameDimensions(Item $itemA, Item $itemB): bool |
|
251 | { |
||
252 | 20 | $itemADimensions = [$itemA->getWidth(), $itemA->getLength(), $itemA->getDepth()]; |
|
253 | 20 | $itemBDimensions = [$itemB->getWidth(), $itemB->getLength(), $itemB->getDepth()]; |
|
254 | 20 | sort($itemADimensions); |
|
255 | 20 | sort($itemBDimensions); |
|
256 | |||
257 | 20 | return $itemADimensions === $itemBDimensions; |
|
258 | } |
||
259 | } |
||
260 |