# 3D bin packing in Java

Posted on

Problem

I made some changes to the first code here I wrote and I want to know which one is more correct logically (before the changes or after the changes).

It’s really hard to manually test these kind of problems.

This is the first code (without the changes):

``````public boolean put3D(ItemsUnit item, int p,int n) {

//------if x still did not exceed the container's length
if(x<length){
//--------if we can put the new item next to the item packed in the extreme point of length
if(putL(item,p)) {
packedItems.add(item); // if item fits add it to the packedItems into the container
return true;
}
}

//------if y still did not exceed the container's breadth

//--------if we can put the new item next to the item packed in the extreme point of breadth
if(putB(item,p)){
packedItems.add(item); // if item fits add it to the packedItems into the container
return true;
}
}

//------if z still did not exceed the container's height
if(z<height){
//--------if we can put the new item next to the item packed in the extreme point of height
if(putH(item,p)){
packedItems.add(item); // if item fits add it to the packedItems into the container
return true;
}
}

return false; //return false if item cannot be packed in neither extreme point
}

//-----------adding the new item to the extreme point in length
private boolean putL(ItemsUnit item, int p) {
double minRemL=remainingLength[0]; //the minimum remaining length of all already packed items
int i=0; //to store the index of the item next to which we should put the new item

//--------choosing the point (position) where to put the new item----
for (int j=0; j<remainingLength.length; j++){
if ((remainingLength[j] != 0) && (minRemL >= remainingLength[j]) && (remainingLength[j] >= item.getLength())){
i=j; //storing the item next to which we should put the new packed item
minRemL=remainingLength[j]; //minimum length left
}
}

remainingLength[p]=remainingLength[i]-item.getLength(); //update the remaining length of the new item added
remainingHeight[p]-=item.getHeight(); //update the remaining height of the new item added
remainingLength[i]=0; //insert 0 to the remainingLength of the item next to which we put the new item (so that we don't consider its remaining length anymore)

x+=item.getLength(); //increment x by the length of the new packed item in the extreme point of length
return true;
}

private boolean putB(ItemsUnit item, int p) {
int i=0;//to store the index of the item next to which we should put the new item

//--------choosing the point (position) where to put the new item----
i=j; //choosing the item to which we should put the new packed item next to
}
/*else {
return false; //------return false if all the positions cannot fit the new item
}*/
}

remainingHeight[p]-=item.getHeight();//update the remaining height of the new item added
remainingLength[p]-=item.getLength(); //update the remaining length of the new item added
remainingBreadth[i]=0; //insert 0 to the remainingBreadth of the item next to which we put the new item (so that we don't consider its remaining breadth anymore)

y+=item.getBreadth(); //increment y by the breadth of the new packed item in the extreme point of breadth
//x=length-remainingLength[p]; //update x to the position of the item next to which we put the new item
return true;
}

//-----------adding the new item to the extreme point in height
private boolean putH(ItemsUnit item, int p) {
double minRemH=remainingHeight[0]; //the minimum remaining height of all already packed items
int i=0; //to store the index of the item next to which we should put the new item

//--------choosing the point (position) where to put the new item----
for (int j=0; j<remainingHeight.length; j++){
if ((remainingHeight[j] !=0 )&&(minRemH >= remainingHeight[j]) && (remainingHeight[j] >= item.getHeight())){
i=j; //choosing the item to which we should put the new packed item next to
minRemH=remainingHeight[j]; //minimum length left
}
/*else {
return false; //------return false if all the positions cannot fit the new item
}*/
}

remainingHeight[p]=remainingHeight[i]-item.getHeight(); //update the remaining height of the new item added
remainingLength[p]-=item.getLength();//update the remaining length of the new item added
remainingHeight[i]=0; //insert 0 to the remainingHeight of the item next to which we put the new item (so that we don't consider its remaining height anymore)

z+=item.getHeight(); //increment z by the height of the new packed item in the extreme point of height
return true;
}
``````

I changed the code by adding:

``````            x=remainingLength[p]; // update x to the position of the new item added
z=remainingHeight[p]; // update z to the position of the new item added

``````

This is the full code after changes:

``````public boolean put3D(ItemsUnit item, int p,int n) {

//------if x still did not exceed the container's length
if(x<length){

z=remainingHeight[p]; // update z to the position of the new item added

//--------if we can put the new item next to the item packed in the extreme point of length
if(putL(item,p)) {
packedItems.add(item); // if item fits add it to the packedItems into the container
return true;
}
}

//------if y still did not exceed the container's breadth
x=remainingLength[p]; // update x to the position of the new item added
z=remainingHeight[p]; // update z to the position of the new item added
//--------if we can put the new item next to the item packed in the extreme point of breadth
if(putB(item,p)){
packedItems.add(item); // if item fits add it to the packedItems into the container
return true;
}
}

//------if z still did not exceed the container's height
if(z<height){

x=remainingLength[p]; // update x to the position of the new item added

//--------if we can put the new item next to the item packed in the extreme point of height
if(putH(item,p)){
packedItems.add(item); // if item fits add it to the packedItems into the container
return true;
}
}

return false; //return false if item cannot be packed in neither extreme point
}

//-----------adding the new item to the extreme point in length
private boolean putL(ItemsUnit item, int p) {
double minRemL=remainingLength[0]; //the minimum remaining length of all already packed items
int i=0; //to store the index of the item next to which we should put the new item

//--------choosing the point (position) where to put the new item----
for (int j=0; j<remainingLength.length; j++){
if ((remainingLength[j] != 0) && (minRemL >= remainingLength[j]) && (remainingLength[j] >= item.getLength())){
i=j; //storing the item next to which we should put the new packed item
minRemL=remainingLength[j]; //minimum length left
}
}

remainingLength[p]=remainingLength[i]-item.getLength(); //update the remaining length of the new item added
remainingHeight[p]-=item.getHeight(); //update the remaining height of the new item added
remainingLength[i]=0; //insert 0 to the remainingLength of the item next to which we put the new item (so that we don't consider its remaining length anymore)

x+=item.getLength(); //increment x by the length of the new packed item in the extreme point of length
return true;
}

private boolean putB(ItemsUnit item, int p) {
int i=0;//to store the index of the item next to which we should put the new item

//--------choosing the point (position) where to put the new item----
i=j; //choosing the item to which we should put the new packed item next to
}
/*else {
return false; //------return false if all the positions cannot fit the new item
}*/
}

remainingHeight[p]-=item.getHeight();//update the remaining height of the new item added
remainingLength[p]-=item.getLength(); //update the remaining length of the new item added
remainingBreadth[i]=0; //insert 0 to the remainingBreadth of the item next to which we put the new item (so that we don't consider its remaining breadth anymore)

y+=item.getBreadth(); //increment y by the breadth of the new packed item in the extreme point of breadth
//x=length-remainingLength[p]; //update x to the position of the item next to which we put the new item
return true;
}

//-----------adding the new item to the extreme point in height
private boolean putH(ItemsUnit item, int p) {
double minRemH=remainingHeight[0]; //the minimum remaining height of all already packed items
int i=0; //to store the index of the item next to which we should put the new item

//--------choosing the point (position) where to put the new item----
for (int j=0; j<remainingHeight.length; j++){
if ((remainingHeight[j] !=0 )&&(minRemH >= remainingHeight[j]) && (remainingHeight[j] >= item.getHeight())){
i=j; //choosing the item to which we should put the new packed item next to
minRemH=remainingHeight[j]; //minimum length left
}
/*else {
return false; //------return false if all the positions cannot fit the new item
}*/
}

remainingHeight[p]=remainingHeight[i]-item.getHeight(); //update the remaining height of the new item added
remainingLength[p]-=item.getLength();//update the remaining length of the new item added
remainingHeight[i]=0; //insert 0 to the remainingHeight of the item next to which we put the new item (so that we don't consider its remaining height anymore)

z+=item.getHeight(); //increment z by the height of the new packed item in the extreme point of height
return true;
}
``````

I need to know which one is logically correct.

Solution

In this case, what you ought to do is write tests that attempt to pack various items into a box. Perhaps you could iterate over a set of boxes each 1 to 3 large in each of the 3 dimensions, (makes for 27 different boxes), that you then try to put into a larger box. Maybe try putting 4 (531441 combinations) (or maybe 5, but that’s gonna take a while, 14348907 different combinations) of those boxes into a 4x4x4 cube, and the algorithm that packs the most wins? (if you’re gonna pack 5 boxes, try 5x5x5 cube or 4x5x5 cube).

Maybe start small with 1-2 in all dimensions, 3 cubes in a 3x3x3 cube. (2*2*2 means 8 different boxes, 3 of those boxes means 8*8*8 possible box combinations [that’s 512], meaning that even if your code takes a full second to test both algorithms like that, it’ll be done in 10 minutes. Compare that to the other case which could take weeks at 1 second per combination and a day at 0.1 seconds per combination, which is too long for you to make sense out of.)

For performance of such a test, you could skip cases where the volume of the boxes to put in the cube is greater than the volume of the cube, as the algorithm should fail to put in all the boxes.

You’d need to record any differences in results between the two algorithms and print out those cases and see which algorithm is better like that. Then you can inspect the differences to see if there’s any weird behaviour.

Like that, you can objectively test the correctness of each algorithm. Be sure to check if each item is actually in the box and doesn’t clip with other items, or you’ll find that the buggiest algorithm wins.