Как я могу найти все прямоугольники, смежные с определенным прямоугольником в данном списке прямоугольников?

Question

Учитывая прямоугольник R1 и список прямоугольников R2, R3, .... Как я могу найти все прямоугольники, которые связаны с основным прямоугольником R1.

Мне просто не нужен прямоугольниккоторые напрямую связаны с R1, но также и все, что косвенно связано с R1.Например, если R2 подключен к R1, а R3 подключен к R2.R3 считается связанным с R1.

Прямоугольники даны в форме (xmin, ymin, xmax, ymax).Все прямоугольники параллельны оси.Прямоугольники считаются связанными, когда они перекрывают друг друга или касаются друг друга.Когда они просто касаются в углу, они не считаются связанными.

Пример:

____________
_111________
_11122______
____22______
____22______
____333333__ 
____22______
__55___4444_
__55___4444_ 

В этом примере R1, R2, R3 связаны друг с другом.Поэтому мне нужно вернуть R1, R2, R3.

R4 и R5 не связаны.

Очевидным решением было бы сравнить каждый прямоугольник с друг другом O (n ^ 2).Но я думаю, что должны быть более быстрые решения.Я попытался использовать Реализовать алгоритм строчной развертки с интервальным деревом.Но это медленно.Мне нужно решение в O (n log n)

Answer 1

Составьте 2 списка, один из которых содержит объекты с координатами X и один с объектами, содержащими Y.

Объект будет состоять из (координата, номер прямоугольника и соответствует ли координата мин или макс).

Сортировка обоих списков O (nlogn) и обход любых.При обнаружении min-координаты добавьте прямоугольник в стек, при обнаружении max-координаты удалите прямоугольник.Если несколько прямоугольников добавляются вместе в стек, добавьте их в группу, при удалении прямоугольника группа будет соответствовать всем перекрывающимся прямоугольникам.Храните информацию о таких группах.Проделайте ту же процедуру, используя другой список.Обычные прямоугольники в группах, полученные из списков X и Y, будут перекрывающимися прямоугольниками.

Решение - O (nlogn).