Issues (2)

src/OrientatedItemFactory.php (1 issue)

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
 * @internal
25
 */
26
class OrientatedItemFactory implements LoggerAwareInterface
27
{
28
    use LoggerAwareTrait;
29
30
    /** @var Box */
31
    protected $box;
32
33
    /**
34
     * @var OrientatedItem[]
35
     */
36
    protected static $emptyBoxCache = [];
37
38 22
    public function __construct(Box $box)
39
    {
40 22
        $this->box = $box;
41 22
    }
42
43
    /**
44
     * Get the best orientation for an item.
45
     *
46
     * @param Item                $item
47
     * @param OrientatedItem|null $prevItem
48
     * @param ItemList            $nextItems
49
     * @param bool                $isLastItem
50
     * @param int                 $widthLeft
51
     * @param int                 $lengthLeft
52
     * @param int                 $depthLeft
53
     * @param int                 $rowLength
54
     *
55
     * @return OrientatedItem|null
56
     */
57 21
    public function getBestOrientation(
58
        Item $item,
59
        ?OrientatedItem $prevItem,
60
        ItemList $nextItems,
61
        bool $isLastItem,
62
        int $widthLeft,
63
        int $lengthLeft,
64
        int $depthLeft,
65
        int $rowLength
66
    ): ?OrientatedItem {
67 21
        $possibleOrientations = $this->getPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft);
68 21
        $usableOrientations = $this->getUsableOrientations($item, $possibleOrientations, $isLastItem);
69
70 21
        if (empty($usableOrientations)) {
71 20
            return null;
72
        }
73
74
        usort($usableOrientations, function (OrientatedItem $a, OrientatedItem $b) use ($widthLeft, $lengthLeft, $depthLeft, $nextItems, $rowLength) {
75 9
            $orientationAWidthLeft = $widthLeft - $a->getWidth();
76 9
            $orientationALengthLeft = $lengthLeft - $a->getLength();
77 9
            $orientationADepthLeft = $depthLeft - $a->getDepth();
78 9
            $orientationBWidthLeft = $widthLeft - $b->getWidth();
79 9
            $orientationBLengthLeft = $lengthLeft - $b->getLength();
80 9
            $orientationBDepthLeft = $depthLeft - $b->getDepth();
81
82 9
            $orientationAMinGap = min($orientationAWidthLeft, $orientationALengthLeft);
83 9
            $orientationBMinGap = min($orientationBWidthLeft, $orientationBLengthLeft);
84
85 9
            if ($orientationAMinGap === 0) { // prefer A if it leaves no gap
86 4
                return -1;
87
            }
88 6
            if ($orientationBMinGap === 0) { // prefer B if it leaves no gap
89 2
                return 1;
90
            }
91
92
            // prefer leaving room for next item in current row
93 5
            if ($nextItems->count()) {
94 4
                $nextItemFitA = count($this->getPossibleOrientations($nextItems->top(), $a, $orientationAWidthLeft, $lengthLeft, $depthLeft));
95 4
                $nextItemFitB = count($this->getPossibleOrientations($nextItems->top(), $b, $orientationBWidthLeft, $lengthLeft, $depthLeft));
96 4
                if ($nextItemFitA && !$nextItemFitB) {
97
                    return -1;
98
                }
99 4
                if ($nextItemFitB && !$nextItemFitA) {
100 2
                    return 1;
101
                }
102
103
                // if not an easy either/or, do a partial lookahead
104 2
                $additionalPackedA = $this->calculateAdditionalItemsPackedWithThisOrientation($a, $nextItems, $widthLeft, $lengthLeft, $depthLeft, $rowLength);
105 2
                $additionalPackedB = $this->calculateAdditionalItemsPackedWithThisOrientation($b, $nextItems, $widthLeft, $lengthLeft, $depthLeft, $rowLength);
106 2
                if ($additionalPackedA !== $additionalPackedB) {
107 1
                    return $additionalPackedB <=> $additionalPackedA;
108
                }
109
            }
110
            // otherwise prefer leaving minimum possible gap, or the greatest footprint
111 2
            return $orientationADepthLeft <=> $orientationBDepthLeft ?: $orientationAMinGap <=> $orientationBMinGap ?: $a->getSurfaceFootprint() <=> $b->getSurfaceFootprint();
112 21
        });
113
114 21
        $bestFit = reset($usableOrientations);
115 21
        $this->logger->debug('Selected best fit orientation', ['orientation' => $bestFit]);
116
117 21
        return $bestFit;
118
    }
119
120
    /**
121
     * Find all possible orientations for an item.
122
     *
123
     * @param Item                $item
124
     * @param OrientatedItem|null $prevItem
125
     * @param int                 $widthLeft
126
     * @param int                 $lengthLeft
127
     * @param int                 $depthLeft
128
     *
129
     * @return OrientatedItem[]
130
     */
131 21
    public function getPossibleOrientations(
132
        Item $item,
133
        ?OrientatedItem $prevItem,
134
        int $widthLeft,
135
        int $lengthLeft,
136
        int $depthLeft
137
    ): array {
138 21
        $orientations = [];
139
140
        //Special case items that are the same as what we just packed - keep orientation
141 21
        if ($prevItem && $this->isSameDimensions($prevItem->getItem(), $item)) {
142 16
            $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth());
143
        } else {
144
            //simple 2D rotation
145 21
            $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth());
146 21
            $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth());
147
148
            //add 3D rotation if we're allowed
149 21
            if (!$item->getKeepFlat()) {
150 13
                $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength());
151 13
                $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth());
152 13
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength());
153 13
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth());
154
            }
155
        }
156
157 21
        $orientations = array_unique($orientations);
158
159
        //remove any that simply don't fit
160
        return array_filter($orientations, function (OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) {
161 21
            return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft;
162 21
        });
163
    }
164
165
    /**
166
     * @param  Item             $item
167
     * @return OrientatedItem[]
168
     */
169 22
    public function getPossibleOrientationsInEmptyBox(Item $item): array
170
    {
171 22
        $cacheKey = $item->getWidth() .
172 22
            '|' .
173 22
            $item->getLength() .
174 22
            '|' .
175 22
            $item->getDepth() .
176 22
            '|' .
177 22
            ($item->getKeepFlat() ? '2D' : '3D') .
178 22
            '|' .
179 22
            $this->box->getInnerWidth() .
180 22
            '|' .
181 22
            $this->box->getInnerLength() .
182 22
            '|' .
183 22
            $this->box->getInnerDepth();
184
185 22
        if (isset(static::$emptyBoxCache[$cacheKey])) {
186 22
            $orientations = static::$emptyBoxCache[$cacheKey];
187
        } else {
188 20
            $orientations = $this->getPossibleOrientations(
189 20
                $item,
190 20
                null,
191 20
                $this->box->getInnerWidth(),
192 20
                $this->box->getInnerLength(),
193 20
                $this->box->getInnerDepth()
194
            );
195 20
            static::$emptyBoxCache[$cacheKey] = $orientations;
196
        }
197
198 22
        return $orientations;
0 ignored issues
show
Bug Best Practice introduced by Doug Wright
The expression return $orientations could return the type DVDoug\BoxPacker\OrientatedItem which is incompatible with the type-hinted return array. Consider adding an additional type-check to rule them out.
Loading history...
199
    }
200
201
    /**
202
     * @param Item             $item
203
     * @param OrientatedItem[] $possibleOrientations
204
     * @param bool             $isLastItem
205
     *
206
     * @return OrientatedItem[]
207
     */
208 21
    protected function getUsableOrientations(
209
        Item $item,
210
        $possibleOrientations,
211
        bool $isLastItem
212
    ): array {
213 21
        $orientationsToUse = $stableOrientations = $unstableOrientations = [];
214
215
        // Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity)
216 21
        foreach ($possibleOrientations as $orientation) {
217 21
            if ($orientation->isStable()) {
218 21
                $stableOrientations[] = $orientation;
219
            } else {
220 21
                $unstableOrientations[] = $orientation;
221
            }
222
        }
223
224
        /*
225
         * We prefer to use stable orientations only, but allow unstable ones if either
226
         * the item is the last one left to pack OR
227
         * the item doesn't fit in the box any other way
228
         */
229 21
        if (count($stableOrientations) > 0) {
230 21
            $orientationsToUse = $stableOrientations;
231 20
        } elseif (count($unstableOrientations) > 0) {
232
            $stableOrientationsInEmptyBox = $this->getStableOrientationsInEmptyBox($item);
233
234
            if ($isLastItem || count($stableOrientationsInEmptyBox) === 0) {
235
                $orientationsToUse = $unstableOrientations;
236
            }
237
        }
238
239 21
        return $orientationsToUse;
240
    }
241
242
    /**
243
     * Return the orientations for this item if it were to be placed into the box with nothing else.
244
     *
245
     * @param  Item  $item
246
     * @return array
247
     */
248
    protected function getStableOrientationsInEmptyBox(Item $item): array
249
    {
250
        $orientationsInEmptyBox = $this->getPossibleOrientationsInEmptyBox($item);
251
252
        return array_filter(
253
            $orientationsInEmptyBox,
254
            function (OrientatedItem $orientation) {
255
                return $orientation->isStable();
256
            }
257
        );
258
    }
259
260
    /**
261
     * Compare two items to see if they have same dimensions.
262
     *
263
     * @param Item $itemA
264
     * @param Item $itemB
265
     *
266
     * @return bool
267
     */
268 19
    protected function isSameDimensions(Item $itemA, Item $itemB): bool
269
    {
270 19
        $itemADimensions = [$itemA->getWidth(), $itemA->getLength(), $itemA->getDepth()];
271 19
        $itemBDimensions = [$itemB->getWidth(), $itemB->getLength(), $itemB->getDepth()];
272 19
        sort($itemADimensions);
273 19
        sort($itemBDimensions);
274
275 19
        return $itemADimensions === $itemBDimensions;
276
    }
277
278
    /**
279
     * Approximation of a forward-looking packing.
280
     *
281
     * Not an actual packing, that has additional logic regarding constraints and stackability, this focuses
282
     * purely on fit.
283
     *
284
     * @param  OrientatedItem $prevItem
285
     * @param  ItemList       $nextItems
286
     * @param  int            $originalWidthLeft
287
     * @param  int            $originalLengthLeft
288
     * @param  int            $depthLeft
289
     * @param  int            $currentRowLengthBeforePacking
290
     * @return int
291
     */
292 2
    protected function calculateAdditionalItemsPackedWithThisOrientation(
293
        OrientatedItem $prevItem,
294
        ItemList $nextItems,
295
        int $originalWidthLeft,
296
        int $originalLengthLeft,
297
        int $depthLeft,
298
        int $currentRowLengthBeforePacking
299
    ): int {
300 2
        $packedCount = 0;
301
302 2
        $currentRowLength = max($prevItem->getLength(), $currentRowLengthBeforePacking);
303
304 2
        $itemsToPack = $nextItems->topN(8); // cap lookahead as this gets recursive and slow
305
306 2
        $tempBox = new WorkingVolume($originalWidthLeft - $prevItem->getWidth(), $currentRowLength, $depthLeft, PHP_INT_MAX);
307 2
        $tempPacker = new VolumePacker($tempBox, clone $itemsToPack);
308 2
        $remainingRowPacked = $tempPacker->pack();
309
        /** @var PackedItem $packedItem */
310 2
        foreach ($remainingRowPacked->getItems() as $packedItem) {
311 2
            $itemsToPack->remove($packedItem->getItem());
312
        }
313
314 2
        $tempBox = new WorkingVolume($originalWidthLeft, $originalLengthLeft - $currentRowLength, $depthLeft, PHP_INT_MAX);
315 2
        $tempPacker = new VolumePacker($tempBox, clone $itemsToPack);
316 2
        $nextRowsPacked = $tempPacker->pack();
317
        /** @var PackedItem $packedItem */
318 2
        foreach ($nextRowsPacked->getItems() as $packedItem) {
319 1
            $itemsToPack->remove($packedItem->getItem());
320
        }
321
322 2
        $this->logger->debug('Lookahead with orientation', ['packedCount' => $packedCount, 'orientatedItem' => $prevItem]);
323
324 2
        return $nextItems->count() - $itemsToPack->count();
325
    }
326
}
327