АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ ДЕКОМПОЗИЦИИ МНОГОСВЯЗНОГО ОРТОГОНАЛЬНОГО ПОЛИГОНА

Аннотация

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