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 |
||
0 ignored issues
–
show
|
|||
32 | * @param bool $isLastItem |
||
33 | * @param int $widthLeft |
||
34 | * @param int $lengthLeft |
||
35 | * @param int $depthLeft |
||
36 | * @return ?OrientatedItem |
||
0 ignored issues
–
show
The doc-type
?OrientatedItem could not be parsed: Unknown type name "?OrientatedItem" at position 0. (view supported doc-types)
This check marks PHPDoc comments that could not be parsed by our parser. To see which comment annotations we can parse, please refer to our documentation on supported doc-types.
Loading history...
|
|||
37 | */ |
||
38 | 33 | public function getBestOrientation( |
|
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 | 33 | $possibleOrientations = $this->getPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft); |
|
49 | 33 | $usableOrientations = $this->getUsableOrientations($possibleOrientations, $box, $item, $isLastItem); |
|
50 | |||
51 | 33 | $orientationFits = []; |
|
52 | /** @var OrientatedItem $orientation */ |
||
53 | 33 | foreach ($usableOrientations as $o => $orientation) { |
|
54 | 33 | $orientationFit = min($widthLeft - $orientation->getWidth(), $lengthLeft - $orientation->getLength()); |
|
55 | 33 | $orientationFits[$o] = $orientationFit; |
|
56 | } |
||
57 | |||
58 | 33 | if (!empty($orientationFits)) { |
|
59 | 33 | asort($orientationFits); |
|
60 | 33 | reset($orientationFits); |
|
61 | 33 | $bestFit = $usableOrientations[key($orientationFits)]; |
|
62 | 33 | $this->logger->debug("Selected best fit orientation", ['orientation' => $bestFit]); |
|
63 | 33 | return $bestFit; |
|
64 | } else { |
||
65 | return null; |
||
66 | } |
||
67 | } |
||
68 | |||
69 | /** |
||
70 | * Find all possible orientations for an item |
||
71 | * @param Item $item |
||
72 | * @param ?PackedItem $prevItem |
||
0 ignored issues
–
show
The doc-type
?PackedItem could not be parsed: Unknown type name "?PackedItem" at position 0. (view supported doc-types)
This check marks PHPDoc comments that could not be parsed by our parser. To see which comment annotations we can parse, please refer to our documentation on supported doc-types.
Loading history...
|
|||
73 | * @param int $widthLeft |
||
74 | * @param int $lengthLeft |
||
75 | * @param int $depthLeft |
||
76 | * @return OrientatedItem[] |
||
77 | */ |
||
78 | 33 | public function getPossibleOrientations( |
|
79 | Item $item, |
||
80 | ?PackedItem $prevItem, |
||
81 | int $widthLeft, |
||
82 | int $lengthLeft, |
||
83 | int $depthLeft |
||
84 | ): array { |
||
85 | |||
86 | 33 | $orientations = []; |
|
87 | |||
88 | //Special case items that are the same as what we just packed - keep orientation |
||
89 | /** @noinspection PhpNonStrictObjectEqualityInspection */ |
||
90 | 33 | if ($prevItem && $prevItem->getItem() == $item) { |
|
91 | 10 | $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth()); |
|
92 | } else { |
||
93 | |||
94 | //simple 2D rotation |
||
95 | 33 | $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth()); |
|
96 | 33 | $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth()); |
|
97 | |||
98 | //add 3D rotation if we're allowed |
||
99 | 33 | if (!$item->getKeepFlat()) { |
|
100 | 13 | $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength()); |
|
101 | 13 | $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth()); |
|
102 | 13 | $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength()); |
|
103 | 13 | $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth()); |
|
104 | } |
||
105 | } |
||
106 | |||
107 | //remove any that simply don't fit |
||
108 | 33 | return array_filter($orientations, function(OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) { |
|
109 | 33 | return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft; |
|
110 | 33 | }); |
|
111 | } |
||
112 | |||
113 | /** |
||
114 | * @param Item $item |
||
115 | * @param Box $box |
||
116 | * @return OrientatedItem[] |
||
117 | */ |
||
118 | 33 | public function getPossibleOrientationsInEmptyBox(Item $item, Box $box): array |
|
119 | { |
||
120 | 33 | $cacheKey = $item->getWidth() . |
|
121 | 33 | '|' . |
|
122 | 33 | $item->getLength() . |
|
123 | 33 | '|' . |
|
124 | 33 | $item->getDepth() . |
|
125 | 33 | '|' . |
|
126 | 33 | ($item->getKeepFlat() ? '2D' : '3D') . |
|
127 | 33 | '|' . |
|
128 | 33 | $box->getInnerWidth() . |
|
129 | 33 | '|' . |
|
130 | 33 | $box->getInnerLength() . |
|
131 | 33 | '|' . |
|
132 | 33 | $box->getInnerDepth(); |
|
133 | |||
134 | 33 | if (isset(static::$emptyBoxCache[$cacheKey])) { |
|
135 | 28 | $orientations = static::$emptyBoxCache[$cacheKey]; |
|
136 | } else { |
||
137 | 30 | $orientations = $this->getPossibleOrientations( |
|
138 | 30 | $item, |
|
139 | 30 | null, |
|
140 | 30 | $box->getInnerWidth(), |
|
141 | 30 | $box->getInnerLength(), |
|
142 | 30 | $box->getInnerDepth() |
|
143 | ); |
||
144 | 30 | static::$emptyBoxCache[$cacheKey] = $orientations; |
|
145 | } |
||
146 | 33 | return $orientations; |
|
147 | } |
||
148 | |||
149 | /** |
||
150 | * @param OrientatedItem[] $possibleOrientations |
||
151 | * @param Box $box |
||
152 | * @param Item $item |
||
153 | * @param bool $isLastItem |
||
154 | * |
||
155 | * @return OrientatedItem[] |
||
156 | */ |
||
157 | 33 | protected function getUsableOrientations( |
|
158 | $possibleOrientations, |
||
159 | Box $box, |
||
160 | Item $item, |
||
161 | bool $isLastItem |
||
162 | ): array { |
||
163 | /* |
||
164 | * Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity) |
||
165 | */ |
||
166 | 33 | $stableOrientations = []; |
|
167 | 33 | $unstableOrientations = []; |
|
168 | |||
169 | 33 | foreach ($possibleOrientations as $o => $orientation) { |
|
170 | 33 | if ($orientation->isStable()) { |
|
171 | 28 | $stableOrientations[] = $orientation; |
|
172 | } else { |
||
173 | 8 | $unstableOrientations[] = $orientation; |
|
174 | } |
||
175 | } |
||
176 | |||
177 | 33 | $orientationsToUse = []; |
|
178 | |||
179 | /* |
||
180 | * We prefer to use stable orientations only, but allow unstable ones if either |
||
181 | * the item is the last one left to pack OR |
||
182 | * the item doesn't fit in the box any other way |
||
183 | */ |
||
184 | 33 | if (count($stableOrientations) > 0) { |
|
185 | 28 | $orientationsToUse = $stableOrientations; |
|
186 | 32 | } else if (count($unstableOrientations) > 0) { |
|
187 | 6 | $orientationsInEmptyBox = $this->getPossibleOrientationsInEmptyBox($item, $box); |
|
188 | |||
189 | 6 | $stableOrientationsInEmptyBox = array_filter( |
|
190 | 6 | $orientationsInEmptyBox, |
|
191 | 6 | function(OrientatedItem $orientation) { |
|
192 | 6 | return $orientation->isStable(); |
|
193 | 6 | } |
|
194 | ); |
||
195 | |||
196 | if ($isLastItem || count($stableOrientationsInEmptyBox) == 0) { |
||
197 | $orientationsToUse = $unstableOrientations; |
||
198 | } |
||
199 | } |
||
200 | |||
201 | return $orientationsToUse; |
||
202 | } |
||
203 | } |
||
204 | |||
205 |
This check marks PHPDoc comments that could not be parsed by our parser. To see which comment annotations we can parse, please refer to our documentation on supported doc-types.