Мне нужен алгоритм для слияния / объединения ряда сегментов в ряд полилиний

У меня есть ряд сегментов, которые не более чем пересекаются друг с другом на концах. Я хочу объединить эти сегменты в полилинии.

Есть ли алгоритм, который делает это в O(N_segments) без использования дополнительного хранилища (например, без необходимости строить дерево или какую-либо другую пространственную структуру данных для точек сегмента и работать над этим)?

Количество сегментов у меня невелико, O (10). Таким образом, размещение их в динамической структуре данных, такой как хеш-таблица или карта (красно-черное дерево), вероятно, будет дороже, чем цикл O(N^2) в конце, если я не помещу эту структуру данных в стек и не буду избегать выделения памяти. (Используемые мною полилинии реализованы с использованием small_vector, что позволяет избежать выделения, пока количество точек достаточно мало.

В настоящее время я придумал это:

polylines = []
// 1. Append each segment to a range of polylines, merging when possible:
for each segment in segments:
    for each polyline in polylines:
       merge_result = merge(segment, polyline)
       if (not merge_result) continue
       polyline = merge_result
       goto done

    // either polylines empty or no merge possible
    polylines.append(segment)

    done:
      continue

// 2. Try to merge the polylines among themselves until no more merges are possible
// Pure brute force, quadratic
done = false
while not done:
    for p1 in polylines: 
        for p2 in polylines[p1..end]:
            merge_result = merge(p1, p2)
            if not merge: continue
            p1 = merge_result
            polylines.remove(p2)
            done = false
            goto restart
    restart: continue

Но второй цикл явно квадратичный, поэтому мне интересно, есть ли лучший алгоритм для слияния / соединения / объединения последовательности сегментов между собой.


algorithm geometry spatial polyline segment
person gnzlbg    schedule 02.09.2016    source источник
comment
Почему следует избегать создания структуры данных? Я бы создал карту конечных точек сегментов, чтобы определить, разделяет ли конечная точка более одного сегмента примерно за время O (n).   -  person MrSmith42    schedule 02.09.2016
comment
В соответствующем сообщении предлагается вычислить хэши конечных точек для ускорения Поиск.   -  person Axel Kemper    schedule 02.09.2016
comment
@ MrSmith42 Я имею дело с порядком сегментов O (10), поэтому, если я не создам карту в стеке, стоимость создания динамической карты, вероятно, превзойдет стоимость последнего цикла O (N ^ 2). Вот почему меня интересовал лучший алгоритм, позволяющий сделать это без дополнительной структуры данных. Я попробую с картой в стеке и протестирую ее. Спасибо за предложение.   -  person gnzlbg    schedule 02.09.2016

Ответы (2)


arrow_upward
2
arrow_downward

Я серьезно сомневаюсь, что может существовать метод O (n).

Вот метод O (n log (n)), который обнаруживает конечности сегмента, которые имеют точно такие же координаты. Он использует «структуру данных», но очень простую (просто вектор):

1) создать вектор элементов (x, y, i) всех конечностей всех сегментов, где x, y обозначают координаты конечности, а i - индекс конечности (например, 2 * индекс сегмента и 2 * индекс сегмента + 1 для двух концов сегмента).

2) отсортировать вектор в лексикографическом порядке на (x, y)

3) просканируйте вектор, точки с точно такими же координатами смежны в векторе (и с индексом i вы можете восстановить конечности сегмента, которым они соответствуют)

Я использую этот алгоритм для слияния вершин в 3D-сетках, он простой и очень быстрый, намного быстрее, чем при использовании хэш-карты или набора (обнаруживает дубликаты в наборах точек размером до 10 миллионов точек за секунды).

person BrunoLevy    schedule 18.09.2016

arrow_upward
0
arrow_downward

Ваша проблема эквивалентна поиску дубликатов в массиве. Эта проблема не может быть решена за время O (N) и 0 (1) пространство в общем случае. Вы можете использовать сортировку, как предлагается, чтобы иметь сложность O (N log N), или использовать структуру данных. Для поиска дубликатов в общем случае вы можете посмотреть это обсуждение. Для особого случая, когда массив размера n содержит элементы в диапазоне 0, ... n-1, существует решение O (N) по времени и 0 (1) по пространству, которое использует о том, что элементы могут использоваться в качестве индексов, см. this пост.

Однако, если вы все равно говорите только о 10 элементах, даже квадратичный цикл не повредит. Если время действительно критично, вам в любом случае следует протестировать оба метода, а не гадать. Проблема в том, что никто не может сказать вам, какой из них будет быстрее на вашей машине всего для 10 элементов, поскольку чистые классы сложности становятся важными только для большого N. Для малых N алгоритм O (N ^ 2) может намного быстрее, чем алгоритм O (N log n). Кроме того, помимо распределения памяти, эффективности кеширования и всего остального, что необходимо. Итак, мой совет: либо тестируйте, если вас действительно волнует скорость, либо не беспокойтесь, если вас это не устраивает.

person Noidea    schedule 18.09.2016