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

Question

Я работаю над эффективным алгоритмом «скрытия» всех пар пересекающихся прямоугольников, расположенных в 2D, в наборе N прямоугольников (по оси выровнены).Все прямоугольники имеют одинаковую ширину и высоту.

Предположим, мой начальный набор прямоугольников, выложенных в 2D, равен R={r_1,r_2,...,r_n}, где r_i - все прямоугольники, r_i имеет логический атрибут visible.

Я хочу найти подмножество S в R так, чтобы для каждого r_i, r_j, принадлежащего S r_i,_r_j, не пересекалось.

Первое тривиальное решение - это грубое решение.максимальный подход с независимым множеством.Сначала я перебираю N(N-1)/2 прямоугольников (данный прямоугольник не пересекается с самим собой) и проверяю, пересекаются они или нет.Одновременно я также поместил все прямоугольники в наборе R как узлы графа G=(V,E).Края в этих графах представлены парами пересекающихся треугольников.

Множество непересекающихся прямоугольников - это тогда один максимальный независимый набор графа.

Я думаю, что это не самый быстрый подход, хотя и правильный.Например, я читал в некоторых обсуждениях, как предварительная сортировка списка прямоугольников по их координате x ускорит вычисление пересекающихся пар прямоугольников до O(nlog(n) ) (вместо грубой силы O(n^2).

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

Переформулировать проблему как проблему SAT также можетбыло бы интересно, хотя эта идея только что пришла мне в голову. Проблема в том, чтобы найти такую ​​перестановку атрибутов visible, чтобы ни один видимый прямоугольник не пересекался с другим.

Answer 1

Да, вы должны отсортировать прямоугольники по x.
Поскольку ваши прямоугольники находятся на одной оси x и имеют одинаковую высоту, после их сортировки вы сможете найти пересечение по линейному времени. Алгоритм, который вы ищете, называется строкой сканирования.

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

Answer 2

Не может быть только одного подмножества S. Например, рассмотрим следующую раскладку прямоугольников:

     +-----+
     |     |
     |  A  |
+----|    +-----+
|    +----|     |
|  D  |   |  B  |
|     |--- +    |
+-----+    |----+
     |  C  |
     |     |
     +-----+

Оба {A,C} и {B,D} являются действительными ответами. Итак, проблема несколько нечеткая. Вы ищете подмножество максимальной мощности?

Answer 3

Тестирование всех парных комбинаций - хорошая идея, но, будучи O (n ^ 2), это помогает найти способы ускорить его.

Разделите пространство на грубую сетку, похожую на шахматную доску, где каждая ячейка имеет список прямоугольников, которыми она владеет. Это означает, что центральная точка прямоугольника находится в ячейке. Это назначение прямоугольников ячейкам O (n).

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

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

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

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