Road network in a database to build a route
Last updated
Last updated
https://habr.com/ru/articles/688556/
И так, формулировка задачи следующая: есть база данных, в ней хранится информация о дорогах, включая координаты, нужно реализовать построение маршрутов из начальной точки к конечной.
Построение маршрутов - задача распространенная, и, как для каждой распространённой задачи, для неё давно существуют реализации. Мне нравится GraphHopper. Да так нравится, что моя первая статья на Хабре была про то, как создать для него собственные правила построения графа дорог.
Кроме того, для построения маршрута по дорогам из PostgreSQL, можете ознакомиться с pgRouting, на Хабре есть несколько статей по этой теме, вот хотя бы: “делаем маршрутизацию (роутинг) на OpenStreetMap”. Но это альтернативный способ реализации, я его затрагивать не буду.
Эта статья будет про то, как использовать свой источник данных, и как этот источник данных редактировать так, чтобы GraphHopper вас понял.
GraphHopper использует данные OSM для построения графа дорог, однако есть возможность для расширения. Если нам понадобится альтернативный от OSM источник, необходимо предоставить свою реализацию класса DataReader, который будет читать данные из нашего хранилища.
К счастью для нас, мы не первые кому такое решение понадобилось, Японская компания Georepublic, уже всё сделала. Репозиторий их проекта есть на GitHub: mbasa/graphhopper-reader-postgis. Используем его. Я сделал форк репозитория Tkachenko-Ivan/graphhopper-reader-postgis, он немного отличается от первоисточника, все примеры кода ниже, взяты из форка.
В качестве хранилища данных используется PostgreSQL, с расширением PostGIS. Давайте разберём как это работает, и с чем это едят. Пример PostgreSQL поможет нам понять принцип создания произвольных источников данных.
Судя по всему, японцы основывали свои наработки на версии 2.x, а потом, с выходом новых версий GraphHopper, их актуализировали. Однако я решил вернуться к корням, все ссылки, которые я буду приводить на репозиторий GraphHopper, будут на ветку 2.x.
GraphHopper написан на Java, поэтому, если планируете делать какие-то доработки, или просто использовать его библиотеки, создайте проект Java. Прежде чем приступить к написанию классов для использования произвольных источников данных, необходимо подключить к проекту основную библиотеку, классы которой мы и будем дополнять и расширять:
В качестве точки доступа к API маршрутизации, используется класс GraphHopper. Он является по сути фасадом для индексирования дорог и построения маршрутов. Как я уже говорил, в качестве источника используется OSM, и для работы с этим источником есть соответствующий класс GraphHopperOSM, - унаследованный от класса GraphHopper
. На основе таких данных из OSM как, тип дороги, направление движения и максимальная скорость, он и строит граф дорог. Нас устраивает всё, кроме источника, поэтому мы можем не изобретать велосипед, а унаследовать класс GraphHopperOSM, и переопределить метод createReader:
Здесь же мы должны дополнить метод init
, создав HashMap
для хранения параметров подключения к источнику данных, в нашем случае PostgreSQL.
Эти параметры были нами использованы при создании объекта класса OSMPostgisReader.
Приступим к разбору классов, которые непосредственно будут выполнять чтение данных из источника: OSMPostgisReader, который наследует абстрактный PostgisReader, который, в свою очередь, реализует интерфейс DataReader:
Диаграмма классов для чтения данных дорог (в пакетах показаны классы GraphHopper, вне пакетов - созданные "нами")
Нам нужно реализовать метод readGraph
в PostgisReader
:
Самое интересное начинается с метода processJunctions()
. Вначале создаётся подключение к БД в методе openPostGisStore:
Затем получаем список дорог - FeatureIterator, и обходим его:
Метод getFeatureIterator реализован в классе PostgisReader
.
Для соединения с БД и чтения геоданных, используется GeoTools, подключаем библиотеки:
Получаем объект соответствующий строке в БД:
Нам необходимо получить координаты геометрии дороги (массив точек), для этого используем метод getCoords(SimpleFeature feature)
:
И в цикле обрабатываем все точки линии. Все обработанные точки хранятся в специальном массиве (для карты дорог России понадобится сохранить порядка 60 миллионов объектов):
Если точка попадает в него впервые, у неё статус COORD_STATE_UNKNOWN
, а если она уже встречалась ранее, то у неё статус COORD_STATE_PILLAR
, что означает, что это узловая точка, - она встречается в нескольких разных линия, а значит в этой точке можно повернуть на другую дорогу, ей присваивается некоторый порядковый номер, начиная с 1, по количеству найденных узлов (повторно узлы не обрабатываются, т.е. точка на перекрёстке семи дорог будет помечена как узловая один раз, и этого достаточно):
Иными словами в этом методе - мы получаем список перекрёстков.
Запускается после processJunctions
, и начинается аналогично: с подключения к БД, получения списка дорог и обхода их в цикле, разложения геометрии дороги на координаты, и перебор этих координат.
Его задача создать рёбра графа дорог и вычислить их длину. Рёбрами графа дорог будут не сами дороги, а те их участки, которые зажаты между найденными ранее точками перекрёстков.
Преобразование дорог в рёбра графа
Помимо перекрёстков существует множество других точек, из которых состоит линия, они позволяют вычислить её длину, поэтому все точки между перекрёстками, сохраняются в массиве pillars
:
А когда дойдём до перекрёстка (условие if (state >= FIRST_NODE_ID)
), - вычисляется длина ребра:
Для найденного ребра затем создаётся объект класса ReaderWay, в который передаются параметры дороги:
В конце настройки регистрируем созданную дорогу в encodingManager:
Здесь и обрабатываются свойства дороги для определения скорости и направления в ребре графа.
На всю Россию получилось примерно 14.5 миллионов рёбер.
Он присутствует в реализации, и накладывает ограничение на проезд, например запрет поворота налево (см. OSMTurnRelation), однако не используется из-за отсутствия в скачанных мною данных, полей:
restriction
- тип ограничения;
restriction_to
- по отношению к какой дороге это ограничение накладывается.
Если хотите чтобы заработал, надо искать другой источник данных или задавать самостоятельно, (я скачал shape c geofabrik.de, но об этом ниже). И не забыть также изменить SQL представление (о представлении тоже ниже).
К счастью проходить всю процедуру построения графа дорог не придётся при каждом запуске приложения, после построения, граф будет благополучно сохранён в указанную директорию. При перезапуске, приложение обратится к этой директории и загрузит индекс из файлов.
На построение графа дорог всей России потребовалось примерно 10 ГБ оперативной памяти, поэтому не забывайте про -Xms
.
В первую очередь читайте README автора, но свои пять копеек так же вставлю.
Для начала нам нужно где-то взять данные, удобно скачать shape c geofabrik, и загрузить файл gis_osm_roads_free_1.shp
(название может немного отличаться) в свою БД, предварительно создав в ней таблицу для дорог (поля соответствуют тем, что представлены в shape файле):
В fclass
содержится значение тега highway, можете выбрать только те типы дорог, которые вас интересуют, а лишние удалить чтобы не занимали место и не тратили время.
Скачанные геоданные имеют тип MULTILINESTRING
, мне было удобнее работать с LINESTRING
, поэтому я сначала гружу во временный слой gis_osm_roads
, а потом осуществляю конвертацию с помощью ST_LineMerge в другой слой - gis_roads
(gis_osm_roads
можно после этого удалять):
Вы можете не конвертировать из MULTILINESTRING
в LINESTRING
, построитель графа и маршрутизатор умеют работать с обоими типами. Я произвожу конвертацию потому что, при добавлении новых данных в слой, мне удобнее работать с LINESTRING .
Таблица не обязательно должна однозначно соответствовать полям в скачанном файле, я добавил в неё несколько дополнительных полей, например дата загрузки date_load
, и удалил то, что посчитал лишним, например ref
. Ключ создал свой - gid
(т.к. вставка данных предполагается не только за счёт импорта с OSM, но и из своих источников), osm_id
по сути уже и не нужен. Вы можете аналогично создавать и удалять поля. Для построителя в первую очередь важны fclass
, geom
, maxspeed
, oneway
, на основе которых создадим представление:
Поля bridge
и tunnel
не нужны для прокладки маршрута, т.к. для GraphHopper важно наличие общей точки, а не тип, однако эти поля важны для поиска пересечений при вставке новых линий, - логично, мост или эстакада не должны иметь точек пересечения с дорогой над которой они проложены.
Я загрузил дороги Калининградской области - она занимает меньше места среди других shape файлов. Если не хочется мучаться с загрузкой, то контейнер с загруженными данными можно взять с Docker Hub: tkachenkoivan/road-data.
Итак, данные получены. Переходим к построению графа.
Разобранный далее код, можно увидеть на GitHub: пример построения маршрута.
Создаём объект, для индексирования и построения маршрута:
Выполняем настройку:
параметры подключения к БД,
указываем имя представления, в котором присутствуют данные - roads_view
,
директорию, где будут храниться построенные индексы,
Поскольку мы решили строить автомобильные маршруты, то указываем имя для класса CarFlagEncoder:
Используем параметры для индексирования графа дорог, или загрузки из файлов, если он уже был ранее проиндексирован:
Вызывается метод init
, класса GraphHopperPostgis
.
Теперь можем построить маршрут, указывая в запросе точки, которые хотим посетить:
Маршрут построен!
Чтение из БД для маршрутизации мы подсмотрели у Georepublic, спасибо им, однако там ничего нет о появлении новых данных. В целом это не проблема, если в качестве источника используется OSM, можно:
раз в какой-то период, например месяц, брать новую выгрузку OSM;
удалять из своей БД все данные;
заменять их новой выгрузкой;
перестраивать граф дорог.
Давайте подумаем что делать, если нам такой сценарий не подходит, например по той причине, что у нас свой анонимный источник данных о дорогах.
Саму вставку данных разбирать не будем, оставим без ответа вопрос о том, как эти данные в таблицу попали: может их загрузили из shape-файла, может этот слой можно редактировать через GeoServer, может геометрии были созданы через SQL выражения… здесь пусть каждый извращается как умеет.
Разберём что делать с новыми данными после того как они оказались в слое - как сделать так, чтобы новые данные учитывались при построении маршрута. А учитываться они будут в том случае, если имеют общие точки с другими линиями, в местах пересечений. Иными словами: нам эти точки предстоит создать, если их там ещё нет.
Вначале подключите net.postgis:
Создадим функцию поиска пересечений, воспользуемся ST_Intersection:
В WHERE temps.gid IN (...)
передаются идентификаторы добавленных линий, добавлены они сразу в основной слой, поэтому необходима проверка temps.gid <> mains.gid
, чтобы не обрабатывать пересечения с самим собой. Чтобы исключить всякие мосты и тоннели, добавляйте подобные условия:
Пересечения нашли с помощью SQL.
Перебираем в цикле найденные пересечения:
Здесь всё зависит от того, какого типа геометрия пересечения, подробнее они будут разобраны ниже, в примерах. Но всё сводится к одной цели - иметь точки с одинаковыми координатами на месте пересечения.
Найдя факт пересечения линий, все эти линии необходимо модифицировать создав в них точки на месте пересечения.
Линия представляет собой массив точек, какую точку вставить мы уже знает, - точку пересечения, осталось найти место в массиве куда вставлять.
Зная координаты точки пересечения, мы можем воспользоваться функцией ST_LineLocatePoint, которая возвращает значение с плавающей точкой от 0 до 1, представляющее местоположение точки на линии:
Теперь нужно понять сколько точек в массиве располагается на этом участке, для этого воспользуемся ST_NumPoints:
Теперь мы знает точку, после которой необходимо вставить найденную точку пересечения, при условии что координаты этих точек не совпадают, Для вставки воспользуемся функцией ST_AddPoint:
Здесь tempWay
- это полученная из БД линия, чтобы ещё раз убедиться что координаты точки в указанной позиции не совпадают с добавляемой точкой пересечения.
Получение tempWay
:
Теперь рассмотрим несколько примеров.
Данные, для моделируемых ситуаций я выложил в репозиторий GitHub Tkachenko-Ivan/shape-example-graphhopper, здесь они сохранены в shape-файлы, в README представлены схематичные иллюстрации содержимого, и дано текстовое представление данных. Текстовое представление можно использовать чтобы не грузить shape, а создать линии сразу в БД, с помощью ST_LineFromText, например:
Сначала добавим две линии, которые пересекают одну из существующих линий, и пересекаются между собой. Точки, на местах пересечения не созданы - необходимо их создать. Например добавление 1 и 3 к линии 2.
Пересекающиеся линии
Мы должны обработать новые линии и создать точки на местах пересечений, при том, как на месте пересечений двух новых линий между собой, так и на месте пересечения с уже добавленной ранее линией.
Если линии пересекаются, то точки, на местах пересечений, должны быть добавлены в обе линии: