dvdoug /
BoxPacker
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 | namespace DVDoug\BoxPacker; |
||
| 8 | |||
| 9 | use Psr\Log\LoggerAwareInterface; |
||
| 10 | use Psr\Log\LoggerAwareTrait; |
||
| 11 | use Psr\Log\NullLogger; |
||
| 12 | |||
| 13 | /** |
||
| 14 | * Actual packer |
||
| 15 | * @author Doug Wright |
||
| 16 | * @package BoxPacker |
||
| 17 | */ |
||
| 18 | class VolumePacker implements LoggerAwareInterface |
||
| 19 | { |
||
| 20 | use LoggerAwareTrait; |
||
| 21 | |||
| 22 | /** |
||
| 23 | * Box to pack items into |
||
| 24 | * @var Box |
||
| 25 | */ |
||
| 26 | protected $box; |
||
| 27 | |||
| 28 | /** |
||
| 29 | * List of items to be packed |
||
| 30 | * @var ItemList |
||
| 31 | */ |
||
| 32 | protected $items; |
||
| 33 | |||
| 34 | /** |
||
| 35 | * Remaining width of the box to pack items into |
||
| 36 | * @var int |
||
| 37 | */ |
||
| 38 | protected $widthLeft; |
||
| 39 | |||
| 40 | /** |
||
| 41 | * Remaining length of the box to pack items into |
||
| 42 | * @var int |
||
| 43 | */ |
||
| 44 | protected $lengthLeft; |
||
| 45 | |||
| 46 | /** |
||
| 47 | * Remaining depth of the box to pack items into |
||
| 48 | * @var int |
||
| 49 | */ |
||
| 50 | protected $depthLeft; |
||
| 51 | |||
| 52 | /** |
||
| 53 | * Remaining weight capacity of the box |
||
| 54 | * @var int |
||
| 55 | */ |
||
| 56 | protected $remainingWeight; |
||
| 57 | |||
| 58 | /** |
||
| 59 | * Used width inside box for packing items |
||
| 60 | * @var int |
||
| 61 | */ |
||
| 62 | protected $usedWidth = 0; |
||
| 63 | |||
| 64 | /** |
||
| 65 | * Used length inside box for packing items |
||
| 66 | * @var int |
||
| 67 | */ |
||
| 68 | protected $usedLength = 0; |
||
| 69 | |||
| 70 | /** |
||
| 71 | * Used depth inside box for packing items |
||
| 72 | * @var int |
||
| 73 | */ |
||
| 74 | protected $usedDepth = 0; |
||
| 75 | |||
| 76 | /** |
||
| 77 | * Constructor |
||
| 78 | * |
||
| 79 | * @param Box $box |
||
| 80 | * @param ItemList $items |
||
| 81 | */ |
||
| 82 | 29 | public function __construct(Box $box, ItemList $items) |
|
| 83 | { |
||
| 84 | 29 | $this->logger = new NullLogger(); |
|
| 85 | |||
| 86 | 29 | $this->box = $box; |
|
| 87 | 29 | $this->items = $items; |
|
| 88 | |||
| 89 | 29 | $this->depthLeft = $this->box->getInnerDepth(); |
|
| 90 | 29 | $this->remainingWeight = $this->box->getMaxWeight() - $this->box->getEmptyWeight(); |
|
| 91 | 29 | $this->widthLeft = $this->box->getInnerWidth(); |
|
| 92 | 29 | $this->lengthLeft = $this->box->getInnerLength(); |
|
| 93 | } |
||
| 94 | |||
| 95 | /** |
||
| 96 | * Pack as many items as possible into specific given box |
||
| 97 | * |
||
| 98 | * @return PackedBox packed box |
||
| 99 | */ |
||
| 100 | 29 | public function pack() |
|
| 101 | { |
||
| 102 | 29 | $this->logger->debug("[EVALUATING BOX] {$this->box->getReference()}"); |
|
| 103 | |||
| 104 | 29 | $packedItems = new ItemList; |
|
| 105 | |||
| 106 | 29 | $layerWidth = $layerLength = $layerDepth = 0; |
|
| 107 | |||
| 108 | 29 | $prevItem = null; |
|
| 109 | |||
| 110 | 29 | while (!$this->items->isEmpty()) { |
|
| 111 | |||
| 112 | 29 | $itemToPack = $this->items->extract(); |
|
| 113 | |||
| 114 | //skip items that are simply too heavy |
||
| 115 | 29 | if ($itemToPack->getWeight() > $this->remainingWeight) { |
|
| 116 | 4 | continue; |
|
| 117 | } |
||
| 118 | |||
| 119 | 29 | $this->logger->debug("evaluating item {$itemToPack->getDescription()}", ['item' => $itemToPack, 'space' => ['widthLeft' => $this->widthLeft, 'lengthLeft' => $this->lengthLeft, 'depthLeft' => $this->depthLeft, 'layerWidth' => $layerWidth, 'layerLength' => $layerLength, 'layerDepth' => $layerDepth]]); |
|
| 120 | |||
| 121 | 29 | $nextItem = !$this->items->isEmpty() ? $this->items->top() : null; |
|
| 122 | 29 | $orientatedItem = $this->findBestOrientation($itemToPack, $prevItem, $nextItem, $this->widthLeft, $this->lengthLeft, $this->depthLeft); |
|
| 123 | |||
| 124 | 29 | if ($orientatedItem) { |
|
| 125 | |||
| 126 | 29 | $packedItems->insert($orientatedItem->getItem()); |
|
| 127 | 29 | $this->remainingWeight -= $itemToPack->getWeight(); |
|
| 128 | |||
| 129 | 29 | $this->lengthLeft -= $orientatedItem->getLength(); |
|
| 130 | 29 | $layerLength += $orientatedItem->getLength(); |
|
| 131 | 29 | $layerWidth = max($orientatedItem->getWidth(), $layerWidth); |
|
| 132 | |||
| 133 | 29 | $layerDepth = max($layerDepth, $orientatedItem->getDepth()); //greater than 0, items will always be less deep |
|
| 134 | |||
| 135 | 29 | $this->usedLength = max($this->usedLength, $layerLength); |
|
| 136 | 29 | $this->usedWidth = max($this->usedWidth, $layerWidth); |
|
| 137 | |||
| 138 | //allow items to be stacked in place within the same footprint up to current layerdepth |
||
| 139 | 29 | $this->tryAndStackItemsIntoSpace($packedItems, $prevItem, $nextItem, $orientatedItem, $layerDepth); |
|
| 140 | |||
| 141 | 29 | $prevItem = $orientatedItem; |
|
| 142 | |||
| 143 | 29 | if (!$nextItem) { |
|
| 144 | 29 | $this->usedDepth += $layerDepth; |
|
| 145 | } |
||
| 146 | } else { |
||
| 147 | |||
| 148 | 24 | $prevItem = null; |
|
| 149 | |||
| 150 | 24 | if ($this->widthLeft >= min($itemToPack->getWidth(), $itemToPack->getLength()) && $this->isLayerStarted($layerWidth, $layerLength, $layerDepth)) { |
|
| 151 | 23 | $this->logger->debug("No more fit in lengthwise, resetting for new row"); |
|
| 152 | 23 | $this->lengthLeft += $layerLength; |
|
| 153 | 23 | $this->widthLeft -= $layerWidth; |
|
| 154 | 23 | $layerWidth = $layerLength = 0; |
|
| 155 | 23 | $this->items->insert($itemToPack); |
|
| 156 | 23 | continue; |
|
| 157 | 18 | } elseif ($this->lengthLeft < min($itemToPack->getWidth(), $itemToPack->getLength()) || $layerDepth == 0) { |
|
| 158 | 7 | $this->logger->debug("doesn't fit on layer even when empty"); |
|
| 159 | 7 | continue; |
|
| 160 | } |
||
| 161 | |||
| 162 | 17 | $this->widthLeft = $layerWidth ? min(floor($layerWidth * 1.1), $this->box->getInnerWidth()) : $this->box->getInnerWidth(); |
|
| 163 | 17 | $this->lengthLeft = $layerLength ? min(floor($layerLength * 1.1), $this->box->getInnerLength()) : $this->box->getInnerLength(); |
|
| 164 | 17 | $this->depthLeft -= $layerDepth; |
|
| 165 | 17 | $this->usedDepth += $layerDepth; |
|
| 166 | |||
| 167 | 17 | $layerWidth = $layerLength = $layerDepth = 0; |
|
| 168 | 17 | $this->logger->debug("doesn't fit, so starting next vertical layer"); |
|
| 169 | 17 | $this->items->insert($itemToPack); |
|
| 170 | } |
||
| 171 | } |
||
| 172 | 29 | $this->logger->debug("done with this box"); |
|
| 173 | 29 | return new PackedBox($this->box, $packedItems, $this->widthLeft, $this->lengthLeft, $this->depthLeft, $this->remainingWeight, $this->usedWidth, $this->usedLength, $this->usedDepth); |
|
| 174 | } |
||
| 175 | |||
| 176 | /** |
||
| 177 | * Get the best orientation for an item |
||
| 178 | * @param Item $item |
||
| 179 | * @param OrientatedItem|null $prevItem |
||
| 180 | * @param Item|null $nextItem |
||
| 181 | * @param int $widthLeft |
||
| 182 | * @param int $lengthLeft |
||
| 183 | * @param int $depthLeft |
||
| 184 | * |
||
| 185 | * @return OrientatedItem|false |
||
| 186 | */ |
||
| 187 | 29 | protected function findBestOrientation( |
|
| 188 | Item $item, |
||
| 189 | OrientatedItem $prevItem = null, |
||
| 190 | Item $nextItem = null, |
||
| 191 | $widthLeft, |
||
| 192 | $lengthLeft, |
||
| 193 | $depthLeft) { |
||
| 194 | |||
| 195 | 29 | $possibleOrientations = $this->findAllPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft); |
|
| 196 | 29 | $orientationsToUse = $this->filterStableOrientations($possibleOrientations, $item, $prevItem, $nextItem); |
|
| 197 | |||
| 198 | 29 | $orientationFits = []; |
|
| 199 | /** @var OrientatedItem $orientation */ |
||
| 200 | 29 | foreach ($orientationsToUse as $o => $orientation) { |
|
| 201 | 29 | $orientationFit = min($widthLeft - $orientation->getWidth(), $lengthLeft - $orientation->getLength()); |
|
| 202 | 29 | $orientationFits[$o] = $orientationFit; |
|
| 203 | } |
||
| 204 | |||
| 205 | 29 | if (!empty($orientationFits)) { |
|
| 206 | 29 | asort($orientationFits); |
|
| 207 | 29 | reset($orientationFits); |
|
| 208 | 29 | $bestFit = $orientationsToUse[key($orientationFits)]; |
|
| 209 | 29 | $this->logger->debug("Selected best fit orientation", ['orientation' => $bestFit]); |
|
| 210 | 29 | return $bestFit; |
|
| 211 | } else { |
||
| 212 | 27 | return false; |
|
| 213 | } |
||
| 214 | } |
||
| 215 | |||
| 216 | /** |
||
| 217 | * Find all possible orientations for an item |
||
| 218 | * @param Item $item |
||
| 219 | * @param OrientatedItem|null $prevItem |
||
| 220 | * @param int $widthLeft |
||
| 221 | * @param int $lengthLeft |
||
| 222 | * @param int $depthLeft |
||
| 223 | * |
||
| 224 | * @return OrientatedItem[] |
||
| 225 | */ |
||
| 226 | 29 | protected function findAllPossibleOrientations( |
|
| 227 | Item $item, |
||
| 228 | OrientatedItem $prevItem = null, |
||
| 229 | $widthLeft, |
||
| 230 | $lengthLeft, |
||
| 231 | $depthLeft) { |
||
| 232 | |||
| 233 | 29 | $orientations = []; |
|
| 234 | |||
| 235 | //Special case items that are the same as what we just packed - keep orientation |
||
| 236 | 29 | if ($prevItem && $prevItem->getItem() == $item) { |
|
| 237 | 12 | $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth()); |
|
| 238 | } else { |
||
| 239 | |||
| 240 | //simple 2D rotation |
||
| 241 | 29 | $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth()); |
|
| 242 | 29 | $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth()); |
|
| 243 | |||
| 244 | //add 3D rotation if we're allowed |
||
| 245 | 29 | if (!$item->getKeepFlat()) { |
|
| 246 | 10 | $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength()); |
|
| 247 | 10 | $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth()); |
|
| 248 | 10 | $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength()); |
|
| 249 | 10 | $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth()); |
|
| 250 | } |
||
| 251 | } |
||
| 252 | |||
| 253 | //remove any that simply don't fit |
||
| 254 | return array_filter($orientations, function(OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) { |
||
| 255 | 29 | return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft; |
|
| 256 | 29 | }); |
|
| 257 | |||
| 258 | } |
||
| 259 | |||
| 260 | /** |
||
| 261 | * Filter a set of orientations allow only those that have a stable base OR |
||
| 262 | * the item doesn't fit in the box any other way |
||
| 263 | * the item is the last one left to pack |
||
| 264 | * |
||
| 265 | * @param OrientatedItem[] $orientations |
||
| 266 | * @param Item $item |
||
| 267 | * @param OrientatedItem|null $prevItem |
||
| 268 | * @param Item|null $nextItem |
||
| 269 | * |
||
| 270 | * @return OrientatedItem[] |
||
| 271 | */ |
||
| 272 | 29 | protected function filterStableOrientations( |
|
| 273 | array $orientations, |
||
| 274 | Item $item, |
||
| 275 | OrientatedItem $prevItem = null, |
||
|
0 ignored issues
–
show
|
|||
| 276 | Item $nextItem = null |
||
| 277 | ) { |
||
| 278 | 29 | $stableOrientations = $unstableOrientations = $orientationsToUse = []; |
|
| 279 | |||
| 280 | 29 | foreach ($orientations as $o => $orientation) { |
|
| 281 | 29 | if ($orientation->isStable()) { |
|
| 282 | 26 | $stableOrientations[] = $orientation; |
|
| 283 | } else { |
||
| 284 | 29 | $unstableOrientations[] = $orientation; |
|
| 285 | } |
||
| 286 | } |
||
| 287 | |||
| 288 | 29 | if (count($stableOrientations) > 0) { |
|
| 289 | 26 | $orientationsToUse = $stableOrientations; |
|
| 290 | 28 | } else if (count($unstableOrientations) > 0) { |
|
| 291 | 4 | $orientationsInEmptyBox = $this->findAllPossibleOrientations($item, null, $this->box->getInnerWidth(), $this->box->getInnerLength(), $this->box->getInnerDepth()); |
|
| 292 | |||
| 293 | 4 | $stableOrientationsInEmptyBox = array_filter( |
|
| 294 | $orientationsInEmptyBox, |
||
| 295 | 4 | function(OrientatedItem $orientation) { |
|
| 296 | 4 | return $orientation->isStable(); |
|
| 297 | 4 | } |
|
| 298 | ); |
||
| 299 | |||
| 300 | 4 | if (is_null($nextItem) || count($stableOrientationsInEmptyBox) == 0) { |
|
| 301 | 4 | $orientationsToUse = $unstableOrientations; |
|
| 302 | } |
||
| 303 | } |
||
| 304 | |||
| 305 | 29 | return $orientationsToUse; |
|
| 306 | } |
||
| 307 | |||
| 308 | /** |
||
| 309 | * Figure out if we can stack the next item vertically on top of this rather than side by side |
||
| 310 | * Used when we've packed a tall item, and have just put a shorter one next to it |
||
| 311 | * |
||
| 312 | * @param ItemList $packedItems |
||
| 313 | * @param OrientatedItem $prevItem |
||
| 314 | * @param Item $nextItem |
||
| 315 | * @param OrientatedItem $orientatedItem |
||
| 316 | * @param int $layerDepth |
||
| 317 | * |
||
| 318 | */ |
||
| 319 | 29 | protected function tryAndStackItemsIntoSpace( |
|
| 320 | ItemList $packedItems, |
||
| 321 | OrientatedItem $prevItem = null, |
||
| 322 | Item $nextItem = null, |
||
| 323 | OrientatedItem $orientatedItem, |
||
| 324 | $layerDepth) |
||
| 325 | { |
||
| 326 | 29 | $stackableDepth = $layerDepth - $orientatedItem->getDepth(); //we already packed this |
|
| 327 | |||
| 328 | 29 | while (!$this->items->isEmpty() && $this->remainingWeight >= $this->items->top()->getWeight()) { |
|
| 329 | 27 | $stackedItem = $this->findBestOrientation($this->items->top(), $prevItem, $nextItem, $orientatedItem->getWidth(), $orientatedItem->getLength(), $stackableDepth); |
|
| 330 | |||
| 331 | 27 | if ($stackedItem) { |
|
| 332 | 1 | $this->remainingWeight -= $this->items->top()->getWeight(); |
|
| 333 | 1 | $stackableDepth -= $stackedItem->getDepth(); |
|
| 334 | 1 | $packedItems->insert($this->items->extract()); |
|
| 335 | } else { |
||
| 336 | 27 | break; |
|
| 337 | } |
||
| 338 | } |
||
| 339 | } |
||
| 340 | |||
| 341 | /** |
||
| 342 | * @param int $layerWidth |
||
| 343 | * @param int $layerLength |
||
| 344 | * @param int $layerDepth |
||
| 345 | * |
||
| 346 | * @return bool |
||
| 347 | */ |
||
| 348 | 24 | protected function isLayerStarted($layerWidth, $layerLength, $layerDepth) { |
|
| 349 | 24 | return $layerWidth > 0 && $layerLength > 0 && $layerDepth > 0; |
|
| 350 | } |
||
| 351 | } |
||
| 352 |
This check looks from parameters that have been defined for a function or method, but which are not used in the method body.