Можно ли эффективно подсчитать количество отрезков, которые перекрывают одну точку P на числовой линии?
Можно ли эффективно подсчитать количество отрезков, которые перекрывают одну точку P на номерной линии?
Все отрезки сидят на одной числовой линии (это 1-D мир, а не 3-D Мир).
Каждый отрезок имеет начальную координату X1 и конечная координата X2,
Пример:
Line segment A spans from X1==1 to X2==3
Line segment B spans from X1==2 to X2==4
Line segment C spans from X1==3 to X2==5
Line segment D spans from X1==1 to X2==4
----------------------------------------
Ex1: Line segments that overlap point P==2: A,B and D >>> overlap count==3.
Ex2: Line segments that overlap point P==7: None >>> overlap count==0.
Ex3: Line segments that overlap point P==3: A,B,C and D >>> overlap count==4.
Конечно, если есть только 4 линейных сегмента, то код прост. Однако, если существует огромная пространственная база данных из 400 миллионов отрезков, поиск будет очень медленным.
Существуют ли алгоритмы, которые могут эффективно выполнять поиск в этом списке сегментов линий по общему количеству перекрытий?
На что я смотрю до сих пор
- Статьи по алгоритмам поиска в пространственном индексе.
- Интервальные деревья (выглядит очень многообещающе).
- Сегмент деревьев (выглядит очень многообещающе).
- RTrees.
Решение
Если вы отсортируете список по начальному значению, а затем снова (по тому же начальному значению) по длине, вы получите корни эффективного алгоритма.
sort the list by starting value
for the same starting value, sort by length (longest first)
Затем, когда вам нужно количество отрезков, которые перекрывают данную точку P:
for a given value p
find the points in the list with starting value <= p (binary search - fast)
for each starting value, start with the longest length
if it spans the point of interest, increment counter
if not, go to the next smaller start value
keep going until you have reached the smallest starting value
Он не идеален, но намного лучше, чем поиск по 10M точкам (хотя первоначальная сортировка займет некоторое время, очевидно. Но вам нужно сделать это только один раз).
Другие решения
Сортируйте точки запроса и конечные точки интервалов все чаще в одном массиве; для каждой точки сохраняйте флаг, указывающий, является ли это началом интервала, концом интервала или запросом.
Инициализируйте счетчик на ноль и отсканируйте список. Старт увеличивает счетчик; конец уменьшает его; запрос знает количество перекрывающихся интервалов, читая счетчик.
Время (N + M). Журнал (N + M) или лучше, если можно использовать специальную сортировку.
Если вам не разрешено сортировать точки запроса, просто сортируйте конечные точки интервала. В одном линейном сканировании вы можете вычислить количество перекрытий сразу после каждой конечной точки.
Для данной точки запроса вы найдете соответствующую конечную точку с помощью дихотомического поиска, отсюда и количество совпадений.
M.Log (M) + N.Log (M) для M интервалов и N точек запроса.
Если вам не разрешено сортировать интервалы, просто сортируйте точки запроса.
Обработайте каждый интервал по очереди, найдите первую точку запроса, которую он перекрывает, с помощью дихотомического поиска, и увеличьте счетчик всех точек запроса, которые он перекрывает.
N.Log (N) + M.Log (N) + O, где O — общее количество совпадений интервалов / запросов.
Если вам вообще не разрешается сортировать, тщательно проверяйте каждый запрос по каждому интервалу, Н.М.
Посмотрите на интервальные деревья или сегментированные деревья, чтобы помочь решить проблему такого рода. Этот ответ Есть несколько хороших примеров того, как эти методы могут помочь вам.
Начните с понимания того, что вы не можете добиться большего успеха, чем O (N), поскольку вам нужно взглянуть на каждый из отрезков линии хотя бы один раз (где N = количество отрезков)
Давайте создадим массив Line_segments_at, в котором будет храниться количество отрезков, проходящих через каждую точку.
Сначала нам нужно инициализировать этот массив до 0.
Затем, когда мы смотрим на i-й отрезок, нам нужно сделать:
for(int j=x1[i];j<=x2[i];j++)
Line_segments_at[j]++;
Для каждой точки запроса k мы можем просто вернуть результат как Line_segments_at [k].