Ответ 1
Несмотря на название вашего вопроса, я думаю, вы действительно ищете минимальное рассечение на прямоугольники прямолинейного многоугольника. (Ссылки Джейсона - это минимальные обложки прямоугольников, что представляет собой совершенно другую проблему.)
Дэвид Эпштейн обсуждает эту проблему в разделе 3 своей обзорной статьи за 2010 год Графо-теоретические решения задач вычислительной геометрии, и он дает хорошее резюме в этом ответе на mathoverflow.net:
Идея состоит в том, чтобы найти максимальное число непересекающихся осевых параллельных диагоналей, которые имеют две вогнутые вершины в качестве конечных точек, разделенных по ним, а затем образуют еще один раскол для каждой оставшейся вогнутой вершины. Чтобы найти максимальное число непересекающихся осевых параллельных диагоналей, сформируем граф пересечений диагоналей; этот граф двудольный, поэтому его максимальный независимый набор можно найти в полиномиальном времени методами сопоставления графа.
Здесь мой блеск по этому замечательно краткому описанию, используя рисунок 2 из статьи Эппштейна. Предположим, что у нас есть прямолинейный многоугольник, возможно с отверстиями.
Когда многоугольник рассекается на прямоугольники, каждая из вогнутых вершин будет встречена краем вскрытия. Таким образом, мы получаем минимальное рассечение, если как можно большее количество этих краев выполняет двойную работу, т.е. Соединяют две вогнутые вершины.
Итак, давайте рисуем все оси-параллельные диагонали между двумя вогнутыми вершинами (диагональ полигона - это линия, соединяющая две несмежные вершины). Мы захотим использовать как можно больше из этих строк при вскрытии.
График пересечения набора сегментов линии имеет node для каждого сегмента линии, а ребро соединяет два узла, если линии пересекать. Здесь граф пересечений для оси-параллельных диагоналей:
Он bipartite с вертикальными диагоналями в одной части и горизонтальными диагоналями в другой части. Теперь мы хотим выбрать как можно больше диагоналей, если они не пересекаются. Это соответствует обнаружению максимального независимого набора в графе пересечений.
Поиск максимального независимого множества в общем графике является NP-полной проблемой, но в частном случае двудольного графа теорема Кёнига показывает, что это эквивалентно задаче нахождения максимального соответствия, которое может быть разрешено в полиномиальное время, например, алгоритмом Hopcroft-Karp. Здесь максимальное совпадение:
И вот соответствующая минимальная обложка вершин (красный) и максимальный независимый набор (зеленый):
Переведя это обратно в проблему диссекции, это означает, что мы можем использовать пять осевых параллельных диагоналей при вскрытии:
Наконец, сделайте вырез из каждого оставшегося вогнутого угла, чтобы завершить вскрытие:
