Вы можете найти путь на основе алгоритмов маршрутизации.Для этого есть несколько программных реализаций, таких как osmand.Затем в данных OSM не ищите узлы, представляющие город, а вместо этого ищите административные границы (полигоны) городов.На этом этапе с классическим алгоритмом геометрии вы можете вычислить список пересечений между маршрутом и административными границами.
Этот подход решает вашу проблему, но не вычисляет упрощенный граф как промежуточный этап.Таким образом, он требует больше компьютеров для каждого запроса.
Я боюсь, что с помощью графика, составленного из дорог, существует огромное количество различных путей между двумя точками, проходящими, возможно, через все города в данныхв разных заказах.Таким образом, вам нужен некоторый критерий оптимизации для выбора небольшого количества трасс (короткое расстояние, короткое время в пути, отсутствие платы за проезд, живописные дороги и т. Д.).Что приводит к необходимости некоторого алгоритма маршрутизации, что приводит к приведенному выше решению ...