Каков наилучший способ реализовать 2D-интервал поиска в C++?

Question

Предположим, у меня есть двумерная сетка интервалов. Множество интервалов вдоль оси x и то же самое вдоль оси y. Теперь я должен определить, какие интервалы по оси x и оси y новый объект принадлежит двум. Предположим, что новый объект имеет числа, один - координату x, а другой - координату y. Определив интервал в x и y, в который входит объект, я хотел бы получить некоторые сохраненные данные.

Я подумал о чем-то вроде std::map<IntervalX, IntervalY, DataToStore> map или std::multimap<IntervalX, IntervalY, DataToStore> map. Любые предложения о том, как реализовать это, чтобы получить сохраненные данные для пары интервалов достаточно эффективно/быстро, а не в O(n²).

EDIT: Интервал определяется двумя значениями поплавка. Например: интервал вдоль оси x [0,5, 3,0]. Таким образом, 0,5 содержится и 3.0 не будет включаться в этот интервал, а в следующий интервал в положительном x-направлении.

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

Например: интервалы вдоль оси х, смотрящие на 0-10 с интервалом 0,5 и вдоль y -axis начиная с 2 до 15 с интервальным размером 1,0. Данная точка P (x = 0,7, y = 3,0), в какой интервал она падает? Это интервал 2 по оси x и интервал 2 по оси y. Теперь мне нужно получить данные, хранящиеся для этой пары интервалов.

В моем случае использования у меня будет около 10000 интервалов вдоль каждой оси, и определение интервала для объекта должно быть быстрым, так как я должен искать около 500 каждые 2 секунды (более или менее).

Answer 1

Теперь, когда мы знаем, что это черепичная плоскость: простым решением будет два отсортированных массива - один для интервалов оси X, один для интервалов оси Y. Затем выполните два запроса, используя std::lower_bound. Ожидаемая сложность log n для каждого поиска. Было бы трудно сделать лучше, и этот код был бы настолько прост и так сильно опирался на уже проверенные std::sort и std::lower_bound, вам нужно было только посмотреть на него снова, если тестирование производительности показало, что это узкое место.

И ... если вы получили эти 500 в партии каждые 2 секунды ... сортируйте их тоже (дважды: один раз на x, а затем на y), затем выполните поиск в отсортированном порядке, используя нижнюю границу каждого элемента, чтобы уменьшить количество предметов, которые были найдены для следующего элемента ... хотя, действительно, теперь мы говорим об оптимизации, которая должна быть проверена только после того, как вы определите, что у вас проблема с производительностью.

Что касается данных, связанных с каждой прямоугольной областью плоскости: Создайте 2-мерный массив указателей на эти данные, индексированные по x- и y-индексам, которые вы получили от std::lower_bound. Ожидаемая сложность доступа к двумерному массиву: постоянная.

Answer 2

Если интервалы не перекрываются (звучит так, как вы указываете, что точка отображается на один интервал на каждой оси), я бы просто сохранил их в отсортированном порядке max (Interval_n) < min (Interval_n + 1), позволяющий эффективный поиск в двоичном поиске.

Если они перекрывают друг друга, вы можете сортировать по мин, но это только поможет вам немного.