Подтвердить что ты не робот

Пересечение осевых прямоугольников

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

Это может быть немного сложно для собеседования, зависит от того, какая работа, Это геометрический алгоритм вычисления алгоритма,

Ответ можно найти здесь: http://www.cs.princeton.edu/~rs/AlgsDS07/17GeometricSearch.pdf

Ответ 2

Ниже приведено краткое описание алгоритма пересечения, представленного в ссылке DuduAlul.

Для решения требуется использование дерева поиска, способного выполнять запросы диапазона. Запрос диапазона запрашивает все элементы со значениями между K1 и K2 и должен быть операцией O (R + log N), где N - общее количество элементов дерева, а R - количество результатов.

В алгоритме используется подход развертки:

1) Сортировка всех левых и правых краев прямоугольника в соответствии с их значением X в список L.

2) Создайте новое дерево поиска пустого диапазона T, для Y-упорядочения прямоугольных вершин/дно

3) Создайте новый пустой набор результатов RS уникальных пар прямоугольников

4) Траверс L в порядке возрастания. Для всех V в L:

    Если visRightEdge()

      T.remove(V.rectangle.top)

      T.remove(V.rectangle.bottom)

    остальное

      Для всех U в T.getRange(V.rectangle.top, V.rectangle.bottom)

                RS <

      T.add(V.rectangle.top)

      T.add(V.rectangle.bottom)

5) вернуть RS

Сложность времени - O (R + N log N), где R - фактическое число пересечений.

- EDIT -

Я только выяснил, что решение не совсем правильно - тест пересечения в дереве T пропускает некоторые случаи. Дерево должно поддерживать Y-интервалы, а не Y, и в идеале это должно быть Дерево интервала.