Поиск всех интервалов, которые перекрывают точку

Рассмотрим большой набор интервалов с плавающей запятой в одномерном пространстве, например

 [1.0, 2.5],                1.0 |---------------|2.5

 [1.5, 3.6],                      1.5|---------------------|3.6

 .....

Требуется найти все интервалы, содержащие данную точку. Например, для point = 1.2 алгоритм должен возвращать первый интервал, а если задан point = 2.0, он должен возвращать первые два интервала в приведенном выше примере.

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

После поиска я увидел, что эта проблема решается с помощью списка пропуска интервалов в контексте вычислительной геометрии. Мне было интересно, есть ли какая-нибудь простая и эффективная реализация на C ++.

РЕДАКТИРОВАТЬ: Чтобы быть более точным в проблеме, существует N интервалов, а для M точек следует определить, какие интервалы содержат каждую точку. N и M - большие числа, где M больше N.


c++ intervals computational-geometry skip-lists
person ramino    schedule 20.02.2015    source источник
comment
зачем пропускать списки? Списки пропуска используются как эффективная структура данных, отображающая ключ в значение; у вас просто проблема с поиском. Я думаю, вам нужно вместо этого дерево интервалов.   -  person Jason S    schedule 21.02.2015
comment
Я не вижу, где здесь нужны списки пропуска. Проверка того, находится ли точка в интервале, - это в основном 2 сравнения, поэтому, если у вас есть N интервалов, вам понадобится 2N сравнений. Это будет простой алгоритм O (N), и, поскольку ваш средний компьютер может выполнять несколько миллионов сравнений в секунду, вы должны получить свой ответ в мгновение ока.   -  person kuroi neko    schedule 21.02.2015
comment
kuroi: это быстрее, чем O (N), если у вас есть проиндексированные структуры данных   -  person Jason S    schedule 21.02.2015
comment
Конечно, но это было бы оправдано только для нескольких десятков миллионов матчей или больше, которые вполне могут и не понадобиться. А если интервалов много, затраты на построение специализированной структуры данных могут не окупить экономии при реальном поиске.   -  person kuroi neko    schedule 21.02.2015
comment
@SaniHuttunen: количество точек больше количества интервалов.   -  person ramino    schedule 21.02.2015
comment
@kuroineko: вы предлагаете поиск грубой силы, основанный на простоте операции сравнения, но, как я объяснил, поиск грубой силой медленный, так как его нужно повторять для большого количества точек (количество точек больше, чем интервалы) .   -  person ramino    schedule 21.02.2015
comment
Не совсем. Я посоветовал вам определить, что было больше - интервалы или точки. Теперь, когда вы отредактировали свой пост, предложенный ответ кажется возможным решением.   -  person kuroi neko    schedule 21.02.2015
comment
@ramino: 2 ›1 ... Нам все еще нужен номер на обоих ...   -  person Sani Singh Huttunen    schedule 21.02.2015
comment
@SaniHuttunen, сложно назвать цифру. Количество точек в моей задаче равно количеству элементов в 2D-сетке, используемой в FEM. Он может варьироваться в зависимости от разрешения сетки, но я бы сказал, что обычно не более 500k. Количество сегментов обычно не превышает 100 тыс.   -  person ramino    schedule 21.02.2015
comment
@ramino Тогда ваш вопрос задают не на том форуме ...   -  person Sani Singh Huttunen    schedule 21.02.2015
comment
@SaniHuttunen, нет, твоя настойчивость отвечать здесь неуместна.   -  person ramino    schedule 21.02.2015

Ответы (2)


arrow_upward
1
arrow_downward

Предложите использовать деревья диапазонов CGAL:

Википедия сообщает, что деревья интервалов (одномерные деревья диапазонов) могут «эффективно находить все интервалы, которые перекрываются с любыми заданный интервал или точка ».

person Jason S    schedule 20.02.2015
comment
Время построения находится в n log (n), поэтому, если у вас достаточно большое количество интервалов относительно количества точек для тестирования, это может стать хуже, чем грубая сила. Исходный вопрос не определяет требования достаточно точно, чтобы выбрать соответствующий алгоритм, ИМХО. - person kuroi neko; 21.02.2015
comment
@kuroineko ОП явно сказал, что он хочет чего-то другого, кроме поиска грубой силы, и что поиск будет выполняться много раз. - person jschultz410; 21.02.2015
comment
... на большом количестве интервалов. Как говорится в первом комментарии, все сводится к определению, какой из них больше других. - person kuroi neko; 21.02.2015
comment
@Jason S, как вы упомянули, интервальные деревья были первым вариантом, с которым я столкнулся. Я устал от interval_map и continuous_interval в бусте. Но он не дает мне списка интервалов, содержащих данную точку. Затем я наткнулся на это в CGAL: doc.cgal.org/latest/Interval_skip_list/ < / а>. Тем не менее я надеялся на простое и изящное решение, подобное github.com/ekg/intervaltree. - person ramino; 21.02.2015
comment
@Jason S: следуя вашему предложению, после переключения между списком пропуска интервалов и деревьями интервалов я нашел эту реализацию (stackoverflow.com/ a / 21327959/1911163), который находит все интервалы с плавающей запятой, содержащие данную точку, в коротком автономном коде. - person ramino; 24.02.2015

arrow_upward
1
arrow_downward

Если ваше распределение интервалов позволяет это, возможно, стоит рассмотреть подход с привязкой к сетке: выберите размер сетки s и создайте массив списков. Каждый k-й список перечисляет интервалы, которые перекрываются «ячейкой» [k.s, (k+1).s[.

Затем запрос сводится к поиску ячейки, содержащей точку запроса (в O(1)), и сообщению обо всех интервалах в списке, которые фактически содержат ее (в O(K)).

Время предварительной обработки и хранилище равны O(I.L+G), где I - количество интервалов, L - средняя длина интервала с точки зрения размера сетки, а G - общее количество ячеек сетки. s следует выбирать осторожно.

person Yves Daoust    schedule 25.02.2015