These results are based on our legacy PHP analysis, consider migrating to our new PHP analysis engine instead. Learn more
1 | <?php |
||
2 | /** |
||
3 | * Box packing (3D bin packing, knapsack problem) |
||
4 | * @package BoxPacker |
||
5 | * @author Doug Wright |
||
6 | */ |
||
7 | declare(strict_types=1); |
||
8 | namespace DVDoug\BoxPacker; |
||
9 | |||
10 | use Psr\Log\LoggerAwareInterface; |
||
11 | use Psr\Log\LoggerAwareTrait; |
||
12 | |||
13 | /** |
||
14 | * Figure out orientations for an item and a given set of dimensions |
||
15 | * @author Doug Wright |
||
16 | * @package BoxPacker |
||
17 | */ |
||
18 | class OrientatedItemFactory implements LoggerAwareInterface |
||
19 | { |
||
20 | use LoggerAwareTrait; |
||
21 | |||
22 | /** |
||
23 | * @var OrientatedItem[] |
||
24 | */ |
||
25 | protected static $emptyBoxCache = []; |
||
26 | |||
27 | /** |
||
28 | * Get the best orientation for an item |
||
29 | * @param Box $box |
||
30 | * @param Item $item |
||
31 | * @param ?PackedItem $prevItem |
||
32 | * @param bool $isLastItem |
||
33 | * @param int $widthLeft |
||
34 | * @param int $lengthLeft |
||
35 | * @param int $depthLeft |
||
36 | * @return ?OrientatedItem |
||
37 | */ |
||
38 | 36 | public function getBestOrientation( |
|
0 ignored issues
–
show
|
|||
39 | Box $box, |
||
40 | Item $item, |
||
41 | ?PackedItem $prevItem, |
||
42 | bool $isLastItem, |
||
43 | int $widthLeft, |
||
44 | int $lengthLeft, |
||
45 | int $depthLeft |
||
46 | ): ?OrientatedItem { |
||
47 | |||
48 | 36 | $possibleOrientations = $this->getPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft); |
|
49 | 36 | $usableOrientations = $this->getUsableOrientations($possibleOrientations, $box, $item, $isLastItem); |
|
50 | |||
51 | 36 | if (empty($usableOrientations)) { |
|
52 | 32 | return null; |
|
53 | } |
||
54 | |||
55 | 36 | usort($usableOrientations, function (OrientatedItem $a, OrientatedItem $b) use ($widthLeft, $lengthLeft) { |
|
56 | 34 | $orientationAWidthLeft = $widthLeft - $a->getWidth(); |
|
57 | 34 | $orientationALengthLeft = $lengthLeft - $a->getLength(); |
|
58 | 34 | $orientationBWidthLeft = $widthLeft - $b->getWidth(); |
|
59 | 34 | $orientationBLengthLeft = $lengthLeft - $b->getLength(); |
|
60 | |||
61 | 34 | $orientationAMinGap = min($orientationAWidthLeft, $orientationALengthLeft); |
|
62 | 34 | $orientationBMinGap = min($orientationBWidthLeft, $orientationBLengthLeft); |
|
63 | |||
64 | 34 | if ($orientationAMinGap === 0) { |
|
65 | 13 | return -1; |
|
66 | 25 | } elseif ($orientationBMinGap === 0) { |
|
67 | 2 | return 1; |
|
68 | } else { |
||
69 | 24 | return min($orientationAWidthLeft, $orientationALengthLeft) <=> min($orientationBWidthLeft, $orientationBLengthLeft); |
|
70 | } |
||
71 | 36 | }); |
|
72 | |||
73 | 36 | $bestFit = reset($usableOrientations); |
|
74 | 36 | $this->logger->debug("Selected best fit orientation", ['orientation' => $bestFit]); |
|
75 | 36 | return $bestFit; |
|
76 | } |
||
77 | |||
78 | /** |
||
79 | * Find all possible orientations for an item |
||
80 | * @param Item $item |
||
81 | * @param ?PackedItem $prevItem |
||
82 | * @param int $widthLeft |
||
83 | * @param int $lengthLeft |
||
84 | * @param int $depthLeft |
||
85 | * @return OrientatedItem[] |
||
86 | */ |
||
87 | 36 | public function getPossibleOrientations( |
|
88 | Item $item, |
||
89 | ?PackedItem $prevItem, |
||
90 | int $widthLeft, |
||
91 | int $lengthLeft, |
||
92 | int $depthLeft |
||
93 | ): array { |
||
94 | |||
95 | 36 | $orientations = []; |
|
96 | |||
97 | //Special case items that are the same as what we just packed - keep orientation |
||
98 | /** @noinspection PhpNonStrictObjectEqualityInspection */ |
||
99 | 36 | if ($prevItem && $prevItem->getItem() == $item) { |
|
100 | 13 | $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth()); |
|
101 | } else { |
||
102 | |||
103 | //simple 2D rotation |
||
104 | 36 | $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth()); |
|
105 | 36 | $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth()); |
|
106 | |||
107 | //add 3D rotation if we're allowed |
||
108 | 36 | if (!$item->getKeepFlat()) { |
|
109 | 15 | $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength()); |
|
110 | 15 | $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth()); |
|
111 | 15 | $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength()); |
|
112 | 15 | $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth()); |
|
113 | } |
||
114 | } |
||
115 | |||
116 | //remove any that simply don't fit |
||
117 | 36 | return array_filter($orientations, function(OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) { |
|
118 | 36 | return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft; |
|
119 | 36 | }); |
|
120 | } |
||
121 | |||
122 | /** |
||
123 | * @param Item $item |
||
124 | * @param Box $box |
||
125 | * @return OrientatedItem[] |
||
126 | */ |
||
127 | 36 | public function getPossibleOrientationsInEmptyBox(Item $item, Box $box): array |
|
128 | { |
||
129 | 36 | $cacheKey = $item->getWidth() . |
|
130 | 36 | '|' . |
|
131 | 36 | $item->getLength() . |
|
132 | 36 | '|' . |
|
133 | 36 | $item->getDepth() . |
|
134 | 36 | '|' . |
|
135 | 36 | ($item->getKeepFlat() ? '2D' : '3D') . |
|
136 | 36 | '|' . |
|
137 | 36 | $box->getInnerWidth() . |
|
138 | 36 | '|' . |
|
139 | 36 | $box->getInnerLength() . |
|
140 | 36 | '|' . |
|
141 | 36 | $box->getInnerDepth(); |
|
142 | |||
143 | 36 | if (isset(static::$emptyBoxCache[$cacheKey])) { |
|
144 | 31 | $orientations = static::$emptyBoxCache[$cacheKey]; |
|
145 | } else { |
||
146 | 32 | $orientations = $this->getPossibleOrientations( |
|
147 | 32 | $item, |
|
148 | 32 | null, |
|
149 | 32 | $box->getInnerWidth(), |
|
150 | 32 | $box->getInnerLength(), |
|
151 | 32 | $box->getInnerDepth() |
|
152 | ); |
||
153 | 32 | static::$emptyBoxCache[$cacheKey] = $orientations; |
|
154 | } |
||
155 | 36 | return $orientations; |
|
156 | } |
||
157 | |||
158 | /** |
||
159 | * @param OrientatedItem[] $possibleOrientations |
||
160 | * @param Box $box |
||
161 | * @param Item $item |
||
162 | * @param bool $isLastItem |
||
163 | * |
||
164 | * @return OrientatedItem[] |
||
165 | */ |
||
166 | 36 | protected function getUsableOrientations( |
|
167 | $possibleOrientations, |
||
168 | Box $box, |
||
169 | Item $item, |
||
170 | bool $isLastItem |
||
171 | ): array { |
||
172 | /* |
||
173 | * Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity) |
||
174 | */ |
||
175 | 36 | $stableOrientations = []; |
|
176 | 36 | $unstableOrientations = []; |
|
177 | |||
178 | 36 | foreach ($possibleOrientations as $o => $orientation) { |
|
179 | 36 | if ($orientation->isStable()) { |
|
180 | 31 | $stableOrientations[] = $orientation; |
|
181 | } else { |
||
182 | 8 | $unstableOrientations[] = $orientation; |
|
183 | } |
||
184 | } |
||
185 | |||
186 | 36 | $orientationsToUse = []; |
|
187 | |||
188 | /* |
||
189 | * We prefer to use stable orientations only, but allow unstable ones if either |
||
190 | * the item is the last one left to pack OR |
||
191 | * the item doesn't fit in the box any other way |
||
192 | */ |
||
193 | 36 | if (count($stableOrientations) > 0) { |
|
194 | 31 | $orientationsToUse = $stableOrientations; |
|
195 | 35 | } else if (count($unstableOrientations) > 0) { |
|
196 | 6 | $orientationsInEmptyBox = $this->getPossibleOrientationsInEmptyBox($item, $box); |
|
197 | |||
198 | 6 | $stableOrientationsInEmptyBox = array_filter( |
|
199 | 6 | $orientationsInEmptyBox, |
|
200 | 6 | function(OrientatedItem $orientation) { |
|
201 | 6 | return $orientation->isStable(); |
|
202 | 6 | } |
|
203 | ); |
||
204 | |||
205 | 6 | if ($isLastItem || count($stableOrientationsInEmptyBox) == 0) { |
|
206 | 6 | $orientationsToUse = $unstableOrientations; |
|
207 | } |
||
208 | } |
||
209 | |||
210 | 36 | return $orientationsToUse; |
|
211 | } |
||
212 | } |
||
213 | |||
214 |
Our type inference engine in quite powerful, but sometimes the code does not provide enough clues to go by. In these cases we request you to add a
@return
annotation as described here.