2D堆叠和优化

Question

我有大矩形（托盘），并且想以优化空间使用的方式堆叠盒子（较小的矩形），目前我的问题是我不确定如何正确旋转最后一行/列以最大化利用率可用空间。

我已经尝试过：

矩形类

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
        )

托盘类

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()

测试

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()

目前结果：

想要的结果：

最后有额外的框列，因为仍有空间容纳更多矩形而不会发生碰撞。

Answer 1

扩展我上面的评论：矩形包装/背包问题是一个众所周知的问题，许多启发式方法都是在Python中实现的，所以除非有明显的额外约束，否则不需要在这里重新发明轮子。

import numpy as np
import matplotlib.pyplot as plt

from rectpack import newPacker

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

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

print("Number of rectangles in pallet:", len(rects))
# 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()