Как определять пересечения фигур на плоскости?

Делаю проект для оптимизации раскроя на метал. листах: через генетический алгоритм мы создаем популяции, и, в конечном итоге, должны находить расположение фигур с минимальной площадью пустого пространства. Но при реализации фигуры накладываются друг на друга. Как найти их размеры (это может быть любая фигура, сложный многоугольник и прочее)? Мне нужно определять, не перекрывает ли одна фигура другую, а если перекрывает - удалять фигуру или не добавлять популяцию. Подскажите как это можно реализовать на python?

пробовал находить размер фигур, но таки не понял, как реализовать

по станку пока нет информации, на вход нам должно будет подаваться множество многоугольных фигур и нужно максимальное количество вместить на лист, фигуры могут быть разного размера, в примере выше я просто использовал как пример поэтому там квадрат FIGURES.append((300,300)), по идеи мы для начала можем генерировать любые многоугольники и они ВО-ПЕРВЫХ НЕ ДОЛЖНЫ ВЫХОДИТЬ ЗА КООРДИНАТЫ ПЛОСКОСТИ КОТОРЫЕ МЫ УКАЗАЛИ, ВО-ВТОРЫХ ФИГУРЫ НЕ ДОЛЖНЫ НАКЛАДЫВАТЬСЯ ДРУГ НА ДРУГА, ЕСЛИ НАКЛАДЫВАЮТСЯ НАДО УДАЛЯТЬ ЭТУ ФИГУРУ Заранее спасибо за обратную связь!)

import random
import numpy as np
import matplotlib.pyplot as plt
from shapely.geometry import Polygon
from shapely.geometry import MultiPolygon
import ezdxf

# Функция для создания случайного многоугольника
def create_random_polygon(center_x, center_y, radius, num_vertices):
    angles = sorted([random.uniform(0, 2 * np.pi) for _ in range(num_vertices)])
    vertices = [
        (
            center_x + radius * np.cos(angle),
            center_y + radius * np.sin(angle)
        )
        for angle in angles
    ]
    return Polygon(vertices)

# Генерация многоугольников
def generate_polygons(grid_size, polygon_count, radius):
    polygons = []
    for _ in range(polygon_count):
        center_x = random.uniform(0, grid_size)
        center_y = random.uniform(0, grid_size)
        num_vertices = random.randint(3, 8)  # Случайное количество вершин
        poly = create_random_polygon(center_x, center_y, radius, num_vertices)
        
        # Проверка, что все точки многоугольника находятся в пределах сетки
        if all(0 <= x <= grid_size and 0 <= y <= grid_size for x, y in poly.exterior.coords):
            polygons.append(poly)
    return polygons

# Отображение многоугольников и их пересечений
def plot_polygons(polygons):
    fig, ax = plt.subplots(figsize=(10, 10))
    ax.set_aspect('equal')

    for poly in polygons:
        x, y = poly.exterior.xy
        ax.fill(x, y, alpha=0.5, edgecolor='black', linewidth=1)

    plt.xlim(0, grid_size)
    plt.ylim(0, grid_size)
    plt.show()

# Сохранение в DXF-файл
def save_to_dxf(polygons, filename="output.dxf"):
    doc = ezdxf.new()
    msp = doc.modelspace()

    for poly in polygons:
        points = list(poly.exterior.coords)
        msp.add_lwpolyline(points, close=True)

    doc.saveas(filename)
    print(f"Файл сохранен: {filename}")

# Функция для скрещивания двух родителей
def crossover(parent1, parent2):
    # Проверка, что у родителей есть больше одного многоугольника
    if len(parent1) < 2 or len(parent2) < 2:
        return parent1  # Если у родителя меньше 2 многоугольников, возвращаем его как есть
    
    split_point = random.randint(1, len(parent1) - 1)  # Выбираем точку раздела
    child = parent1[:split_point] + parent2[split_point:]  # Склеиваем родителей в ребенка
    return child

# Функция для мутации (удаление или добавление многоугольников)
def mutate(individual, grid_size, radius, mutation_rate=0.1):
    if random.random() < mutation_rate:
        if random.random() < 0.5 and len(individual) > 1:
            individual.pop(random.randint(0, len(individual) - 1))  # Удаление случайного многоугольника
        else:
            # Добавление нового случайного многоугольника
            center_x = random.uniform(0, grid_size)
            center_y = random.uniform(0, grid_size)
            num_vertices = random.randint(3, 8)
            new_polygon = create_random_polygon(center_x, center_y, radius, num_vertices)
            
            if all(0 <= x <= grid_size and 0 <= y <= grid_size for x, y in new_polygon.exterior.coords):
                individual.append(new_polygon)
    return individual

# Оценка качества популяции (количество непересекающихся многоугольников)
def fitness(individual):
    non_intersecting_count = 0
    for i in range(len(individual)):
        intersecting = False
        for j in range(i + 1, len(individual)):
            if not individual[i].intersection(individual[j]).is_empty:
                intersecting = True
                break
        if not intersecting:
            non_intersecting_count += 1
    return non_intersecting_count

# Генетический алгоритм
def genetic_algorithm(pop_size, grid_size, radius, polygon_count, generations, top_n):
    population = [generate_polygons(grid_size, polygon_count, radius) for _ in range(pop_size)]
    best_individual = None
    best_fitness = 0

    for generation in range(generations):
        print(f"Поколение {generation + 1}")
        
        # Оценка популяции
        population.sort(key=lambda x: fitness(x), reverse=True)
        
        # Обновляем лучшее решение
        if fitness(population[0]) > best_fitness:
            best_fitness = fitness(population[0])
            best_individual = population[0]
        
        # Выбираем лучших и создаем новое поколение
        new_population = population[:top_n]  # Топ-n лучших
        while len(new_population) < pop_size:
            parent1, parent2 = random.choices(new_population, k=2)
            child = crossover(parent1, parent2)
            child = mutate(child, grid_size, radius)
            new_population.append(child)
        
        population = new_population
    
    return best_individual

# Параметры
grid_size = 100  # Размер области
polygon_count = 5  # Количество многоугольников в каждой особи
radius = 20  # Радиус для генерации многоугольников
pop_size = 10  # Размер популяции
generations = 20  # Количество поколений
top_n = 5  # Топ-n лучших особей для скрещивания

# Генерация и отображение лучшего решения
best_individual = genetic_algorithm(pop_size, grid_size, radius, polygon_count, generations, top_n)
plot_polygons(best_individual)

# Сохранение в DXF
save_to_dxf(best_individual, "best_individual.dxf")