Найти минимальное количество выравниваемых по краям перекрывающихся прямоугольников в непересекающемся вогнутом многоугольнике

Question

Я ищу алгоритм или алогирты, которые я могу использовать, чтобы взять непересекающийся вогнутый многоугольник и найти минимальный набор прямоугольников с выравниванием по краям, разделяющих многоугольник. Прямоугольники могут перекрываться (желательно минимально).

Я подумывал об отсечении уха, чтобы найти минимальные треугольники. Я мог бы построить прямоугольники из этих треугольников. Я думаю, что каждый треугольник может иметь набор прямоугольников. Затем я изучаю прямоугольники и объединяюсь с другими, коллинеарными прямоугольниками. Я не знаю, хороший это подход или нет.

Я думаю, что проблема звучит немного субъективно, но я все еще думаю, что есть хороший подход к решению этой проблемы с известными алгоритмами и небольшим количеством эвристик.

* РЕДАКТИРОВАТЬ: Больше с эвристикой, я могу ожидать, что выровненные по оси прямоугольники, между прочим, распространенным явлением.

** РЕДАКТИРОВАТЬ: Я также могу ожидать, что ноль выпуклых углов будет меньше, чем 90 градусов.

Answer 1

Справедливое предупреждение, у меня нет опыта в вычислительной геометрии, поэтому я просто придумываю вещи.Это был бы мой первоначальный подход к проблеме.

1. Выясните, является ли многоугольник выпуклым.Если так, покройте это одним прямоугольником, выровненным с краем.Чтобы сделать это, я бы сказал, просто попробуйте все ребра и посмотрите, какой из них дает прямоугольник с наименьшей площадью.Может быть лучший способ определить, какое ребро использовать, но опять же, в этом материале нет фона.

2. Если многоугольник вогнутый, давайте назовем ребро «вогнутым ребром», еслиэто не на выпуклой оболочке многоугольника.Найдите вогнутый край в многоугольнике и расширьте его, чтобы разрезать многоугольник на два или более новых, меньших многоугольника.Выполните повторение на каждом из дочерних многоугольников.

Если у многоугольника достаточно мало ребер, я думаю, что исчерпывающий поиск будет разумным, и просто выберите соответствие, которое наилучшим образом соответствует вашей эвристикепрямоугольники, наименьшее количество пространства вне охватываемого многоугольника, количество совпадений, некоторая функция предыдущих факторов и т. д.)