Я пытаюсь проложить маршрут через множество пешеходных переходов. Я запрашиваю маршрут к службе Карт Google, чтобы получить маршрут по умолчанию, проблема с этим маршрутом состоит в том, что он не включает некоторые путевые точки (пешеходные переходы) (и повторный запрос маршрута с найденными пешеходными путями в качестве путевых точек не приводит к удовлетворительным результатам ). У меня есть географические координаты каждого пешеходного перехода на улицах, по которым запрашивается маршрут (для каждого из них у меня есть координаты обеих конечных точек).
Чтобы решить эту проблему, я аппроксимирую координаты широты и долготы значениями (x, y), что соответствует точности, которая мне нужна. Таким образом, маршрут определяется с помощью набора (x, y) координат.
Я могу разложить проблему на две подзадачи:
1) Поиск пешеходных переходов для достижения пункта назначения
2) Обновить существующий маршрут найденными пешеходными переходами
Для 1) я определил некоторые условия о том, когда прикреплять перекресток к данному сегменту маршрута.
а. Каждый конец пешеходного перехода должен находиться на расстоянии не более 10 м от текущего сегмента
б. Каждая конечная точка расположена «внутри» текущего сегмента (произведение точки некоторой конечной точки на начало сегмента и на конец сегмента должно быть отрицательным)
с. Я только прикрепляю один переход к данному сегменту маршрута (другие отклоняются). Это дает мне совершенно правильное подмножество пешеходных переходов, но я не уверен, является ли он оптимальным?
Для 2) Я понятия не имею, как эффективно объединить найденные пешеходные дорожки с существующим маршрутом (я начал смотреть на алгоритм A *)?
Ниже приведен пример маршрута из точки A в точку B (оранжевым цветом обозначены пешеходные переходы, черным цветом - входной маршрут, синим цветом - ожидаемый выходной маршрут).