Построение маршрутов..., люди регулярно этим пользуются, особенно для автомобильных маршрутов, в навигаторах.
Решений, для построения маршрута тоже немало, в том числе существует GraphHopper, который умеет строить маршруты, и для автомобилей, и для пешеходов, и даже для пешего туризма, - подойдёт, наверно, в 99% случаев.
Далее речь пойдёт том, что делать в остальных ситуациях, точнее о моём опыте использования GraphHopper, когда существующее решение не подходило. Требовалось учитывать дополнительные ограничения: строить пешеходные маршруты для людей с ограниченными возможностями. Не будет ни каких значимых особенностей реализации именно этой задачи. Обобщённо.
Будет описано, как создать на основе библиотеки GraphHopper свой вебсервис, который, по координатам начала и окончания пути, вернёт массив координат маршрута.
Пример приложения, со всеми необходимыми для запуска заглушками, можно найти в моём репозитории на GitHub.
GraphHopper - механизм маршрутизации, написанный на Java. Выпущен под лицензией Apache, и может быть встроен в продукты с закрытым исходным кодом.
Статьи подобного толка на хабре встречаются, например, Гуляем по городу с умом, но в ней не приводится деталей реализации, к сожалению, и ну и всё.
Также в публикации Новости из мира OpenStreetMap 512 (05.05.2020-11.05.2020), была новость следующего содержания:
Разработчики GraphHopper ждут наших с вами комментариев, так как они ввели новую функцию, позволяющую даже людям без знания программирования или Java изменять модель построения маршрутов.
Наверно, эта новая функция покроет ещё 0.99% возможных ситуаций, вероятно подойдёт и для Вашей задачи, знания Java не потребуются, и вообще проблем не возникнет. Я расскажу, а своём опыте создания правил построения маршрутов, когда этой функции не было, а до её создания оставалось 2 года.
Понадобятся знания Java.
Считаю, что публикация всё ещё актуальна, ибо:
-
ничто не может сравниться по гибкости и податливости с возможностью изменения исходного кода
-
GraphHopper работает на данных OSM, а Вам могут потребоваться правила, не предусмотренные OSM. Например, вы можете строить маршруты по закрытым дорогам, их закрытость очевидна из OSM. Вот только надо учесть цветовую дифференциации штанов. А ездить по зимникам в летнее время года я крайне не рекомендую, здесь может потребоваться проверка даты.
Решение
В статье используется версия библиотеки GraphHopper 0.10.0, актуальная на момент создания приложения.
Для начала подключаем библиотеку.
Maven:
<dependency><groupId>com.graphhopper</groupId><artifactId>graphhopper-reader-osm</artifactId><version>0.10.0</version></dependency>
Исходный код GraphHopper, в том числе этой библиотеки, выложен
на github. Так же там есть некоторая документация, например
How to create new routing
profile aka a new FlagEncoder? которая, как бы намекает, что
нам необходимо создавать совой FlagEncoder
. Уже
существующие FlagEncoder
, находятся в пакете
com.graphhopper.routing.util
, нас особо интересуют
FootFlagEncoder
, т.к. он занимается построением именно
пешеходных маршрутов, и AbstractFlagEncoder
, как его
родительский класс.
Отправной точкой для постижения GraphHopper (актуальной версии) может стать вот эта страница GraphHopper Documentation и пример RoutingExample.java.
Создаём FlagEncoder
Имеет смысл, либо унаследовать свой FlagEncoder
от
AbstractFlagEncoder
, частично повторив
FootFlagEncoder
и внеся изменения куда следует, либо
сразу от FootFlagEncoder
, что избавит от дублирования
кода. Мне больше подходит наследование от
AbstractFlagEncoder
и копирование кода
FootFlagEncoder
, ибо требуется доступ к полям, которые
в FootFlagEncoder
приватны.
Магия построения графа путей сосредоточена в методе
acceptWay
, который принимает поочерёдно объекты дорог
- ReaderWay
и решает пригодна эта дорога для
прохода/проезда или нет. Определение пригодности это уже
прерогатива FlagEncoder
. Я передаю во
FlagEncoder
список дорог, по которым ходить нельзя.
Необходимо чтобы метод acceptWay
, натолкнувшись на эту
дорогу сказал своё твёрдое нет вернув 0.
Список назовём restricted
, и хранить он будет
id
объекта way
из OSM.
public class MyFlagEncoder {private List<Long> restricted;@Overridepublic long acceptWay(ReaderWay way) { if (restricted.contains(way.getId())) return 0; }}
У нас запретительный подход, если объект оказался в списке, то выполнение прерываем, вернув 0.
Предварительная подготовка данных
Написав FlagEncoder
, и переделав в нём всё что
хотели, можно приступать к построению графа маршрутов.
Я черпал вдохновение в документации Routing via Java API.
GraphHopper closableInstance = new GraphHopperOSM().setOSMFile(osmFilePath).forServer();closableInstance.setStoreOnFlush(true);closableInstance.setGraphHopperLocation(graphFolder);closableInstance.setEncodingManager(new EncodingManager(encoder));closableInstance.setCHEnabled(false);GraphHopper hopper = closableInstance.importOrLoad();
Здесь
-
osmFilePath - путь к pbf-файлу региона, pbf можно взять например на geofabrik, или других порталов, это срез данных из OSM;
-
encoder объект интересующего нас
FlagEncoder
, например того, который мы сами и создали на предыдущем шаге; -
graphFolder директория куда будут сохранены результаты построения.
Метод importOrLoad
проведёт построение графа, в
соответствии с правилами из FlagEncoder
, и сохранит
результат в указанную папку.
Строим маршрут
Нужно обратиться к следующей части документации GraphHopper: Low level API.
Предварительно созданные графы можно загрузить всё тем же
методом importOrLoad
.
GraphHopper closableInstance = new GraphHopperOSM().setOSMFile(pbfFile).forServer().setStoreOnFlush(true).setGraphHopperLocation(graphFolder).setEncodingManager(new EncodingManager(encoder)).setCHEnabled(false);GraphHopper hopper = closableInstance.importOrLoad();
Затем создать объект класса LocationIndex
:
GraphHopperStorage graph = hopper.getGraphHopperStorage();LocationIndex index = new LocationIndexTree(graph, new RAMDirectory());index.prepareIndex();
Для построения маршрута нам потребуются объекты трёх классов:
GraphHopperStorage
, FlagEncoder
,
LocationIndex
.
Используем их следующим образом, результатом будет
List<Double[]>
:
QueryResult fromQR = index.findClosest(fromLon, fromLat, EdgeFilter.ALL_EDGES);QueryResult toQR = index.findClosest(toLon, toLat, EdgeFilter.ALL_EDGES);QueryGraph queryGraph = new QueryGraph(graph);// Получить координаты путиqueryGraph.lookup(fromQR, toQR);Dijkstra dij = new Dijkstra(queryGraph, new FastestWeighting(encoder), TraversalMode.NODE_BASED);Path path = dij.calcPath(fromQR.getClosestNode(), toQR.getClosestNode());PointList pl = path.calcPoints();return pl.toGeoJson();
Заключение
Реализация получилась примитивной т.к. основана на проверке (в
методе acceptWay
) попадания объекта в заранее
составленный (или полученный всеми правдами и неправдами)
список:
if (restricted.contains(way.getId()))return 0;
Гораздо правильнее было сделать что-то подобное коду, основанному на проверке значений тегов из OSM, как здесь:
if (way.hasTag("foot", intendedValues)) {return acceptBit;}
Если у Вас есть возможность, для своей задачи, использовать второй вариант, основанный на проверке тегов лучше предпочесть его. Это ни как не помешает подмешать туда и дополнительную логику, не вписывающуюся в этот подход.
Удачи!