Extreme point based-packing algorithm (3D)

Question

I am trying to implement a 3D packing algorithm using the extreme point-based approach. The paper which introduced this approach can be seen here: Extreme Point-Based Heuristics for Three-Dimensional Bin Packing

At the end of the paper there is also an algorithm (Algorithm 1 Update3DEPL) in pseudo code. I have quite a hard time to understand what the author meant with the following:

• What is he referring to with the identifiers Yx, Yz, Xy, Xz, Zx, Zy? I know that he uses this to index the array, however i don't know what he means by this. I am pretty sure tho that the author wants to refer to an pair of axis each time but then again I have no clue what that means.

• What I am even more confused about is what the function CanTakeProjection does and what it needs the above mentioned symbols (Yx, Yz, ...) for? Also the explanation of the function didn't help me:

CanTakeProjection: function returning true if an EP k lie on the side of an item k

How should the extremePoint k not lie on a side of an item k ever? Or is this a typo and it should be like following:

CanTakeProjection: function returning true if an EP k lie on the side of an item i

(Note the 'i' at the end instead of the 'k'.) But again, what does it mean that an extremePoint lies on the side of an item? And which side does it mean? Any? Or a specific defined by the given parameter Xy (for example).

I hope I made clear what my problem is. It's quite tricky to explain. I would highly appreciate it if anyone could clarify this for me or point me in the right direction.

Hux

Answer 1

The identifiers relate to the performed projections according to Figure 5, e.g. Y_x means project the Y coordinate (north edge) of item k on to the on to the x-axis where it intersects with the X coordinate (east edge) of item i.

CanTakeProjection() determines whether the resulting projection is a valid extreme point according to their extreme point definition, which includes:

• need not necessarily touch the surface of item k (touching k is not guaranteed, see Fig. 4b),
• need not necessarily touch item i (see Fig. 4a and especially 4b), and
• that an item that is placed with the south west corner on the extreme point must not overlap with any other item. Some cases can be excluded without knowing the dimensions of the item, e.g. if the extreme points touches the southern border of another item i (excluding the south east corner).

See the following C++ implementation.

std::array<int, 6> maxBound = {-1, -1, -1, -1, -1, -1};
std::array<ExtremePoint, 6> newExtremePoints;

// Depending on the implementation, the initial extreme points might never be used.
newExtremePoints[Projection::YX] = ExtremePoint(newItem.X, newItem.Y + newItem.Dy, newItem.Z);
newExtremePoints[Projection::YZ] = ExtremePoint(newItem.X, newItem.Y + newItem.Dy, newItem.Z);
newExtremePoints[Projection::XY] = ExtremePoint(newItem.X + newItem.Dx, newItem.Y, newItem.Z);
newExtremePoints[Projection::XZ] = ExtremePoint(newItem.X + newItem.Dx, newItem.Y, newItem.Z);
newExtremePoints[Projection::ZX] = ExtremePoint(newItem.X, newItem.Y, newItem.Z + newItem.Dz);
newExtremePoints[Projection::ZY] = ExtremePoint(newItem.X, newItem.Y, newItem.Z + newItem.Dz);

// Extreme point projections for container walls can be handled here or elswhere. 
// For example, introduce auxiliary items as west and south container walls (and one for the container floor if overhang is allowed), and perform the projection onto those, then enter the for loop.

for (const Cuboid* const item: container.PlacedItems)
{    
    int projectedX = item->X + item->Dx;
    int projectedY = item->Y + item->Dy;
    int projectedZ = item->Z + item->Dz;

    // Project the Y coordinate (bottom north west point) of item k in the negative x-direction where it intersects with the X coordinate (east face) of item i.
    if (IsProjectionValidYX(newItem, item) && projectedX > maxBound[Projection::YX])
    {
        newExtremePoints[Projection::YX] = ExtremePoint(projectedX, newItem.Y + newItem.Dy, newItem.Z);
        maxBound[Projection::YX] = projectedX;
    }

    if (IsProjectionValidYZ(newItem, item) && projectedZ > maxBound[Projection::YZ])
    {
        newExtremePoints[Projection::YZ] = ExtremePoint(newItem.X, newItem.Y + newItem.Dy, projectedZ);
        maxBound[Projection::YZ] = projectedZ;
    }

    if (IsProjectionValidXY(newItem, item) && projectedY > maxBound[Projection::XY])
    {
        newExtremePoints[Projection::XY] = ExtremePoint(newItem.X + newItem.Dx, projectedY, newItem.Z);
        maxBound[Projection::XY] = projectedY;
    }

    if (IsProjectionValidXZ(newItem, item) && projectedZ > maxBound[Projection::XZ])
    {
        newExtremePoints[Projection::XZ] = ExtremePoint(newItem.X + newItem.Dx, newItem.Y, projectedZ);
        maxBound[Projection::XZ] = projectedZ;
    }

    if (IsProjectionValidZX(newItem, item) && projectedX > maxBound[Projection::ZX])
    {
        newExtremePoints[Projection::ZX] = ExtremePoint(projectedX, newItem.Y, newItem.Z + newItem.Dz);
        maxBound[Projection::ZX] = projectedX;
    }

    if (IsProjectionValidZY(newItem, item) && projectedY > maxBound[Projection::ZY])
    {
        newExtremePoints[Projection::ZY] = ExtremePoint(newItem.X, projectedY, newItem.Z + newItem.Dz);
        maxBound[Projection::ZY] = projectedY;
    }
}

And the methods to check if a projection results in a valid extreme point:

bool ExtremePoints::IsProjectionValidYX(const Cuboid& newItem, const Cuboid* const item)
{
    return newItem.X >= item->X + item->Dx && newItem.Y + newItem.Dy < item->Y + item->Dy && newItem.Z < item->Z + item->Dz;
}

bool ExtremePoints::IsProjectionValidYZ(const Cuboid& newItem, const Cuboid* const item)
{
    return newItem.Z >= item->Z + item->Dz && newItem.Y + newItem.Dy < item->Y + item->Dy && newItem.X < item->X + item->Dx;
}

bool ExtremePoints::IsProjectionValidXY(const Cuboid& newItem, const Cuboid* const item)
{
    return newItem.Y >= item->Y + item->Dy && newItem.X + newItem.Dx < item->X + item->Dx && newItem.Z < item->Z + item->Dz;
}

bool ExtremePoints::IsProjectionValidXZ(const Cuboid& newItem, const Cuboid* const item)
{
    return newItem.Z >= item->Z + item->Dz && newItem.X + newItem.Dx < item->X + item->Dx && newItem.Y < item->Y + item->Dy;
}

bool ExtremePoints::IsProjectionValidZX(const Cuboid& newItem, const Cuboid* const item)
{
    return newItem.X >= item->X + item->Dx && newItem.Z + newItem.Dz < item->Z + item->Dz && newItem.Y < item->Y + item->Dy;
}

bool ExtremePoints::IsProjectionValidZY(const Cuboid& newItem, const Cuboid* const item)
{
    return newItem.Y >= item->Y + item->Dy && newItem.Z + newItem.Dz < item->Z + item->Dz && newItem.X < item->X + item->Dx;
}

Untie

Firstly, thank you @Untie for your post, it was very useful in helping understand the paper. I'm not sure however about your definition of newExtremePoints. With no zeros in the initial state, does this not mean that they will never project on to the axes (unless perhaps another object already lies on that axis)? Figure 5 of the paper shows a one item container. All of the extreme points lie on the axes in the projected dimension. But in your code, they will lie on the item corners, which are not actual extreme points. – Warfold

Yes you are right, with only the snippet that I have posted, the extreme points will never be projected onto the west and south walls of the container. I left it out because there are several ways to handle this, and the paper does not specify. For example, what you can do is to add auxiliary items that act as a west and as a south wall of the container. Perform the projection onto the auxiliary items, then enter the for loop. – Untie

Interesting. It seems like an important case for the algorithm, it's a shame there's not a little more help in the paper. I'm seeding my extreme points with 0 at the projected axis, e.g. in your code newExtremePoints[Projection::YX] = ExtremePoint(0, newItem.Y + newItem.Dy, newItem.Z);. This seems natural given how the existing containers are handled, but I'm yet to convince myself this is definitely correct. – Warfold

I don't know the rest of your implementation, so it's hard to tell. If you use the projection on the auxiliary walls, it should not matter because the initial extreme points will never be used (maxBound == -1), or will be overriden by the first feasible projection with maxBound >= 0. Somewhere there should be a line to the effect if (maxBound[i] < 0) continue;. Is this helpful? Can you confirm? – Untie

It's definitely helpful to see a different method. However I don't think we should reject extreme points with maxBound == -1. It's a valid extreme point, which lies on the axis. As you say, if there are any existing items between the new item and the boundary, that will override it, which seems to be the intention of the algorithm in the paper? – Warfold

maxBound gives the maximum coordinate for which a valid projection exists. maxBound == -1 is intended to mean the associated extreme point is invalid, because it lies outside the container. Of course, for your "seeded" points, you can (and should) set maxBound == 0: they touch the walls, i.e. lie at 0 on their axis. Caution, this way you might very well end up with many extreme points inside other items (items that touch container walls), which should be taken care of. If not, there's a considerable performance penalty, especially for instances with many items. – Untie

The maxBound of an item would never be zero unless you had an item with 0 volume, since an item on the x axis would have maxBound = object width. So, my maxBound == -1 extreme points (on the axis) will only end up as a selected extreme point if no other objects are discovered with a valid projection and a higher maxBound. I'll only ever select 6 points per added item, as per the paper. I also prune the ones that have become occluded to avoid performance issues. – Warfold

Well, if you define your extreme points on the container wall to have maxBound == -1 and filter infeasible points in a separate routine, then that should be fine. I still think it's clearer to make them have maxBound == 0 because -1 is intended for infeasible points. E.g., my extreme points on container walls have maxBound == 0, when I encounter something that causes this extreme point to become infeasible I set maxBound == -1 (think no stacking allowed on certain items -> blocks extreme points above that item). Thanks for the discussion, hopefully this is helpful to future readers. – Untie

Answer 2

Probably not helpful 2 years later...but I found your question when looking for the same answer. Ultimately, I figured them out.

What is he referring to with the identifiers Yx, Yz, Xy, Xz, Zx, Zy? I know that he uses this to index the array, however i don't know what he means by this. I am pretty sure tho that the author wants to refer to an pair of axis each time but then again I have no clue what that means.

It's basically the conglomeration of X,Y,Z's of the current item being packed and the X,Y,Z's of every item already packed (since it's a loop), to get all new appropriate extreme points. Example...Yx is the x:(x + width) of the ith item, y:y + length of the item being packed, z of the item being packed. Xy is the x:(x + width) of the item being packed, y:(y + length) of the ith item, z of the item being packed.

What I am even more confused about is what the function CanTakeProjection does and what it needs the above mentioned symbols (Yx, Yz, ...) for? Also the explanation of the function didn't help me: "CanTakeProjection: function returning true if an EP k lie on the side of an item k" How should the extremePoint k not lie on a side of an item k ever? Or is this a typo and it should be like following: "CanTakeProjection: function returning true if an EP k lie on the side of an item i"

If you actually draw out the extreme points it makes sense. Sometimes an extreme point calculation won't be touching the new packed item at all. So that is not a valid extreme point. So it is correct being 'k'. Early in the paper, it refers to a Corner points algorithm, which tries a new item on each point. The more you pack the slower the algorithm gets. These guys realized that you don't really care about each point, just the furthest out in each axis direction, e.g. extreme point. So the CanTakeProjection is just saying, is the calculated point touching item k...we know it'll be touching item i.

The one the threw me was the Clustered Height-Area sort, and what was j in that calculation. It seems easy now, but j is just 0, 1, 2, 3, ... until you get to the box height, then each item's height must be greater than the lower bound and less than or equal to the upper bound, then sorted by decreasing cluster.

They could have definitely added a sentence here and there to make the paper way more understandable.

Hemichordate

I am currently trying to understand CanTakeProjection. I don't follow your comments here though. It is fine for extreme points to not touch any item at all - the paper shows these, in the blue areas where there is an item above and to the right of an empty space. – Warfold