Нахождение всех интервалов, которые перекрывают точку
Рассмотрим большой набор интервалов с плавающей точкой в 1-мерном
например
[1.0, 2.5], 1.0 |---------------|2.5
[1.5, 3.6], 1.5|---------------------|3.6
.....
Желательно найти все интервалы, которые содержат данную точку. Например, если задана точка = 1.2, алгоритм должен вернуть первый интервал, а если задана точка = 2.0, он должен вернуть первые два интервала в приведенном выше примере.
В проблеме, с которой я сталкиваюсь, эту операцию нужно повторять большое количество раз для большого количества интервалов. Поэтому поиск методом перебора нежелателен, а производительность является важным фактором.
После поиска я увидел, что эта проблема решается с помощью списка пропусков интервалов в контексте вычислительной геометрии. Мне было интересно, есть ли какая-либо простая, эффективная реализация C ++.
РЕДАКТИРОВАТЬ: Чтобы быть более точным о проблеме, есть N интервалов, и для M точек, должно быть определено, какие интервалы содержат каждую точку. N и M большие числа, где М больше, чем N.
Решение
Предложить использование Деревья диапазона CGAL:
Википедия говорит интервальные деревья (Одномерные деревья диапазонов) могут «эффективно находить все интервалы, которые перекрываются с любым заданным интервалом или точкой».
Другие решения
Если ваше распределение интервалов позволяет это сделать, возможно, стоит рассмотреть подход с использованием сетки: выберите размер сетки s и создать массив списков. каждый k-ый список перечисляет интервалы, которые перекрываются с «ячейкой» [k.s, (k+1).s[,
Тогда запрос сводится к поиску ячейки, содержащей точку запроса (в O(1)) и сообщать обо всех интервалах в списке, которые его содержат (в O(K)).
Время предварительной обработки и хранения O(I.L+G) где I количество интервалов и L средняя длина интервала с точки зрения размера сетки и G общее количество ячеек сетки. s должен быть выбран тщательно.