Road network in a database to build a route
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. Прежде чем приступить к написанию классов для использования произвольных источников данных, необходимо подключить к проекту основную библиотеку, классы которой мы и будем дополнять и расширять:
GraphHopperPostgis - фасад для работы с графом дорог
В качестве точки доступа к 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.
Пересекающиеся линии
Мы должны обработать новые линии и создать точки на местах пересечений, при том, как на месте пересечений двух новых линий между собой, так и на месте пересечения с уже добавленной ранее линией.
Если линии пересекаются, то точки, на местах пересечений, должны быть добавлены в обе линии:
Было:
Стало:
Можно запустить ещё раз обработку этих линий, для того чтобы убедиться что повторно точки пересечения не создаются, - у ранее созданных точек дубли не появляются.
Если передать линии 1 и 3, для обработки, то будет найдено как пересечение 1 с 3, так и 3 с 1, важно повторно линии не обрабатывать, поэтому для хранения факта обработки необходимо создать список, и проверять в нём факт обработки.
Соприкасающиеся линии
Отличие от предыдущего примера в том, что одна линия, своим концом примыкает к другой линии, но не пересекает её.
Соприкасающиеся линии
Необходимо убедиться что мы находим и корректно обрабатываем эту ситуацию: в одной из линий, создавать новую точку не надо, точка пересечения, ну или “примыкания”, уже создана, осталось модифицировать вторую линию. Но это в идеале, практика несколько далека от идеала, из-за возможных допусков.
Ситуацию смоделировать легко, а вот написать обработчик наоборот - сложно. Основная сложность заключается в том, что примыкание может осуществляться с некоторой погрешностью, разумной конечно же. Если мы используем функцию ST_Intersects для определения статуса пересечения (пересеклась или нет), то допустимая погрешность 0.00001 (sic!). Это очень мало, невозможно гарантировать что все линии будут создаваться с таким допуском, поэтому первое что нужно сделать - перегрузить функцию ST_Intersects:
Теперь мы можем находить факт пересечения с той погрешностью, с которой посчитаем необходимым.
ST_Intersection
находит геометрию пересечения - точку пересечения, которую мы ожидаем найти, однако, из-за тех же допусков и погрешностей может возвращать пустую геометрию. В этом случае можно воспользоваться функцией ST_ClosestPoint, которая вернёт из первой геометрии самую ближайшую точку ко второй геометрии:
Понятно что “ближайшая” и “лежащая на линии” не совсем одно и то же, тем более что мы вводим некоторые допуски, поэтому, есть вероятность что будет две близко расположенные, но отличающиеся друг от друга, точки.
Кроме того, введение погрешности значительно замедляет работу SQL-запроса при поиске пересечений, если данных много, например все дороги России, - замедление становится чувствительным.
Соединяющиеся линии
Тут всё просто, линии примыкают друг к другу.
Соединяющиеся линии
Если конечные точки линий совпадут, то линии останутся неизменными, если из-за погрешности точки не будут совпадать, то одна из линий будет модифицирована.
Многократное пересечение линий
Две линии пересекаются более чем один раз. Необходимо убедиться что все точки пересечения будут созданы.
Многократно пересекающиеся линии
Особенность этого случая в том, что пересечением будет MULTIPOINT
:
Во всех предыдущих случаях был POINT
.
Мы можем разложить MultiPoint на Point, и обработать все точки последовательно, независимо друг от друга:
Накладывающиеся линии
Здесь линии не просто пересекаются, но частично накладываются друг на друга. Тот участок, который повторяется в обеих линиях, он избыточен, хранить его не надо, и поэтому из одной из линий он должен быть удалён. В этом случае линия разбивается на части, и части сохраняются как новые линии.
Накладывающиеся линии
Если одна из линий существует давно, а вторая загружена и в процессе обработки, то логично старую линия не трогать, а новую разбить на участки. Если обе линии новые, то “жертвой” может стать любая из них.
Результатом пересечения в этом случае будет LINESTRING, или MULTILINESTRING (если линии совпали на разных участках), например:
Именно этот участок необходимо убрать. Воспользуемся ST_Difference и посмотрим что осталось от линии:
В нашем примере, от линии останется два отдельных куска, их надо вставить в слой:
Изначальная линия после этого должна быть удалена, а две новые линии необходимо обработать так же, как если бы изначально вставляли их, а не удалённую линию, - рекурсия.
Это самая сложно воспроизводимая из ситуаций, всё дело, как всегда, в погрешности. Если при редактировании карты не включён режим “прилипания”, или он сам рассчитал с некоторым допуском (например в QGIS он может работать с точностью до 0,00001 градуса) - идеального совпадения не будет, а значит участок не будет обнаружен. Конечно факт пересечения в виде точке будет найден, благодаря ST_ClosestPoint
, но именно точки, а не линии. И это меньшее из зол. Можно попытаться нивелировать погрешность с помощью ST_Buffer, однако считаю это плохой идеей, т.к. ST_Buffer
скажется даже на тех запросах, где результатом пересечения должна быть точка, - вместо неё будет линия длинной с размер буфера.
Ситуация может быть типичной, например если один и тот же файл загружать дважды, например по ошибке.
Полное наложение линий
Необходимо убедиться что останется только одна линия: новая линия не будет создана, если в БД уже такая существует, а если дубль присутствует в самом файле загрузки, то будет выбрана и создана только одна из двух.
Воспользуемся методом ST_Difference
, например таким образом:
Если линии полностью совпадают, то ответом будет LINESTRING EMPTY
. Для удобства можем в запрос добавить ST_IsEmpty(diff)
, и условие проверяющее на пустоту.
Так же может возникнуть ситуация когда одна линия больше чем другая, но при этом полностью её поглощает. Если добавляется меньшая линия, - она должна быть удалена, если большая, - она должна быть рассечена повторяющейся частью.
Похоже на пример с “наложением линий”.
Поглощение линий
Важно обратить внимание на последовательность действий: когда линия разделяется на кусочки (путём удаления совпадающей с другими линиями части), происходит операция вставки этих линий, и их тоже надо обработать как добавленные линии и найти точки пересечения с уже существующими. Необходимо чтобы линия, из которой они получились не участвовала в запросе поиска пересечений, иначе изначальная линия их полностью поглотит. Исходную линию надо как-то исключить, или даже удалить - deleteFromTemp
, и только потом выполнять поиск пересечений рекурсивно вызвав putIntersectionPoint
.
Идея та же: одна из наложившихся линий будет удалена, вместо неё будет создано две новые линии. Однако помимо наложения, эта линия ещё и имеет точки пересечения с некоторыми линиями (например при добавлении линии 4, она частично совпадает с линией 3, линия 4 будет удалена, и вместо неё появятся две новые).
Наложение и пересечение линий
Необходимо убедиться, что в местах пересечений будет создано только по одной точке в каждой линии, и удаление не приведёт к ошибкам, в случае, если в списке найденных пересечений, имеется факт пересечения с удалённой ранее линией. Поэтому можно сохранять список удалённых линий, и при обработке найденных пересечений, проверять не была ли эта линия удалена:
Это был последний из рассматриваемых примеров.
Итог
Статья получилась объёмной, давайте ещё раз соберём всё вместе.
И так, мы разобрали решение от Georepublic, оригинал их репозитория есть на GitHub: mbasa/graphhopper-reader-postgis.
Я сделал форк их решения и немного подшаманил его: Tkachenko-Ivan/graphhopper-reader-postgis.
Данные в виде spahe файлов можно взять с geofabrik.
Для тех, кому данные не принципиальные и хочется перейти к экспериментам с построителем, я уже загрузил данные по Калининградской области и выложил в докер контейнере на Docker Hub: tkachenkoivan/road-data.
Затем разобрали как обрабатывать появление новых данных в таблице, получившийся код есть на GitHub Gist Tkachenko-Ivan/PostGisGeometry.java
Примеры загружаемых данных, на которых можно протестировать загрузку есть на GitHub: Tkachenko-Ivan/shape-example-graphhopper
Мы рассмотрели, как реализовать в GraphHopper чтение данных из источника отличного от OSM, на примере PostgreSQL, но точно такой же подход можно использовать для чего угодно, из чего можно получить список дорог и их координат.
Удачи!
Last updated