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 . |
|
|
|
|
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
|
|
|
|