2D stacking and optimizing

Question

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.

Answer 1

To expand on my comment above: rectangle packing / the knapsack problem is a well-known problem with many heuristics implemented in python, so unless there are significant additional constraints, there is no need to reinvent the wheel here.

import numpy as np
import matplotlib.pyplot as plt

from rectpack import newPacker

pallet = (120, 100)
rectangle = (32, 17)

packer = newPacker()
packer.add_bin(*pallet)
theoretical_maximum = np.prod(pallet) // np.prod(rectangle)
for _ in range(theoretical_maximum):
    packer.add_rect(*rectangle)
packer.pack()
rects = [((x, y), w, h) for (_, x, y, w, h, _) in packer.rect_list()]

print("Theoretical maximum based on bin and rectangle areas:", theoretical_maximum)
print("Number of rectangles in pallet:", len(rects))
# Theoretical maximum based on bin and rectangle areas: 22
# Number of rectangles in pallet: 19

fig, ax = plt.subplots()
for rect in rects:
    ax.add_patch(plt.Rectangle(*rect, color=np.random.rand(3)))
ax.add_patch(plt.Rectangle((0, 0), pallet[0], pallet[1], color="black", fill=False))
ax.autoscale_view()
plt.show()