Completed
Push — master ( 4734ca...53d220 )
by Doug
14:09
created

OrientatedItemFactory::getBestOrientation()   B

Complexity

Conditions 3
Paths 4

Size

Total Lines 30
Code Lines 23

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 13
CRAP Score 3

Importance

Changes 0
Metric Value
dl 0
loc 30
ccs 13
cts 13
cp 1
rs 8.8571
c 0
b 0
f 0
cc 3
eloc 23
nc 4
nop 7
crap 3
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
Documentation introduced by Doug Wright
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...
32
     * @param bool $isLastItem
33
     * @param int $widthLeft
34
     * @param int $lengthLeft
35
     * @param int $depthLeft
36
     * @return ?OrientatedItem
0 ignored issues
show
Documentation introduced by Doug Wright
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
Documentation introduced by Doug Wright
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