Расчет оптимальной прямоугольной планировки для максимизации площади ⇐ Python

[Anonymous]

Я работаю над задачей оптимизации макета, где мне нужно разместить набор прямоугольников в заданной области, гарантируя, что прямоугольники не перекрываются, а макет максимально эффективно использует область. У клиента есть особые требования: прямоугольники должны быть размещены эффективно и выровнены по горизонтали, без разрезов внутри отдельных прямоугольников.
Вот ключевые детали:
Размеры области: 1480 (ширина) x 4000 (высота)
Размеры прямоугольника (ширина x высота):
[(190, 190), (190, 190), (240) , 240), (240, 240), (240, 240), (490, 240), (290, 690), (390, 990), (390, 990), (390, 490), (490, 490) ), (490, 490), (490, 490), (590, 490), (590, 590), (290, 690)]
Цель — расположить эти прямоугольники в заданной области, избегая перекрытий, размещая самые большие прямоугольники первыми и обеспечивая эффективную горизонтальную резку.
Я попробовал два подхода:
Размещение на основе строк: прямоугольники размещаются ряд за рядом, пока ширина не превысит ширину области, затем начинается новый ряд. Однако этот подход приводит к неоптимальному использованию, а иногда и к перекрытиям или пробелам.
Размещение на основе сетки: этот метод проверяет наличие свободного места в сетке и сначала размещает самые большие прямоугольники. Хотя это позволяет избежать перекрытий, я до сих пор не уверен, как обеспечить наиболее эффективное горизонтальное разрезание и максимально эффективно использовать пространство.
в целом код работает, но с размещением я не согласен. получаю результат, какой хочу. Вот код:

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

import numpy as np
import matplotlib.pyplot as plt

class LayoutOptimizer:
def __init__(self, area_width, area_height):
self.area_width = area_width
self.area_height = area_height
self.grid = np.zeros((area_height, area_width), dtype=int)  # Initialize grid
self.rectangles = []  # To store rectangle information
self.total_area = area_width * area_height  # Total available area

def can_place(self, x, y, width, height):
"""Check if a rectangle of width and height can be placed at (x, y)."""
if x + height > self.area_height or y + width >  self.area_width:
return False  # Out of bounds
if np.any(self.grid[x:x + height, y:y + width]):  # Check if space is occupied
return False
return True

def place_rectangle(self, rect_id, width, height):
"""Try to place the rectangle on the grid."""
# Prioritize horizontal placement from both left and right sides
for i in range(self.area_height - height + 1):
for j in range(self.area_width - width + 1):
if self.can_place(i, j, width, height):
# Place the rectangle
self.grid[i:i + height, j:j + width] = rect_id
self.rectangles.append((rect_id, width, height, i, j))
print(f"Rectangle_{rect_id}: {{'width': {width}, 'height': {height}, 'position': ({j}, {i})}}")
return (i, j)
for j in range(self.area_width - 1, width - 1, -1):
if self.can_place(i, j, width, height):
# Place the rectangle
self.grid[i:i + height, j - width + 1:j + 1] = rect_id
self.rectangles.append((rect_id, width, height, i, j - width + 1))
print(f"Rectangle_{rect_id}: {{'width': {width}, 'height': {height}, 'position': ({j - width + 1}, {i})}}")
return (i, j - width + 1)
return None

def optimize_layout(self, rectangles):
"""Place all rectangles on the grid."""
# Sort rectangles by width
sorted_rectangles = sorted(rectangles, key=lambda r: r[0], reverse=True)
for idx, (width, height) in enumerate(sorted_rectangles, 1):
if not self.place_rectangle(idx, width, height):
print(f"Rectangle {idx} could not be placed.")

def visualize_layout(self):
"""Generate a graphical visualization of the layout."""
plt.figure(figsize=(10, 10))
for rect_id, width, height, x, y in self.rectangles:
plt.gca().add_patch(plt.Rectangle((y, x), width, height, edgecolor='black', facecolor=np.random.rand(3,), fill=True))
plt.text(y + width / 2, x + height / 2, f'{rect_id}\n{width}x{height}', fontsize=10, ha='center', va='center')
# Highlight horizontal divisions
for i in range(1, self.area_height):
plt .axhline(i, color='gray', linestyle='--', linewidth=0.5)
plt.xlim(0, self.area_width)
plt.ylim(0, self.area_height)
plt.gca().set_aspect('equal', adjustable='box')
plt.gca().invert_yaxis()  # Invert y-axis to match grid orientation
plt.show()

def calculate_utilization(self):
"""Calculate and print the area utilization."""
used_area = sum(width * height for _, width, height, _, _ in self.rectangles)
utilization = (used_area / self.total_area) * 100
print(f"Utilization: {utilization:.2f}%")

# Example usage
if __name__ == "__main__":
# Area dimensions (as per client specifications)
area_width = 1480
area_height = 4000

# List of rectangle dimensions (width, height)
widths = [190, 190, 240, 240, 240, 490, 290, 390, 390, 390, 490, 490, 490, 590, 590, 290]
heights = [190, 190, 240, 240, 240, 240, 690, 990, 990 , 490, 490, 490, 490, 490, 590, 690]

rectangles = list(zip(widths, heights))  # Combine widths and heights into tuples

optimizer = LayoutOptimizer(area_width, area_height)

# Optimize the layout and place rectangles
optimizer.optimize_layout(rectangles)

# Visualize the optimized layout
optimizer.visualize_layout()

# Calculate and print the utilization percentage
optimizer.calculate_utilization()

Я хочу заполнить этот блок: мне нужен ожидаемый результат, но я получаю следующее: [это вывод моего кода][1]
[1]: https://i.sstatic.net/rdGovTkZ.png. пожалуйста, дайте мне знать, как я могу получить лучшие результаты!

Подробнее здесь: https://stackoverflow.com/questions/790 ... ximization