[Python] 3D Bin packing and Intersection locations

I am currently using Py3dbp to show how I could fill a shipping container with parts. I have modified it a good bit but I need to add a "shelf" to place items on inside the bin. Here is what it looks like so far:

Here the red line is the door of the container and the blue is the shelf. As you can see the shelf is drawn in the figure but the items ignore the area. I need to have the items pack around the shelf. There is an auxiliary method script in the py3dbp library that has an intersection function:

from decimal import Decimal
from .constants import Axis


def rectIntersect(item1, item2, x, y):
d1 = item1.getDimension()
d2 = item2.getDimension()

cx1 = item1.position[x] + d1[x]/2
cy1 = item1.position[y] + d1[y]/2
cx2 = item2.position[x] + d2[x]/2
cy2 = item2.position[y] + d2[y]/2

ix = max(cx1, cx2) - min(cx1, cx2)
iy = max(cy1, cy2) - min(cy1, cy2)

return ix < (d1[x]+d2[x])/2 and iy < (d1[y]+d2[y])/2


def intersect(item1, item2):
return (
rectIntersect(item1, item2, Axis.WIDTH, Axis.HEIGHT) and
rectIntersect(item1, item2, Axis.HEIGHT, Axis.DEPTH) and
rectIntersect(item1, item2, Axis.WIDTH, Axis.DEPTH)
)


def binIntersect(item, bin, x, y):
# Assuming 'bin' has 'width', 'height', 'depth', and 'position' attributes
d1 = item.getDimension()
d2 = [bin.width, bin.height, bin.depth/2] # Modify based on your Bin class attributes

cx1 = item.position[x] + d1[x]/2
cy1 = item.position[y] + d1[y]/2
cx2 = bin.width + d2[Axis.WIDTH]/2
cy2 = bin.height + d2[Axis.HEIGHT]/2

ix = max(cx1, cx2) - min(cx1, cx2)
iy = max(cy1, cy2) - min(cy1, cy2)

return ix < (d1[Axis.WIDTH] + d2[Axis.WIDTH])/2 and iy < (d1[Axis.HEIGHT] + d2[Axis.HEIGHT])/2


def itemIntersectsWithBin(item, bin):
# Assuming 'item' has 'position' and 'getDimension' methods
return (
binIntersect(item, bin, Axis.WIDTH, Axis.HEIGHT) and
binIntersect(item, bin, Axis.HEIGHT, Axis.DEPTH) and
binIntersect(item, bin, Axis.WIDTH, Axis.DEPTH/2)
)


def getLimitNumberOfDecimals(number_of_decimals):
return Decimal('1.{}'.format('0' * number_of_decimals))


def set2Decimal(value, number_of_decimals=0):
number_of_decimals = getLimitNumberOfDecimals(number_of_decimals)

return Decimal(value).quantize(number_of_decimals)


I added the binIntersect and itemIntersectWithBin functions to try to solve this issue I am having, but it does not seem to work when I add use it in the main script PackItem function here:

def putItem(self, item, pivot,axis=None):
''' put item in bin '''
fit = False
valid_item_position = item.position
item.position = pivot
shelf = self.shelfBin()

# rotate = RotationType.ALL if item.updown == True else RotationType.Notupdown
rotate = RotationType.ALL if item.updown else RotationType.Notupdown
for i in range(0, len(rotate)):
item.rotation_type = i
dimension = item.getDimension()
shelf_dimension = shelf.getBinDimension()
# rotatate

if (
self.width < pivot[0] + dimension[0] or
self.height < pivot[1] + dimension[1] or
self.depth < pivot[2] + dimension[2]
):
continue

fit = True

# Check for intersection with shelf_bin
for current_item_in_bin in self.items:
if intersect(current_item_in_bin, item) or itemIntersectsWithBin(current_item_in_bin, shelf):
fit = False
break

# shelf.dimension = (self.width, self.height, self.depth / 2 + 6) # Adjust dimensions based on your shelf Bin definition
# if itemIntersectsWithBin(item, shelf):
# fit = False
# break

if fit:
# cal total weight
if self.getTotalWeight() + item.weight > self.max_weight:
print("Too Heavy for container: ", self.item.partno)
fit = False
return fit

# fix point float prob
if self.fix_point == True :

[w,h,d] = dimension
[x,y,z] = [float(pivot[0]),float(pivot[1]),float(pivot[2])]

for i in range(3):
# fix height
y = self.checkHeight([x,x+float(w),y,y+float(h),z,z+float(d)])
# fix width
x = self.checkWidth([x,x+float(w),y,y+float(h),z,z+float(d)])
# fix depth
z = self.checkDepth([x,x+float(w),y,y+float(h),z,z+float(d)])

# check stability on item
# rule :
# 1. Define a support ratio, if the ratio below the support surface does not exceed this ratio, compare the second rule.
# 2. If there is no support under any vertices of the bottom of the item, then fit = False.
if self.check_stable == True :
# Cal the surface area of item.
# item_area_lower = int(dimension[0] * dimension[1])
item_area_lower = dimension[0] * dimension[1]
# Cal the surface area of the underlying support.
support_area_upper = 0
for i in self.fit_items:
# Verify that the lower support surface area is greater than the upper support surface area * support_surface_ratio.
if z == i[5] :
area = len(set([ j for j in range(int(x),int(x+int(w)))]) & set([ j for j in range(int(i[0]),int(i[1]))])) * \
len(set([ j for j in range(int(y),int(y+int(h)))]) & set([ j for j in range(int(i[2]),int(i[3]))]))
support_area_upper += area

# If not , get four vertices of the bottom of the item.
if support_area_upper / item_area_lower < self.support_surface_ratio :
four_vertices = [[x,y],[x+float(w),y],[x,y+float(h)],[x+float(w),y+float(h)]]
# If any vertices is not supported, fit = False.
c = [False,False,False,False]
for i in self.fit_items:
if z == i[5] :
for jdx,j in enumerate(four_vertices) :
if (i[0] <= j[0] <= i[1]) and (i[2] <= j[1] <= i[3]) :
c[jdx] = True
if False in c :
item.position = valid_item_position
fit = False
return fit

self.fit_items = np.append(self.fit_items,np.array([[x,x+float(w),y,y+float(h),z,z+float(d)]]),axis=0)
item.position = [set2Decimal(x),set2Decimal(y),set2Decimal(z)]

# shelf.putItem(copy.deepcopy(item))
self.items.append(copy.deepcopy(item))


# if fit :
# # # if shelf_bin and not shelf_bin.is_stable():


# self.items.append(copy.deepcopy(item))
else :
item.position = valid_item_position

return fit

else :
item.position = valid_item_position

return fit


So the end goal is to have the capability to read the area of the shelf and check to see the item intersects the area of the shelf and if it does, to try and add it on top the shelf or remove it.

For reference, here is the visual for the shelf.

self._shelf(ax,0, 0, float(self.depth)/2-0.5, float(self.width), float(self.height), 6.0,color='blue',mode=1,linewidth=2,text="Shelf")
# fit rotation type

Continue reading...