Найти все ограничивающие прямоугольники, пересекающиеся с данной точкой (с использованием древовидной структуры)

Question

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

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

Лучше всего использовать какое-то двоичное дерево поиска, где я рекурсивно разбиваю оси x и y (например, срединный разрез)?

Answer 1

Я предлагаю вам использовать дерево сегментов.

Посмотрите на этих слайдах:

http://algo.kaust.edu.sa/Documents/cs372l07.pdf

вы особенно искали решения колющих запросов в более высоких измерениях (слайд 25)