Question about rotation flags

[neodisco]

I am using dev-master as I've been trying to debug a particular problem trying to get the correct number of items in a box.

@dvdoug can you let me know why "keep flat" (as well as 0) provides a better result than "best fit"? Should I always run each option as a possible scenario to ensure the highest chance of a successful pack?

Thank you for an amazing library.

Test:

use DVDoug\BoxPacker\VolumePacker;
use DVDoug\BoxPacker\ItemList;
use DVDoug\BoxPacker\Item;
use DVDoug\BoxPacker\Test\TestItem;
use DVDoug\BoxPacker\Test\TestBox;

$rotations = [
    0,
    Item::ROTATION_NEVER,
    Item::ROTATION_KEEP_FLAT,
    Item::ROTATION_BEST_FIT,
];

foreach ($rotations as $rotation) {
    $box = new TestBox('A Box', 279, 215, 139, 10, 279, 215, 139, 100000);

    $items = new ItemList();
    $items->insert(new TestItem('Item A-1', 160, 160, 64, 1, $rotation));
    $items->insert(new TestItem('Item A-2', 160, 160, 64, 1, $rotation));
    $items->insert(new TestItem('Item B-1', 203, 114, 51, 1, $rotation));
    $items->insert(new TestItem('Item B-2', 203, 114, 51, 1, $rotation));

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

    echo "Rotation Value: $rotation -> Items that Fit: ".count($packedBox->getItems())."\n\n";

Output:

Rotation Value: 0 -> Items that Fit: 4
Rotation Value: 1 -> Items that Fit: 2
Rotation Value: 2 -> Items that Fit: 4
Rotation Value: 6 -> Items that Fit: 3

[neodisco]

As a possibly related issue, switching the last two dimensions in item B stops 4 items being packed using any rotation paradigm.

foreach ($rotations as $rotation) {
    $box = new TestBox('A Box', 279, 215, 139, 10, 279, 215, 139, 100000);

    $items = new ItemList();
    $items->insert(new TestItem('Item A-1', 160, 160, 64, 1, $rotation));
    $items->insert(new TestItem('Item A-2', 160, 160, 64, 1, $rotation));
    $items->insert(new TestItem('Item B-1', 203, 51, 114, 1, $rotation));
    $items->insert(new TestItem('Item B-2', 203, 51, 114, 1, $rotation));

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

    echo "Rotation Value: $rotation -> Items that Fit: ".count($packedBox->getItems())."\n\n";
}

Output:

Rotation Value: 0 -> Items that Fit: 3
Rotation Value: 1 -> Items that Fit: 2
Rotation Value: 2 -> Items that Fit: 3
Rotation Value: 6 -> Items that Fit: 3

[dvdoug]

Hi @neodisco. Thanks for the report.

Several things to pick through here:

0 isn't supposed to be a supported value, by using it I think you've accidentally trigged a 2D rotation packing - the item has not been rotated, but the box has been which gives the same end result. I'll add a tweak so that 0 is treated the same as 1.

In your 2nd example with the swapped dimensions - that looks "expected" to me I think[1]. The packer only packed 4 items when 2D packing was used - by swapping length and depth (height), the 2D packing will have had different dimensions to work with so will have had a different result. The 3D rotation packing will have had the same orientations to work with as before the swap, so having the same result there is normal.

As to why 2D packing gives a better result than 3D packing in this case...it can happen. There is no known algorithm that guarantees optimal packing for all possible combinations of items and boxes other than to try literally every possible permutation of every item in every orientation in every placement. The performance of that for anything but a very small number of items would be....not good 😅.

Having said that, I do consider any report of a non-optimal orientation selection to be a bug so I'll see if I can find a heuristic that improves this scenario without regressing others.

[1]I haven't done the maths to check if packing all 4 items with those dimensions and 2D rotation only is physically possible or not...

[neodisco]

Thanks Doug!

Thank you for taking the time to reply and for your promptness.

[1]I haven't done the maths to check if packing all 4 items with those dimensions and 2D rotation only is physically possible or not...

I have viewed it in 3D and it looks right to me (below) (No guarantees my alpha-quality viewer doesn't have a bug but it is proving reliable).

1. Are there any guidelines for how to best prepare the data before submission to BoxPacker? For example, I am now assuming that all dimensions on both box and items, should be sorted descending, largest to smallest (as that works in this scenario). If this is a false assumption please let me know.

2. I have not given any consideration previously to what "flat" means. Up until now I used all dimensions interchangeably. If I should ensure height is always the smallest dimension (or some other guideline) let me know.

3. If I do need to try various rotation methods it might be nice to be able to specify that as an "override" argument to the ->pack() command, rather than have to remake the item list all over with different flags. I can see an argument both ways.

In this case, this particular and common combination of products is popular (my 3PL alerted me to fact these things could be packed together). For my use-case (small business with common "popular" product combinations), warming up caches using the last 1000 orders worth of data would help me ensure I can keep offered shipping prices down by offering flat rate boxes where possible.

[dvdoug]

1. Are there any guidelines for how to best prepare the data before submission to BoxPacker? For example, I am now assuming that all dimensions on both box and items, should be sorted descending, largest to smallest (as that works in this scenario). If this is a false assumption please let me know.

For BoxPacker purposes, width/length are the 2 "horizontal" dimensions, and depth is the "vertical" dimension. The algorithm tries to pack larger and heavier items at the bottom of the box and thus uses the box width/length as the base area to work with. Which dimension is width and which one is length doesn't really matter for a box except to correctly match up the x and y axes.

2. I have not given any consideration previously to what "flat" means. Up until now I used all dimensions interchangeably. If I should ensure height is always the smallest dimension (or some other guideline) let me know.

"Flat" is intended for e.g. fragile items with a "this way up" sign, where there is defined bottom surface that should be respected. For those items, it's important to specify the depth appropriately to ensure appropriate placement. Again, which dimension is width and which is length is only really important for matching up to axes. For items that are not set to keep flat, the results should be the same regardless of which order the dimensions are specified in.

3. If I do need to try various rotation methods it _might_ be nice to be able to specify that as an "override" argument to the ->pack() command, rather than have to remake the item list all over with different flags. I can see an argument both ways.

I'll think about it - 3D packing should give better results than 2D most of the time, and having an API to try both just in case feels like masking the problem. I'd rather address the root cause if possible and fix any cases of the 3D packing being sub-optimal.

[lvming920716]

hey , you say "I'll think about it - 3D packing should give better results than 2D most of the time, and having an API to try both just in case feels like masking the problem." , i want to know the Api , please ~