基于极值点的打包算法（3D）

Question

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

论文最后还有一个伪代码算法（Algorithm 1 Update3DEPL）。我很难理解作者的意思如下：

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

• 我更困惑的是该函数的CanTakeProjection作用以及它需要上述符号（Yx，Yz，...）的用途？该功能的解释也没有帮助我：

CanTakeProjection：如果 EP k 位于项目 k 的一侧，则函数返回 true

极端点 k 应该如何不位于项目 k 的一侧？或者这是一个错字，它应该如下所示：

CanTakeProjection：如果 EP k 位于项目i的一侧，则函数返回 true

（注意末尾的 'i' 而不是 'k'。）但同样，extremePoint位于项目的一侧是什么意思？它是指哪一边？任何？或者由给定参数 Xy 定义的特定值（例如）。

我希望我说清楚我的问题是什么。解释起来很棘手。如果有人能为我澄清这一点或为我指明正确的方向，我将不胜感激。

Answer 1

两年后可能没有帮助......但我在寻找相同答案时发现了你的问题。最终，我弄清楚了它们。

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

它基本上是当前正在打包的项目的 X、Y、Z 和已打包的每个项目的 X、Y、Z 的组合（因为它是一个循环），以获得所有新的适当极值点。示例...Yx 是第 i 个物品的 x:(x + 宽度)，y:y + 所包装物品的长度，z 是所包装物品的长度。Xy 是被包装物品的 x:(x + 宽度)，y:(y + 长度) 第 i 个物品，被包装物品的 z。

我更困惑的是函数 CanTakeProjection 的作用以及它需要上述符号（Yx，Yz，...）的用途？另外，该函数的解释对我没有帮助：“CanTakeProjection：如果 EP k 位于项目 k 的一侧，则函数返回 true”extremePoint k 应该如何不位于项目 k 的一侧？或者这是一个拼写错误，应该如下所示：“CanTakeProjection：如果 EP k 位于项目 i 的一侧，则函数返回 true”

如果你真的画出了极值点，那就有意义了。有时，极值点计算根本不会触及新包装的物品。所以这不是一个有效的极值点。所以“k”是正确的。在本文的早期，它指的是角点算法，该算法在每个点上尝试一个新项目。打包的越多，算法就越慢。这些人意识到你并不真正关心每个点，只关心每个轴方向上最远的点，例如极值点。所以 CanTakeProjection 只是说，计算出的点是否接触项目 k...我们知道它将接触项目 i。

向我抛出的是聚类高度面积排序，以及该计算中的 j 是什么。现在看起来很简单，但是 j 只是 0, 1, 2, 3, ... 直到达到盒子高度，那么每个项目的高度必须大于下限并小于或等于上限，然后按递减簇排序。

他们绝对可以在这里或那里添加一句话，以使论文更容易理解。