Алгоритм слияния пространственно близких путей/отрезков линий

Ищу (название) геометрический алгоритм картографического обобщения карты улиц.

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

В качестве примера рассмотрим следующий график дорог/полос дорог, созданный с использованием данных OpenStreetMaps:

График дорожной сети, состоящий из трех горизонтальных линий, проходящих по изображению почти параллельно, и одной вертикальной линии, пересекающей их посередине

Как видите, две полосы дороги, идущие горизонтально, смоделированы как два отдельных пути. Для подробного просмотра это полезно, но для более масштабного просмотра мне нужно объединить два пути (полосы), чтобы отобразить только одну линию для дороги.

Какие устоявшиеся алгоритмы используются в рендерерах карт для достижения этой цели? Очевидно, Google Maps, OSM и т. д. делают это — как?


algorithm gis geometry graphics cartography
person anroesti    schedule 10.09.2019    source источник
comment
Вы можете начать поиск с сопоставления карт, это близко к вашей проблеме.   -  person Jean-Baptiste Yunès    schedule 10.09.2019
comment
Для подробных представлений это полезно, но для более уменьшенного представления мне нужно объединить два пути (дорожки) Для более уменьшенных представлений вы можете захотеть объединить два полосы, но вы могли просто игнорировать одну из них. Если они расположены достаточно близко, чтобы их можно было представить осевой линией в большом масштабе, это может удовлетворить ваши требования и упростить кодирование.   -  person High Performance Mark    schedule 13.10.2019
comment
Если вы ничего не делали дополнительно и просто наносили обе соседние линии, они естественным образом перекрывались бы при уменьшении масштаба и автоматически отображались бы как одна линия, естественно, в зависимости от масштаба. Но, похоже, ты этого не хочешь. Поэтому, пожалуйста, объясните, что вам в этом не нравится и чего вы хотите избежать, сделав что-то другое, чем позволяя линиям перекрываться. Каковы ваши цели для хорошего решения, которое было бы лучше, чем просто написать все строки и позволить им естественным образом перекрываться при уменьшении масштаба?   -  person Eric    schedule 15.10.2019
comment
@Eric Вы правы, в некоторых ситуациях может быть достаточно просто нарисовать все и позволить ему перекрываться (просто показывать, что оказывается сверху). Однако, если рендеринг карты более сложный (подумайте о том, чтобы метки на дорогах, но только один раз для каждой дороги, или повторяющиеся текстуры, или контуры, тени и т. д.), этот подход приводит к картам, которые просто не выглядят красиво.   -  person anroesti    schedule 16.10.2019

Ответы (3)


arrow_upward
3
arrow_downward

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

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

Более простым способом достижения является использование следующего алгоритма:

def reduce_segments (G : graph):
    for e in G.edges: 
        if not e.mark: 
            continue
        similar_edges = get_all_edge_with_frechet_distance_less_than_thr(G.edges, thr)
        for se in similar_edges:
            se.mark = True
    return {ee : ee in G.edges and ee.mark == False}
person Edward Aung    schedule 16.10.2019
comment
Спасибо за указатель на расстояние Фреше, я не знал об этом раньше. Однако, как я понимаю, это расстояние все равно было бы большим, если бы очень короткий отрезок прямой лежал очень близко к гораздо более длинному пути. Если это так, это будет проблемой, так как я хотел бы объединить короткий путь (т. е. короткую часть, где дорога имеет ширину в две полосы), которая находится рядом с гораздо более длинным путем (т. е. большую часть дороги шириной в одну полосу). Кроме того, будет ли ваш get_all_edge_with_frechet_distance_less_than_thr сравнивать ребра с целыми путями или ребра с ребрами? - person anroesti; 16.10.2019
comment
мы сравниваем траектории (каждая из которых состоит из нескольких ребер/сегментов) друг с другом. следует отметить, что едва ли существует единственный правильный ответ (в детерминистическом смысле). - person Edward Aung; 17.10.2019

arrow_upward
2
arrow_downward

Это не то, для чего это нужно, но как насчет того, чтобы сделать что-то вроде преобразования Хафа?

Чтобы найти достаточно близкие пути:

  1. Преобразуйте отрезки в плоское пространство (r, ),
  2. Пусть каждая точка голосует за ближайший доступный «бункер». Вы можете определить квантование бина на основе того, насколько вы хотите, чтобы ваш допуск для слияния двух путей был.
  3. Каждая точка в аккумуляторе также должна содержать ссылку на свой родительский путь и длину сегмента линии.
  4. Найдите корзины, которые содержат ровно два голоса, потому что нас интересует только слияние двух путей.
  5. Создайте накопительную матрицу nxn A, где n – количество путей, которые у вас есть, так что aij – это количество голосов для слияния iго и jth путь, это будет в основном разреженная матрица.
  6. Для каждого интересующего нас бина проголосуйте в матрице накопителя в ячейке, соответствующей двум его родительским путям.
  7. Если в матрице-аккумуляторе существует ячейка, имеющая достаточно большое количество голосов (т. е. достаточное количество отрезков в этих путях алгоритм считает допустимо похожими), то эти два пути могут быть объединены.

Чтобы объединить два пути:

  1. Преобразуйте обратно точки из выбранных бинов в декартово пространство, используйте длину (которая была сохранена в качестве эталона), наклон и положение для определения каждого сегмента линии, соответствующего каждому бину.
person Ahmed Elyamani    schedule 13.10.2019
comment
Мне это нравится, но предположение о желании объединить только два пути неверно (дороги могут иметь более двух полос). Конечно, ваш подход можно было бы расширить, используя тензоры, чтобы приспособиться к этому, но я мог бы просто пропустить процесс голосования и просто объединить все сегменты линий, которые попадают в один и тот же бин (вместо путей) преобразования Хафа, и в end удалить одинаковые/перекрывающиеся пути. - person anroesti; 16.10.2019
comment
Еще одна проблема, которую я вижу в этом предложении, заключается в том, что два сегмента линии параллельны, и на одном и том же расстоянии от начала координат этот алгоритм будет считаться объединенным (окажутся в одном и том же бункере в пространстве Хафа). Но поскольку это сегменты линии, они не обязательно должны быть близкими (т.е. два сегмента на одной диагональной линии, но один находится в крайнем верхнем левом углу, а другой - в крайнем нижнем правом). Как бы вы справились с этим? - person anroesti; 16.10.2019

arrow_upward
0
arrow_downward

Чтобы найти расстояние между путем A и путем B:

  • Дана точка X на пути A
  • Определите линию Y под углом 90 градусов к линии между точкой X и следующей точкой.
  • Вычислить пересечение линии Y с одной из линий пути B
  • Вычислите расстояние между точкой X и точкой пересечения, и вы получите пространство между путями в точке X.

Чтобы создать путь между двумя путями:

  • Описанный выше метод поможет найти расстояния.
  • Новый путь будет средним расстоянием между двумя путями.
person google dev    schedule 13.10.2019