2D堆叠优化：如何正确旋转末行/列矩形以最大化托盘空间利用率

2D堆叠优化：如何正确旋转末行/列矩形以最大化托盘空间利用率 #

我完全懂你现在的困扰——在托盘上规整堆叠盒子时，最后总会剩下一块空间，明明看起来能放下更多盒子，却因为没找到正确的旋转和放置方式浪费了。先看看你现有的实现，咱们一步步来优化它。

首先，你已经定义了Rect类来处理矩形的属性和碰撞检测，还有Pallet类来管理托盘和填充逻辑。不过先提个小问题：原Rect类里的collides_with方法逻辑有点问题，轴对齐矩形的碰撞检测应该用更简洁准确的判断，我先帮你修正这个，避免后续添加盒子时误判碰撞。

修正后的Rect类 #

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

        # 轴对齐矩形碰撞检测：判断两个矩形是否存在重叠
        # 不重叠的四种情况：一个在另一个的左、右、上、下方，取反就是重叠
        return not (
            self_max_x <= other_min_x
            or self_min_x >= other_max_x
            or self_max_y <= other_min_y
            or self_min_y >= other_max_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类 #

接下来重点优化fill_with_rects方法，让它在常规填充后自动检查剩余空间，尝试用旋转后的盒子（交换原尺寸的长和宽）来填补空隙。核心思路是：

• 先按原尺寸铺满托盘
• 计算水平和垂直方向的剩余空间
• 判断剩余空间是否能容纳旋转后的盒子，如果可以就批量添加

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

        # 检查矩形是否超出托盘边界
        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]
        # 旋转后的盒子尺寸：交换原长和宽
        rotated_size = (rect_width, rect_length)
        rotated_length = rotated_size[0]
        rotated_width = rotated_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
                box = Rect(corner=(cx, cy), size=(rect_length, rect_width))
                self.add_rect(box)

        # 第二步：检查水平剩余空间，尝试添加旋转后的盒子
        remaining_x = self.length - rows_x * rect_length
        if remaining_x >= rotated_length:
            # 计算垂直方向能放多少个旋转后的盒子
            rotated_cols = int(self.width // rotated_width)
            for j in range(rotated_cols):
                cx = rows_x * rect_length
                cy = rotated_width * j
                box = Rect(corner=(cx, cy), size=rotated_size)
                self.add_rect(box)

        # 第三步：检查垂直剩余空间，尝试添加旋转后的盒子（可选，根据需求开启）
        remaining_y = self.width - cols_y * rect_width
        if remaining_y >= rotated_length:
            # 计算水平方向能放多少个旋转后的盒子
            rotated_rows = int(self.length // rotated_width)
            for i in range(rotated_rows):
                cx = rotated_width * i
                cy = cols_y * rect_width
                box = Rect(corner=(cx, cy), size=rotated_size)
                self.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()

效果对比 #

• 当前原代码结果：托盘上按32x17的尺寸排列了3行（120//32=3）、5列（100//17=5），共15个盒子，右侧剩余120-3*32=24的空间，没法放下32长度的盒子，但足够放下旋转后的17长度的盒子。
• 优化后期望结果：在右侧剩余空间里多放一列旋转后的盒子（17x32），总共能放15+5=20个盒子，完美利用了剩余空间。

备注：内容来源于stack exchange，提问作者Bilal