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

Question

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

Мои координаты отправления-назначения иногда находятся в середине длинной прямой дороги. Однако кратчайший путь, рассчитанный 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. Добавить (5) расстояние до (3): получить
   • o1-> a-> c-> e1
   • o1-> a-> d-> e1
   • o1-> b-> c-> e1
   • o1-> b-> d-> e1
7. Выберите путь с наименьшим расстоянием

Answer 1

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

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

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

Смотри также: https://stackoverflow.com/a/55601732/7321942