2D-укладка и оптимизация ⇐ Python

[Anonymous]

У меня есть большой прямоугольник (поддон), и я хотел бы сложить коробки (прямоугольники меньшего размера), чтобы оптимизировать использование пространства. В настоящее время моя проблема в том, что я не уверен, как правильно повернуть последнюю строку/столбец, чтобы максимизировать использование доступного пространства.
Я пробовал:
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
)

Класс поддона

Код: Выделить всё

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 

Подробнее здесь: [url]https://stackoverflow.com/questions/79285844/2d-stacking-and-optimizing[/url]