Algorithm seems inefficient for tight packing

[MarcoWel]

Hi, First of all a big thank you to @dvdoug for this excellent and easy-to-use library. We use it to automatically find the right box for a given set of products.

However, there are regular cases where Packer() just does not seem to work well. One particular case is the following:

$packer = new Packer();
$packer->addBox(new TestBox('Small', 160, 130,  70, 0, 0, 0, 0, 100000));
$packer->addBox(new TestBox('Large', 250, 175, 100, 0, 0, 0, 0, 100000));
$rot = TestItem::ROTATION_BEST_FIT; // TestItem::ROTATION_KEEP_FLAT;
$packer->addItem(new TestItem('Item 1', 105,  70,  14, 0, $rot), 1);
$packer->addItem(new TestItem('Item 2', 152, 101,   5, 0, $rot), 1);        
$packer->addItem(new TestItem('Item 3',  80,  70,  50, 0, $rot), 1);
$packer->addItem(new TestItem('Item 4',  97,  71,  28, 0, $rot), 1);
$packer->addItem(new TestItem('Item 5',  95,  70,  28, 0, $rot), 1); 
$packedBoxes = $packer->pack();

This leads to Packer() suggesting the large box although everything would fit into the small box as well.

Just providing the small box with ROTATION_BEST_FIT leads to Item 2 (yellow) not fitting in the package:

Just providing the small box with ROTATION_KEEP_FLAT would actually work just fine, but somehow it does not fit Item 5 (dark red) anymore, although there is clearly enough space left:

Any ideas?

Best regards, Marco

[Elyos59]

Hi!

Same for me : https://github.com/dvdoug/BoxPacker/discussions/261#discussioncomment-1494520

And if I add 1 unit to my length, width, depth box the result is completely different :(

[dvdoug]

I'll try and take a look later this week

[dvdoug]

$packer->addBox(new TestBox('Small', 160, 130,  70, 0, 0, 0, 0, 100000));
$packer->addBox(new TestBox('Large', 250, 175, 100, 0, 0, 0, 0, 100000));

I assume in the example you meant the below? Otherwise there won't be any results 😅

$packer->addBox(new TestBox('Small', 160, 130,  70, 160, 130,  70, 0, 100000));
$packer->addBox(new TestBox('Large', 250, 175, 100, 250, 175, 100, 100000));

[dvdoug]

This is one of those where when I tweak the logic to make the packing better in this particular scenario better, others regress and get worse. Will keep at it...

[colinmollenhour]

Not sure if I should open a separate task or not but here is a similar example that is actually much simpler:

• 5 units of an item which is 2.6 L x 2.6 W x 4.6 H inches
• One box option that is 7.25 L x 7.25 W x 6.5 H inches (a USPS flat rate box)

This should be able to fit up to 6 units by laying 4 on their side and stacking those 4 two high and then the remaining two upright. However, BoxPacker splits it into two boxes (first one with 3 units shown) but you can see how six would be able to fit:

[dvdoug]

Not sure if I should open a separate task or not

In general yes please as it's very possible there are different issues in play for different scenarios. I've created #272 to track that example