algorithm - 基于极值点的打包算法(3D)

Question

我正在尝试使用基于极值点的方法实现 3D 打包算法。介绍这种方法的论文可以在这里看到:Extreme Point-Based Heuristics for Three-Dimensional Bin Packing

文末还有伪代码的算法(Algorithm 1 Update3DEPL)。我很难理解作者的意思:

• 他用标识符Yx、Yz、Xy、Xz、Zx、Zy指的是什么？我知道他用它来索引数组，但我不知道他的意思。我很确定作者每次都想引用一对轴，但我又不知道那是什么意思。

• 令我更加困惑的是函数CanTakeProjection 的作用以及它需要上述符号(Yx、Yz、...)的目的是什么？此外，该功能的解释对我没有帮助:

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

极端点 k 如何不位于项目 k 的一侧？或者这是一个错字，它应该像下面这样:

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

(注意末尾的“i”而不是“k”。)但同样，extremePoint 位于在项目的一侧是什么意思？它指的是哪一边？任何？或由给定参数 Xy 定义的特定对象(例如)。

我希望我说清楚了我的问题所在。这很难解释。如果有人能为我澄清这一点或为我指明正确的方向，我将不胜感激。

Answer 1

标识符与根据图 5 执行的投影相关，例如Y_x表示将项目k的Y坐标(北边)投影到与项目i的X坐标(东边)相交的x轴上。

CanTakeProjection()根据它们的极值点定义判断得到的投影是否为有效的极值点，包括:

• 需要不一定接触元素k的表面(不能保证接触k，见图4b)，
• 不一定需要触摸项目 i(见图 4a，尤其是 4b)，并且
• 将西南角放在极值点上的项目不得与任何其他项目重叠。有些情况可以在不知道元素尺寸的情况下排除，例如如果极值点触及另一个项目 i 的南边界(不包括东南角)。

请参阅以下 C++ 实现。

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

以及检查投影是否产生有效极值点的方法:

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