Issues (30)

Branch: master

src/OrientatedItemFactory.php (1 issue)

Labels
Severity
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\LoggerInterface;
13
use Psr\Log\NullLogger;
14
15
use function array_filter;
16
use function count;
17
use function usort;
18
19
/**
20
 * Figure out orientations for an item and a given set of dimensions.
21
 * @internal
22
 */
23
class OrientatedItemFactory implements LoggerAwareInterface
24
{
25
    protected LoggerInterface $logger;
26
27
    protected bool $singlePassMode = false;
28
29
    protected bool $boxIsRotated = false;
30
31
    /**
32
     * @var array<string, bool>
33
     */
34
    protected static array $emptyBoxStableItemOrientationCache = [];
35
36 102
    public function __construct(protected Box $box)
37
    {
38 102
        $this->logger = new NullLogger();
39
    }
40
41 99
    public function setLogger(LoggerInterface $logger): void
42
    {
43 99
        $this->logger = $logger;
44
    }
45
46 19
    public function setSinglePassMode(bool $singlePassMode): void
47
    {
48 19
        $this->singlePassMode = $singlePassMode;
49
    }
50
51 99
    public function setBoxIsRotated(bool $boxIsRotated): void
52
    {
53 99
        $this->boxIsRotated = $boxIsRotated;
54
    }
55
56
    /**
57
     * Get the best orientation for an item.
58
     */
59 92
    public function getBestOrientation(
60
        Item $item,
61
        ?OrientatedItem $prevItem,
62
        ItemList $nextItems,
63
        int $widthLeft,
64
        int $lengthLeft,
65
        int $depthLeft,
66
        int $rowLength,
67
        int $x,
68
        int $y,
69
        int $z,
70
        PackedItemList $prevPackedItemList,
71
        bool $considerStability
72
    ): ?OrientatedItem {
73 92
        $this->logger->debug(
74 92
            "evaluating item {$item->getDescription()} for fit",
75 92
            [
76 92
                'item' => $item,
77 92
                'space' => [
78 92
                    'widthLeft' => $widthLeft,
79 92
                    'lengthLeft' => $lengthLeft,
80 92
                    'depthLeft' => $depthLeft,
81 92
                ],
82 92
                'position' => [
83 92
                    'x' => $x,
84 92
                    'y' => $y,
85 92
                    'z' => $z,
86 92
                ],
87 92
            ]
88 92
        );
89
90 92
        $possibleOrientations = $this->getPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft, $x, $y, $z, $prevPackedItemList);
91 92
        $usableOrientations = $considerStability ? $this->getUsableOrientations($item, $possibleOrientations) : $possibleOrientations;
92
93 92
        if (empty($usableOrientations)) {
94 92
            return null;
95
        }
96
97 84
        $sorter = new OrientatedItemSorter($this, $this->singlePassMode, $widthLeft, $lengthLeft, $depthLeft, $nextItems, $rowLength, $x, $y, $z, $prevPackedItemList, $this->logger);
98 84
        usort($usableOrientations, $sorter);
99
100 84
        $this->logger->debug('Selected best fit orientation', ['orientation' => $usableOrientations[0]]);
101
102 84
        return $usableOrientations[0];
103
    }
104
105
    /**
106
     * Find all possible orientations for an item.
107
     *
108
     * @return OrientatedItem[]
109
     */
110 102
    public function getPossibleOrientations(
111
        Item $item,
112
        ?OrientatedItem $prevItem,
113
        int $widthLeft,
114
        int $lengthLeft,
115
        int $depthLeft,
116
        int $x,
117
        int $y,
118
        int $z,
119
        PackedItemList $prevPackedItemList
120
    ): array {
121 102
        $permutations = $this->generatePermutations($item, $prevItem);
122
123
        // remove any that simply don't fit
124 102
        $orientations = [];
125 102
        foreach ($permutations as $dimensions) {
126 102
            if ($dimensions[0] <= $widthLeft && $dimensions[1] <= $lengthLeft && $dimensions[2] <= $depthLeft) {
127 99
                $orientations[] = new OrientatedItem($item, $dimensions[0], $dimensions[1], $dimensions[2]);
128
            }
129
        }
130
131 102
        if ($item instanceof ConstrainedPlacementItem && !$this->box instanceof WorkingVolume) {
132 3
            $orientations = array_filter($orientations, function (OrientatedItem $i) use ($x, $y, $z, $prevPackedItemList): bool {
133
                /** @var ConstrainedPlacementItem $constrainedItem */
134 3
                $constrainedItem = $i->item;
135
136 3
                if ($this->boxIsRotated) {
137 2
                    $rotatedPrevPackedItemList = new PackedItemList();
138 2
                    foreach ($prevPackedItemList as $prevPackedItem) {
139 2
                        $rotatedPrevPackedItemList->insert(new PackedItem($prevPackedItem->item, $prevPackedItem->y, $prevPackedItem->x, $prevPackedItem->z, $prevPackedItem->length, $prevPackedItem->width, $prevPackedItem->depth));
140
                    }
141
142 2
                    return $constrainedItem->canBePacked(new PackedBox($this->box, $rotatedPrevPackedItemList), $y, $x, $z, $i->length, $i->width, $i->depth);
143
                } else {
144 3
                    return $constrainedItem->canBePacked(new PackedBox($this->box, $prevPackedItemList), $x, $y, $z, $i->width, $i->length, $i->depth);
145
                }
146 3
            });
147
        }
148
149 102
        return $orientations;
150
    }
151
152
    /**
153
     * @param  OrientatedItem[] $possibleOrientations
154
     * @return OrientatedItem[]
155
     */
156 92
    protected function getUsableOrientations(
157
        Item $item,
158
        array $possibleOrientations
159
    ): array {
160 92
        $stableOrientations = $unstableOrientations = [];
161
162
        // Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity)
163 92
        foreach ($possibleOrientations as $orientation) {
164 84
            if ($orientation->isStable() || $this->box->getInnerDepth() === $orientation->depth) {
165 82
                $stableOrientations[] = $orientation;
166
            } else {
167 12
                $unstableOrientations[] = $orientation;
168
            }
169
        }
170
171
        /*
172
         * We prefer to use stable orientations only, but allow unstable ones if
173
         * the item doesn't fit in the box any other way
174
         */
175 92
        if (count($stableOrientations) > 0) {
176 82
            return $stableOrientations;
177
        }
178
179 92
        if ((count($unstableOrientations) > 0) && !$this->hasStableOrientationsInEmptyBox($item)) {
180 5
            return $unstableOrientations;
181
        }
182
183 92
        return [];
184
    }
185
186
    /**
187
     * Return the orientations for this item if it were to be placed into the box with nothing else.
188
     */
189 10
    protected function hasStableOrientationsInEmptyBox(Item $item): bool
190
    {
191 10
        $cacheKey = $item->getWidth() .
192 10
            '|' .
193 10
            $item->getLength() .
194 10
            '|' .
195 10
            $item->getDepth() .
196 10
            '|' .
197 10
            $item->getAllowedRotation()->name .
0 ignored issues
show
The property name does not seem to exist on DVDoug\BoxPacker\Rotation.
Loading history...
198 10
            '|' .
199 10
            $this->box->getInnerWidth() .
200 10
            '|' .
201 10
            $this->box->getInnerLength() .
202 10
            '|' .
203 10
            $this->box->getInnerDepth();
204
205 10
        if (isset(static::$emptyBoxStableItemOrientationCache[$cacheKey])) {
206 9
            return static::$emptyBoxStableItemOrientationCache[$cacheKey];
207
        }
208
209 10
        $orientations = $this->getPossibleOrientations(
210 10
            $item,
211 10
            null,
212 10
            $this->box->getInnerWidth(),
213 10
            $this->box->getInnerLength(),
214 10
            $this->box->getInnerDepth(),
215 10
            0,
216 10
            0,
217 10
            0,
218 10
            new PackedItemList()
219 10
        );
220
221 10
        $stableOrientations = array_filter(
222 10
            $orientations,
223 10
            static fn (OrientatedItem $orientation) => $orientation->isStable()
224 10
        );
225 10
        static::$emptyBoxStableItemOrientationCache[$cacheKey] = count($stableOrientations) > 0;
226
227 10
        return static::$emptyBoxStableItemOrientationCache[$cacheKey];
228
    }
229
230
    /**
231
     * @return array<array<int>>
232
     */
233 102
    private function generatePermutations(Item $item, ?OrientatedItem $prevItem): array
234
    {
235
        // Special case items that are the same as what we just packed - keep orientation
236 102
        if ($prevItem && $prevItem->isSameDimensions($item)) {
237 73
            return [[$prevItem->width, $prevItem->length, $prevItem->depth]];
238
        }
239
240 102
        $permutations = [];
241 102
        $w = $item->getWidth();
242 102
        $l = $item->getLength();
243 102
        $d = $item->getDepth();
244
245 102
        $permutations[$w . '|' . $l . '|' . $d] = [$w, $l, $d];
246
247 102
        if ($item->getAllowedRotation() !== Rotation::Never) { // simple 2D rotation
248 101
            $permutations[$l . '|' . $w . '|' . $d] = [$l, $w, $d];
249
        }
250
251 102
        if ($item->getAllowedRotation() === Rotation::BestFit) { // add 3D rotation if we're allowed
252 70
            $permutations[$w . '|' . $d . '|' . $l] = [$w, $d, $l];
253 70
            $permutations[$l . '|' . $d . '|' . $w] = [$l, $d, $w];
254 70
            $permutations[$d . '|' . $w . '|' . $l] = [$d, $w, $l];
255 70
            $permutations[$d . '|' . $l . '|' . $w] = [$d, $l, $w];
256
        }
257
258 102
        return $permutations;
259
    }
260
}
261