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.

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;
}