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

Question

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

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

При таком наборе из трех прямоугольников правильное решение будет заканчиваться двумя прямоугольниками, например так:

Однако в этом случае мой алгоритм начинается с обработки синего прямоугольника. Это расширяется вниз и разбивает желтый прямоугольник (правильно). Но затем, когда обрабатывается остаток от желтого прямоугольника, а не расширяется вниз, он сначала расширяется вправо и отбирает часть, которая была ранее отделена. Затем обрабатывается последний прямоугольник, и он не может расширяться вправо или вниз, поэтому остается исходный набор прямоугольников. Я мог бы настроить алгоритм, чтобы сначала развернуть вниз, а затем вправо. Это исправит этот случай, но это вызовет ту же проблему в аналогичном сценарии, который был перевернут.

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

Answer 1

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

Дэвид Эппштейн обсуждает эту проблему в разделе 3 своей обзорной статьи 2010 года " Теоретические графы решения задач вычислительной геометрии", и он дает хорошее резюме в этом ответе на mathoverflow.net:

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

Вот мой глянец на этом замечательном кратком описании, используя рисунок 2 из статьи Эппштейна. Предположим, у нас есть прямолинейный многоугольник, возможно, с отверстиями.

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

Итак, давайте нарисуем параллельные по оси диагонали между двумя вогнутыми вершинами, которые полностью содержатся в многоугольнике. ("Ось параллельная" здесь означает "горизонтальная или вертикальная", а диагональ многоугольника - это линия, соединяющая две несмежные вершины.) Мы хотим использовать как можно больше этих линий при расчленении, если они не совпадают. не пересекаются.

(Если нет диагональных осей-параллелей, рассечение является тривиальным - просто сделайте разрез из каждой вогнутой вершины. Или если нет пересечений между диагональными осями-параллелями, тогда мы используем их все, плюс разрез из каждой оставшейся вогнутой вершины Иначе читай дальше.)

Граф пересечений набора отрезков имеет узел для каждого отрезка, а ребро соединяет два узла, если линии пересекаются. Вот график пересечения диагональных осей:

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

Нахождение максимального независимого множества в общем графе является NP-трудной задачей, но в частном случае двудольного графа теорема Кенига показывает, что она эквивалентна задаче нахождения максимального соответствия, которая может быть решена за полиномиальное время для пример по алгоритму Хопкрофта – Карпа. У данного графа может быть несколько максимальных совпадений, но подойдет любой из них, так как все они имеют одинаковый размер. В этом примере все максимальные соответствия имеют три пары вершин, например {(2, 4), (6, 3), (7, 8)}:

(Другие максимальные соответствия на этом графике включают {(1, 3), (2, 5), (7, 8)}; {(2, 4), (3, 6), (5, 7)}; и {(1, 3), (2, 4), (7, 8)}.)

Чтобы получить максимальное совпадение с соответствующим минимальным покрытием вершин, примените доказательство теоремы Кенига. В приведенном выше сопоставлении левый набор равен L = {1, 2, 6, 7}, правый набор равен R = {3, 4, 5, 8}, а набор несопоставленных вершин в L равен U = { 1}. Существует только один чередующийся путь, начинающийся в U, а именно 1–3–6, поэтому набор вершин в чередующихся путях равен Z = {1, 3, 6}, и, таким образом, минимальное покрытие вершин равно K = (L \ Z) ∪ (R ∩ Z) = {2, 3, 7}, показано красным цветом ниже, с максимальным независимым набором зеленого цвета:

Переводя это обратно в проблему рассечения, это означает, что мы можем использовать пять диагонально-параллельных диагоналей в рассечении:

Наконец, сделайте вырез из каждой оставшейся вогнутой вершины, чтобы завершить рассечение:

Answer 2

Вот некоторые научные статьи, обсуждающие решения этой проблемы;

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

Оптимальные прямоугольные покрытия для выпуклых прямолинейных многоугольников (это один из вариантов вашей конкретной задачи)

Вы также можете попробовать здесь список литературы по этому вопросу.

Answer 3

Сегодня я нашел решение этой проблемы O(N^5), и я поделюсь им здесь.

Для первого шага вам нужно найти способ получить сумму любого прямоугольника в матрице со сложностью O(1). Сделать это довольно просто.

Теперь для второго шага вам нужно знать динамическое программирование. Идея состоит в том, чтобы сохранить прямоугольник и разбить его на более мелкие части. Если прямоугольник пуст, вы можете вернуть 0. А если он заполнен, вернуть 1.

Есть N^4 состояний для хранения прямоугольника плюс сложность O(N) для каждого состояния ... Таким образом, вы получите алгоритм O(N^5).

Вот мой код. Думаю поможет.

Ввод простой. N, M (размер матрицы) После этого в следующих N строках будут единицы и нули. Пример:

      4 9
010000010
111010111
101111101
000101000

      #include <bits/stdc++.h>
#define MAX 51
int tab[MAX][MAX];
int N,M;
int sumed[MAX][MAX];
int t(int x,int y) {
    if(x<0||y<0)return 0;
    return sumed[x][y];
}
int subrec(int x1,int y1,int x2,int y2) {
    return t(x2,y2)-t(x2,y1-1)-t(x1-1,y2)+t(x1-1,y1-1);
}
int resp[MAX][MAX][MAX][MAX];
bool exist[MAX][MAX][MAX][MAX];
int dp(int x1,int y1,int x2,int y2) {
    if(exist[x1][y1][x2][y2])return resp[x1][y1][x2][y2];
    exist[x1][y1][x2][y2]=true;
    int soma = subrec(x1,y1,x2,y2);
    int area = (x2-x1+1)*(y2-y1+1);
    if(soma==area){return resp[x1][y1][x2][y2]=1;}
    if(!soma) {return 0;}
    int best = 1000;
    for(int i = x1;i!=x2;++i) {
        best = std::min(best,dp(x1,y1,i,y2)+dp(i+1,y1,x2,y2));
    }
    for(int i = y1;i!=y2;++i) {
        best = std::min(best,dp(x1,y1,x2,i)+dp(x1,i+1,x2,y2));
    }
    return resp[x1][y1][x2][y2]=best;
}
int main()
{
    std::cin >> N >> M;
    for(int i = 0; i != N;++i) {
        std::string s;
        std::cin >> s;
        for(int j = 0; j != M;++j) {
            if(s[j]=='1')tab[i][j]++;
        }
    }
    for(int i = 0; i != N;++i) {
        int val = 0;
        for(int j = 0; j != M;++j) {
            val += tab[i][j];
            sumed[i][j]=val;
            if(i)sumed[i][j]+=sumed[i-1][j];
        }
    }
    std::cout << dp(0,0,N-1,M-1) << std::endl;
}

Answer 4

Спасибо за эту публикацию, которая мне действительно помогла.

По тезисам 2 вещи:

1 Я действительно супид. 2 Я плохой программист.

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

Хорошо, но теперь мне очень трудно вычислить список прямоугольников с этим.

Подлый алгоритм разговора или конечно.

Заранее спасибо.

Жан-Ив