Algorithm for calculating the extreme point (3D)
I am trying to implement a 3D packing algorithm using an extreme point approach. The paper that introduced this approach can be seen here: Extreme point heuristics for 3D bin packing
At the end of the article there is also an algorithm ( Algorithm 1 Update3DEPL ) in pseudocode. I find it very difficult to understand what the author meant:
-
What does he mean with identifiers
Yx, Yz, Xy, Xz, Zx, Zy
? I know he uses this to index the array, however I don't know what he means. I'm sure the author wants to reference a pair of axes every time, but then I don't know what that means yet. -
What confuses me even more is what the function does
CanTakeProjection
and what are the above symbols (Yx, Yz, ...) for? Also the explanation of the function didn't work for me:
CanTakeProjection: the function returns true if EP k lies on the side of element k
How does an extreme object k not lie on the side of element k? Or is it a typo and it should look like this:
CanTakeProjection: function returns true if EP k lies on the side of element i
(Note the "i" at the end, not the "k"). But then again, what does it mean that the extreme point lies on the side of the element? And which side does it mean? Anyone? Or specific, defined by the given parameter Xy (for example).
I hope I have clarified what my problem is. This is rather difficult to explain. I would really appreciate it if someone could clarify this for me or point me in the right direction.
source to share
Probably useless 2 years later ... but I found your question when I was looking for the same answer. Eventually, I figured them out.
What is it referring to with the identifiers Yx, Yz, Xy, Xz, Zx, Zy? I know he uses this to index the array, however I don't know what he means. I'm pretty sure the author wants to reference a pair of axes every time, but then again, I have no idea what that means.
It is basically a conglomeration of the X, Y, Z of the current packaged item and the X, Y, Z of each packaged item (since this is a loop) to get all new matching extreme points. Example ... Yx is x: (x + width) of the i-th item, y: y + the length of the item to be packed, z of the item to be packed. Xy is x: (x + width) of the item to be packed, y: (y + length) of the i-th item, z of the item to be packed.
What confuses me even more is what the CanTakeProjection function does and what does it need the above characters (Yx, Yz, ...) for? Also the explanation of the function did not help: "CanTakeProjection: function that returns true if EP k lies on the side of k" How should the endpoint k not lie on the side of k ever? Or it's a typo, and it should look something like this: "CanTakeProjection: function that returns true if EP k lies on the side of element i"
If you are really drawing the extreme points, this makes sense. Sometimes the calculation of extreme points does not concern a new packaged item at all. So this is not a valid extreme point. So it's right to be "k". At the beginning of the article, this refers to the corner point algorithm, which tries a new element at each point. The more you pack, the slower the algorithm becomes. These guys realized that you don't care about every point, only the farthest axis in each direction, for example, the extreme point. So CanTakeProjection simply says that the computed point touches element k ... we know that it touches element i.
What threw me off was sorting Clustered Height-Area, and what was j in that calculation. Now this seems easy, but j is 0, 1, 2, 3, ... until you get to the block height, then the height of each element must be greater than the bottom border and less than or equal to the top border, then sorted in descending order of the cluster.
They could definitely add a sentence here and there to make the paper path clearer.
source to share