Как использовать GraphHopper для построения пешеходных маршрутов по собственным правилам

Построение маршрутов..., люди регулярно этим пользуются, особенно для автомобильных маршрутов, в навигаторах.

Решений, для построения маршрута тоже немало, в том числе существует 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;
	
	@Override
	public 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;
}

Если у Вас есть возможность, для своей задачи, использовать второй вариант, основанный на проверке тегов – лучше предпочесть его. Это ни как не помешает подмешать туда и дополнительную логику, не вписывающуюся в этот подход.

Удачи!

Комментарии 16

    +1
    Мы применяли Graphhopper, в том числе из Spark приложений, там реально достаточно продуманный API, и в целом все удобно. Мне кажется, Graphhopper незаслуженно мало популярен. Особенно, если вы на Java пишете.
      0
      Я не очень понял из документации в репозитории, есть ли open source вариант GraphHopper, предоставляющий REST? Или открытая редакция предполагает использование в составе Java-приложения?
        0
        Такой вариант есть, посмотрите документ Quickstart, нужно будет скачать уже готовый web service jar. После запуска получите аналог graphhopper.com/maps, взаимодействие с API можно на нём и посмотреть или в документации Routing API.

        Я создаю своё Java приложение потому что хочу работать через низкоуровневое API, прошу прощения если ввёл в заблуждение.
          0
          Спасибо! попробую.
          0
          Я бы советовал почитать документацию на основном сайте. GraphHopper не весь open source, некоторые части они не открывали совсем, некоторые не сразу, в общем, там все меняется, на github не все новости отражены. Ну т.е. REST-то допустим есть, но какие конкретно API там имеются — это отдельная история (в том смысле, что кроме routing есть еще isochrone, например, и т.п.).
            0
            Мне нужно только построение маршрутов. На данных OSM. Я пробежался и по сайту и по рпепозиторию, но не совсем понял.
              0
              Ну, дело в том, что там есть еще такой API, как отображение точки на граф дорог. Т.е. вы скажем в качестве исходной точки задаете произвольную, а этот API ее матчит на ближайшую точку на графе (ну т.е. представим, что исходная точка в лесу, а дорога по периметру). Вот собственно Routing API всегда был открыт (ну, насколько я помню), а эти некоторые другие — не всегда, то есть тут нужно еще и на версию поглядеть.

              В общем, смотрите матрицу вот тут: www.graphhopper.com/open-source, там написано, что открыто, что нет.
                0
                Спасибо! Навскидку свободная редакция мне подходит. Полагаю, что это как раз то, что я искал. Надо пробовать.
                  +1
                  Если интересует простое построение маршрутов/навигация или получение travel distance/time между точками, то посмотрите https://github.com/Project-OSRM/osrm-backend
                  Можно легко поднять как веб сервер и общаться через REST API. Документация http://project-osrm.org/docs/v5.23.0/api/#
                    0
                    Круто! Есть готовый контейнер, так что буду пробовать. Спасибо.
          0
          который, по координатам начала и окончания пути, вернёт массив координат маршрута.

          Только по началу и окончанию?
          Сам по себе GraphHopper идеален для нужного/гибкого построения маршрута с промежуточными, заданными точками.
            0
            Насколько я понимаю RoutingAlgorithm имеет метод который строит только по двум точкам, и все его реализации, например Dijkstra — тоже.

            Речь идёт именно про низкоуровневое API.

            Вероятно метод
            List<Path> calcPaths(int from, int to);
            вызывается несколько раз, в зависимости от количества этих промежуточных точек, а результат объединяется.

            Если бы мне нужно было строить через промежуточные точки, я бы так и сделал, а потом объединил множество
            List<Double[]>
            в один ответ.
              0
              Строить маршрут по двум точкам (для пользователя так себе, я об этом, а не возможностях api).
              Например в openstreetmap.org используется graphhopper, но он строит маршрут по 2 точкам, не так гибко, как нужно пользователю. Поэтому пользователь переходит на graphhopper.com и строит маршрут с промежуточными точками (через любые места, которые ему нужно посетить. И с graphhopper для пользователя это легко и просто).
            0

            есть еще классная штука для оптимизации маршрутов jsprit, но по ней документацию собрать крайне сложно. я уже много месяцев разбираюсь, но есть вопросы которые до сих пор не получается решить, а поддержки у них нет.

              0
              Вы, должно быть, логистикой занимаетесь? К сожалению не использовал jsprit.
                0

                Да, есть задумка, пока изучаем, но с документацией беда, в форумах ни разу никто не ответил, а специалистов вообще нет, так что все пока не торопко получается, к сожалению

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое