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

Question

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

У меня есть еще один прямоугольник A с целочисленными координатами, координаты которого движутся (но вы можете предположить, что его размер постоянен)

Как наиболее эффективно определить, какие прямоугольники пересекаются (или внутри) A? Я не могу просто перебрать свой набор, так как он слишком большой. Спасибо

edit: все прямоугольники параллельны оси

Answer 1

Вычисляя площадь каждого прямоугольника и проверяя длину L, высоту H и площадь прямоугольников, превышает или нет длину и высоту и площадь прямоугольника A

Answer 2

Пусть ваш набор прямоугольников будет (Xi1, Yi1, Xi2, Yi2), где я варьируется от 0 до N.

Прямоугольник A и B НЕ могут пересекаться, если Ax1> Bx2 || Ay1 Ax2 || By1

Создание дерева, которое оптимизировано для диапазона / интервала (например: дерево сегментов или дерево интервалов) Смотри http://w3.jouy.inra.fr/unites/miaj/public/vigneron/cs4235/l5cs4235.pdf

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