Матричный способ декомпозиции многосвязного полигона на множество прямоугольных областей минимальной мощности

Аннотация

Рассматривается задача декомпозиции многосвязных ортогональных полигонов на множество прямоугольных областей минимальной мощности, к которой сводятся многие задачи оптимального размещения и покрытия в областях сложной структуры. В данной постановке размеры сторон боксов произвольные и их перекрытие запрещено. Задача является NP-трудной и для конструирования декомпозиции предлагается эвристический метод, основанный на матричном способе разделения полигона на прямоугольные области. Оптимальное решение предлагается искать на базе эволюционного алгоритма.