Problem stacking boxes using BestFit

[howdu]

These two items should be stacked on top of each other but it's unable to fit them. Strangle it works when you specify KeepFlat.

$box = new TestBox('Example box', 380, 380, 140, 0, 380, 380, 140, 0);

$itemList = new ItemList();
$itemList->insert(new TestItem('Item 1', 315, 315, 11, 0, Rotation::BestFit));
$itemList->insert(new TestItem('Item 2', 135, 135, 80, 0, Rotation::BestFit));

$packer = new VolumePacker($box, $itemList);
$packedBox = $packer->pack();

self::assertCount(2, $packedBox->getItems());

Logging

[EVALUATING BOX] Box {"box":{"TestBox":{"reference":"Box","innerWidth":380,"innerLength":380,"innerDepth":140,"emptyWeight":0,"maxWeight":0}}} [EVALUATING ROTATION] Box {"width":380,"length":380} evaluating item Item 1 for fit {"item":{"TestItem":{"description":"Item 1","width":135,"length":135,"depth":80,"weight":0,"keepFlat":0}},"space":{"widthLeft":380,"lengthLeft":380,"depthLeft":140},"position":{"x":0,"y":0,"z":0}} Lookahead with orientation {"packedCount":0,"orientatedItem":{"DVDoug\BoxPacker\OrientatedItem":{"item":{"description":"Item 1","width":135,"length":135,"depth":80,"weight":0,"keepFlat":0},"width":135,"length":135,"depth":80}}} Lookahead with orientation {"packedCount":0,"orientatedItem":{"DVDoug\BoxPacker\OrientatedItem":{"item":{"description":"Item 1","width":135,"length":135,"depth":80,"weight":0,"keepFlat":0},"width":135,"length":80,"depth":135}}} Lookahead with orientation {"packedCount":0,"orientatedItem":{"DVDoug\BoxPacker\OrientatedItem":{"item":{"description":"Item 1","width":135,"length":135,"depth":80,"weight":0,"keepFlat":0},"width":80,"length":135,"depth":135}}} Selected best fit orientation {"orientation":{"DVDoug\BoxPacker\OrientatedItem":{"item":{"description":"Item 1","width":135,"length":135,"depth":80,"weight":0,"keepFlat":0},"width":135,"length":80,"depth":135}}} evaluating item Item 0 for fit {"item":{"TestItem":{"description":"Item 0","width":315,"length":315,"depth":11,"weight":0,"keepFlat":0}},"space":{"widthLeft":135,"lengthLeft":0,"depthLeft":140},"position":{"x":0,"y":80,"z":0}} no items fit, so starting next vertical layer evaluating item Item 0 for fit {"item":{"TestItem":{"description":"Item 0","width":315,"length":315,"depth":11,"weight":0,"keepFlat":0}},"space":{"widthLeft":245,"lengthLeft":380,"depthLeft":140},"position":{"x":135,"y":0,"z":0}} No more fit in width wise, resetting for new row evaluating item Item 0 for fit {"item":{"TestItem":{"description":"Item 0","width":315,"length":315,"depth":11,"weight":0,"keepFlat":0}},"space":{"widthLeft":380,"lengthLeft":300,"depthLeft":140},"position":{"x":0,"y":80,"z":0}} no items fit, so starting next vertical layer evaluating item Item 0 for fit {"item":{"TestItem":{"description":"Item 0","width":315,"length":315,"depth":11,"weight":0,"keepFlat":0}},"space":{"widthLeft":380,"lengthLeft":380,"depthLeft":5},"position":{"x":0,"y":0,"z":135}} no items fit, so starting next vertical layer evaluating item Item 0 for fit {"item":{"TestItem":{"description":"Item 0","width":315,"length":315,"depth":11,"weight":0,"keepFlat":0}},"space":{"widthLeft":245,"lengthLeft":380,"depthLeft":140},"position":{"x":135,"y":0,"z":0}} no items fit, so starting next vertical layer evaluating item Item 0 for fit {"item":{"TestItem":{"description":"Item 0","width":315,"length":315,"depth":11,"weight":0,"keepFlat":0}},"space":{"widthLeft":380,"lengthLeft":300,"depthLeft":140},"position":{"x":0,"y":80,"z":0}} no items fit, so starting next vertical layer

[oddvalue]

To add more info to this, the item list gets sorted so that the 2nd box gets checked first because it has a greater volume. It then tries several orientations for that box, except just lying it flat, and fails to fit the 1st box. If you bump the depth of the 1st item up to 15 it works fine.

[dvdoug]

Hi, thanks for the minimal testcase - makes it a lot easier to reproduce and debug.

This is one of those ones where I can easily make changes that makes this particular example pack better, but then others end up packing worse - I'll keep seeing if I can find the right heuristic.

Is this just an odd example that you've found, or this a typical scenario for what you're trying to pack with a large flat item that's almost (but not quite), the same dimensions as the box not being put at the bottom?

[howdu]

Thanks for looking into this @dvdoug - it's a great package and all other package combinations are working flawlessly.

The issue we're having is with a vinyl record box plus a DVD box set, and the reason for the outer box dimensions.

[dvdoug]

OK, I'll certainly keep this on the list. In the meantime, something that might work for you is using custom sorting - as this works when the vinyl is packed first, depending on your application you can probably enforce that using the mechanism at https://boxpacker.io/en/stable/sortation.html#overriding-the-default-algorithm

$sorter = new CustomItemSorter();
$itemList = new ItemList($sorter);

class CustomItemSorter extends DefaultItemSorter
{
    public function compare(Item $itemA, Item $itemB): int
    {
        if ($itemA->isVinyl()) {  // or check a category, or ->getDepth() < 15 or whatever works in your app to identify one
          return -1;
        }

        if ($itemB->isVinyl()) {
          return 1;
        }

        // fall back to regular rules
        return parent::compare($itemA, $itemB);
    }
}