Расчет кратчайших путей от точек, начинающихся от середины края

У меня есть набор координат исходной и конечной точек, по которым я хочу рассчитать кратчайшие пути между ними.

Мои координаты пункта отправления и пункта назначения иногда располагаются посреди длинной прямой дороги. Однако кратчайший путь, вычисленный OSMnx / networkx, не будет учитывать этот путь от середины до ближайшего узла.

Есть ли в OSMnx или networkx готовая функция, которую я могу использовать для поиска кратчайшего пути, который начинается / заканчивается посреди дороги?

Если такой функции нет, я думаю об использовании следующих шагов.

  1. Получите ближайшие края отправления и назначения
  2. Получите узлы этих ближайших ребер: скажем, (a, b) для начала и (c, d) для пункта назначения
  3. Рассчитайте расстояние из 4 возможных комбинаций: a-> c, a-> d, b-> c, b-> d
  4. Спроецируйте исходную точку / пункт назначения на их ближайшие края: назовем их o1 и e1
  5. Вычислить расстояние o1-> a, o1-> b, e1-> c, e1-> d
  6. Add (5) distance to (3): to get
    • o1->a->c->e1
    • o1->a->d->e1
    • o1->b->c->e1
    • o1->b->d->e1
  7. Выберите путь с наименьшим расстоянием

osmnx networkx
person ShizukuF    schedule 09.04.2019    source источник
comment
Однако кратчайший путь, вычисленный OSMnx, отбрасывает путь от среднего края до ближайшего узла. - Если такое поведение не задокументировано в документации, этого достаточно, чтобы гарантировать сообщение об ошибке на их github . Сопровождающий кажется очень отзывчивым (1,6 тыс. Звезд, 210 закрытых выпусков, 4 открытых выпуска - что за легенда). В противном случае ваш обходной путь кажется надежным.   -  person Paul Brodersen    schedule 09.04.2019
comment
Спасибо за ваш комментарий. Сопровождающий уже ответил ниже. Я попробую с его предложением, иначе я выберу свой обходной путь.   -  person ShizukuF    schedule 10.04.2019

Ответы (1)


arrow_upward
1
arrow_downward

OSMnx создает объект графа networkx для маршрутизации / анализа. Как вы заметили, вычисление кратчайшего пути networkx принимает исходный и целевой узел, поэтому попытка вычислить кратчайший путь графа от средней точки края не сработает.

Вот пара вещей, которые вы можете попробовать:

  1. попробуйте установить simplify=False при создании графа, чтобы сохранить как можно больше узлов в середине улиц.
  2. если это не сработает, вы можете попытаться разделить ребра (с длиной больше некоторого порогового значения) на 50-метровые куски или что-то вроде того, чтобы дискретизировать их с большим количеством узлов.

См. Также: https://stackoverflow.com/a/55601732/7321942

person gboeing    schedule 09.04.2019
comment
Спасибо за ответ. Я уже установил simpleify = False, но, как я уже заметил, мое начало находится посередине прямой дороги. Я попробую с вашим предложением нет. 2. - person ShizukuF; 10.04.2019