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

Question

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

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

Answer 1

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

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

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

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

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

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

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

Если V.isRightEdge ()

T.remove (V.rectangle.top)

T.remove (V.rectangle.bottom)

остальное

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

RS.add ()

T.add (V.rectangle.top)

T.add (V.rectangle.bottom)

5) возврат RS

---

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

- РЕДАКТИРОВАТЬ -

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

Answer 2

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

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

Answer 3

Подметание и сокращение - это метод, с помощью которого многие физические движки решают эту проблему.

Хорошее объяснение есть в заметках Дэвида Бараффа SIGGRAPH ,в разделе 7.2 Ограничительные рамки.