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

src/OrientatedItemFactory.php (1 issue)

Upgrade to new PHP Analysis Engine

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
12
/**
13
 * Figure out orientations for an item and a given set of dimensions
14
 * @author Doug Wright
15
 * @package BoxPacker
16
 */
17
class OrientatedItemFactory implements LoggerAwareInterface
18
{
19
    use LoggerAwareTrait;
20
21
    /**
22
     * @var OrientatedItem[]
23
     */
24
    protected static $emptyBoxCache = [];
25
26
    /**
27
     * Get the best orientation for an item
28
     * @param Box $box
29
     * @param Item $item
30
     * @param PackedItem|null $prevItem
31
     * @param bool $isLastItem
32
     * @param int $widthLeft
33
     * @param int $lengthLeft
34
     * @param int $depthLeft
35
     * @return OrientatedItem|false
36
     */
37 36
    public function getBestOrientation(Box $box, Item $item, PackedItem $prevItem = null, $isLastItem, $widthLeft, $lengthLeft, $depthLeft) {
38
39 36
        $possibleOrientations = $this->getPossibleOrientations($item, $prevItem, $widthLeft, $lengthLeft, $depthLeft);
40 36
        $usableOrientations = $this->getUsableOrientations($possibleOrientations, $box, $item, $isLastItem);
41
42 36
        $orientationFits = [];
43
        /** @var OrientatedItem $orientation */
44 36
        foreach ($usableOrientations as $o => $orientation) {
45 36
            $orientationFit = min($widthLeft - $orientation->getWidth(), $lengthLeft - $orientation->getLength());
46 36
            $orientationFits[$o] = $orientationFit;
47
        }
48
49 36
        if (!empty($orientationFits)) {
50 36
            asort($orientationFits);
51 36
            reset($orientationFits);
52 36
            $bestFit = $usableOrientations[key($orientationFits)];
53 36
            $this->logger->debug("Selected best fit orientation", ['orientation' => $bestFit]);
54 36
            return $bestFit;
55
        } else {
56
            return false;
57
        }
58
    }
59
60
    /**
61
     * Find all possible orientations for an item
62
     * @param Item $item
63
     * @param PackedItem|null $prevItem
64
     * @param int $widthLeft
65
     * @param int $lengthLeft
66
     * @param int $depthLeft
67
     * @return OrientatedItem[]
68
     */
69 36
    public function getPossibleOrientations(Item $item, PackedItem $prevItem = null, $widthLeft, $lengthLeft, $depthLeft) {
70
71 36
        $orientations = [];
72
73
        //Special case items that are the same as what we just packed - keep orientation
74
        /** @noinspection PhpNonStrictObjectEqualityInspection */
75 36
        if ($prevItem && $prevItem->getItem() == $item) {
76 13
            $orientations[] = new OrientatedItem($item, $prevItem->getWidth(), $prevItem->getLength(), $prevItem->getDepth());
77
        } else {
78
79
            //simple 2D rotation
80 36
            $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getLength(), $item->getDepth());
81 36
            $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getWidth(), $item->getDepth());
82
83
            //add 3D rotation if we're allowed
84 36
            if (!$item->getKeepFlat()) {
85 13
                $orientations[] = new OrientatedItem($item, $item->getWidth(), $item->getDepth(), $item->getLength());
86 13
                $orientations[] = new OrientatedItem($item, $item->getLength(), $item->getDepth(), $item->getWidth());
87 13
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getWidth(), $item->getLength());
88 13
                $orientations[] = new OrientatedItem($item, $item->getDepth(), $item->getLength(), $item->getWidth());
89
            }
90
        }
91
92
        //remove any that simply don't fit
93 36
        return array_filter($orientations, function(OrientatedItem $i) use ($widthLeft, $lengthLeft, $depthLeft) {
94 36
            return $i->getWidth() <= $widthLeft && $i->getLength() <= $lengthLeft && $i->getDepth() <= $depthLeft;
95 36
        });
96
    }
97
98
    /**
99
     * @param Item $item
100
     * @param Box  $box
101
     * @return OrientatedItem[]
0 ignored issues
show
Should the return type not be OrientatedItem|OrientatedItem[]?

This check compares the return type specified in the @return annotation of a function or method doc comment with the types returned by the function and raises an issue if they mismatch.

Loading history...
102
     */
103 36
    public function getPossibleOrientationsInEmptyBox(Item $item, Box $box)
104
    {
105 36
        $cacheKey = $item->getWidth() .
106 36
            '|' .
107 36
            $item->getLength() .
108 36
            '|' .
109 36
            $item->getDepth() .
110 36
            '|' .
111 36
            ($item->getKeepFlat() ? '2D' : '3D') .
112 36
            '|' .
113 36
            $box->getInnerWidth() .
114 36
            '|' .
115 36
            $box->getInnerLength() .
116 36
            '|' .
117 36
            $box->getInnerDepth();
118
119 36
        if (isset(static::$emptyBoxCache[$cacheKey])) {
120 31
            $orientations = static::$emptyBoxCache[$cacheKey];
121
        } else {
122 33
            $orientations = $this->getPossibleOrientations(
123 33
                $item,
124 33
                null,
125 33
                $box->getInnerWidth(),
126 33
                $box->getInnerLength(),
127 33
                $box->getInnerDepth()
128
            );
129 33
            static::$emptyBoxCache[$cacheKey] = $orientations;
130
        }
131 36
        return $orientations;
132
    }
133
134
    /**
135
     * @param OrientatedItem[] $possibleOrientations
136
     * @param Box              $box
137
     * @param Item             $item
138
     * @param bool             $isLastItem
139
     *
140
     * @return OrientatedItem[]
141
     */
142 36
    protected function getUsableOrientations(
143
        $possibleOrientations,
144
        Box $box,
145
        Item $item,
146
        $isLastItem
147
    ) {
148
        /*
149
         * Divide possible orientations into stable (low centre of gravity) and unstable (high centre of gravity)
150
         */
151 36
        $stableOrientations = [];
152 36
        $unstableOrientations = [];
153
154 36
        foreach ($possibleOrientations as $o => $orientation) {
155 36
            if ($orientation->isStable()) {
156 31
                $stableOrientations[] = $orientation;
157
            } else {
158 8
                $unstableOrientations[] = $orientation;
159
            }
160
        }
161
162 36
        $orientationsToUse = [];
163
164
        /*
165
         * We prefer to use stable orientations only, but allow unstable ones if either
166
         * the item is the last one left to pack OR
167
         * the item doesn't fit in the box any other way
168
         */
169 36
        if (count($stableOrientations) > 0) {
170 31
            $orientationsToUse = $stableOrientations;
171 35
        } else if (count($unstableOrientations) > 0) {
172 6
            $orientationsInEmptyBox = $this->getPossibleOrientationsInEmptyBox($item, $box);
173
174 6
            $stableOrientationsInEmptyBox = array_filter(
175 6
                $orientationsInEmptyBox,
176 6
                function(OrientatedItem $orientation) {
177 6
                    return $orientation->isStable();
178 6
                }
179
            );
180
181
            if ($isLastItem || count($stableOrientationsInEmptyBox) == 0) {
182
                $orientationsToUse = $unstableOrientations;
183
            }
184
        }
185
186
        return $orientationsToUse;
187
    }
188
}
189
190