[Python] 2D stacking and optimizing

I have big rectangle (pallet), and would like to stack boxes (smaller rectangles) in way to optimize space usage, currently my problem is I'm not sure how I can rotate the last row/column properly to maximize the utilization of the available space.

I have tried:

Rect class


from typing import List, Tuple
import matplotlib.pyplot as plt
import matplotlib.patches as patches

class Rect:
def __init__(self, corner: Tuple[float, float], size: Tuple[float, float]):
self.length = max(size)
self.width = min(size)
self.center = (corner[0] + self.length/2, corner[1] + self.width/2)
self.size = (self.length, self.width)

@property
def min_corner(self) -> Tuple[float, float]:
return (self.center[0] - self.size[0]/2, self.center[1] - self.size[1]/2)

@property
def max_corner(self) -> Tuple[float, float]:
return (self.center[0] + self.size[0]/2, self.center[1] + self.size[1]/2)

@property
def area(self) -> float:
return self.length * self.width

def collides_with(self, other: 'Rect') -> bool:
"""Checks if this rectangle collides with another rectangle."""
self_min_x, self_min_y = self.min_corner
self_max_x, self_max_y = self.max_corner

other_min_x, other_min_y = other.min_corner
other_max_x, other_max_y = other.max_corner

# Check for overlap
return (
(
(self_max_x < other_max_x and self_max_y < other_max_y) and
(self_max_x > other_min_x and self_max_y > other_min_y)
)
or
(
(other_max_x < self_max_x and other_max_y < self_max_y) and
(other_max_x > self_min_x and other_max_y > self_min_y)
)
)

def get_patch(self):
"""Returns a matplotlib Rectangle patch for visualization."""
x, y = self.min_corner
rect_width, rect_height = self.size
return patches.Rectangle(
(x, y),
rect_width,
rect_height,
edgecolor='red',
facecolor='lightgreen',
linewidth=1
)

Pallet Class


class Pallet:
def __init__(self, size: Tuple[float, float]):
self.size = size
self.length = max(size)
self.width = min(size)
self.rects: List[Rect] = []

def add_rect(self, rect: Rect) -> bool:
"""Attempts to add a rectangle to the pallet. Returns True if successful, False otherwise."""
if rect.area > self.length * self.width:
return False

# Check if the rectangle's corners are inside the pallet size
max_corner = rect.max_corner
min_corner = rect.min_corner
x_max, y_max = max_corner
x_min, y_min = min_corner
if (not (0 <= x_max <= self.length and 0 <= y_max <= self.width)) or (x_min< 0 or y_min<0):
print("Out of Pallet")
return False

for r in self.rects:
if r.collides_with(rect):
print("Collision")
return False

self.rects.append(rect)
return True

def fill_with_rects(self, rect_size: Tuple[float, float]):
rect_length = rect_size[0]
rect_width = rect_size[1]

rows_x = int(self.length // rect_length)
cols_y = int(self.width // rect_width)

for i in range(rows_x):
for j in range(cols_y):
cx = rect_length * (i)
cy = rect_width * (j)
corner = (cx, cy)
box = Rect(corner, (rect_length, rect_width))
box_added = pallet.add_rect(box)

def visualize(self):
fig, ax = plt.subplots(figsize=(10, 8))
ax.set_xlim(0, self.length)
ax.set_ylim(0, self.width)
ax.set_aspect('equal')
for box in self.rects:
box_patch = box.get_patch()
ax.add_patch(box_patch)
ax.set_xlabel("Pallet Length")
ax.set_ylabel("Pallet Width")

plt.grid(True)
plt.show()

Test


if __name__=="__main__":
# Filling a pallet
pallet = Pallet(size=(120, 100))
pallet.fill_with_rects((32, 17))
print("Number of rectangles in pallet:", len(pallet.rects))
pallet.visualize()

Current result:




Desired result:


Additional box column in the end as there still space to contain more rectangles without collision.

Continue reading...