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

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. Загрузите все x-координатные перекрывающиеся прямоугольники в структуру данных и проверьте, пересекаются ли они (на основе y-координаты).

Answer 2

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

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

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

Answer 3

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

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

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

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

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

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