Road network in a database to build a route

Last updated 1 year ago

Как хранить сеть дорог в БД для построения маршрута?

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

Построение маршрутов - задача распространенная, и, как для каждой распространённой задачи, для неё давно существуют реализации. Мне нравится 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. Прежде чем приступить к написанию классов для использования произвольных источников данных, необходимо подключить к проекту основную библиотеку, классы которой мы и будем дополнять и расширять:

<dependency>
  <groupId>com.graphhopper</groupId>
  <artifactId>graphhopper-web</artifactId>
  <version>2.4</version>
</dependency>

GraphHopperPostgis - фасад для работы с графом дорог

В качестве точки доступа к API маршрутизации, используется класс GraphHopper. Он является по сути фасадом для индексирования дорог и построения маршрутов. Как я уже говорил, в качестве источника используется OSM, и для работы с этим источником есть соответствующий класс GraphHopperOSM, - унаследованный от класса GraphHopper. На основе таких данных из OSM как, тип дороги, направление движения и максимальная скорость, он и строит граф дорог. Нас устраивает всё, кроме источника, поэтому мы можем не изобретать велосипед, а унаследовать класс GraphHopperOSM, и переопределить метод createReader:

public class GraphHopperPostgis extends GraphHopperOSM {

    private final Map<String, String> postgisParams = new HashMap<>();

    ...

    @Override
    protected DataReader createReader(GraphHopperStorage ghStorage) {
        OSMPostgisReader reader = new OSMPostgisReader(ghStorage, postgisParams);
        for (OSMPostgisReader.EdgeAddedListener l : edgeAddedListeners) {
            reader.addListener(l);
        }
        return initDataReader(reader);
    }

    ...

}

Здесь же мы должны дополнить метод init, создав HashMap для хранения параметров подключения к источнику данных, в нашем случае PostgreSQL.

public class GraphHopperPostgis extends GraphHopperOSM {

    ...

    private final Map<String, String> postgisParams = new HashMap<>();

    @Override
    public GraphHopper init(GraphHopperConfig ghConfig) {
        postgisParams.put("dbtype", "postgis");
        postgisParams.put("host", ghConfig.getString("db.host", host));
        postgisParams.put("port", ghConfig.getString("db.port", port));
        ...

        return super.init(ghConfig);
    }

    ...
}

Эти параметры были нами использованы при создании объекта класса OSMPostgisReader.

Приступим к разбору классов, которые непосредственно будут выполнять чтение данных из источника: OSMPostgisReader, который наследует абстрактный PostgisReader, который, в свою очередь, реализует интерфейс DataReader:

Диаграмма классов для чтения данных дорог (в пакетах показаны классы GraphHopper, вне пакетов - созданные "нами")

Нам нужно реализовать метод readGraph в PostgisReader:

public abstract class PostgisReader implements DataReader {

    ...

    @Override
    public void readGraph() {
        graphStorage.create(1000);
        processJunctions();
        processRoads();
        finishReading();
    }

    ...

}

Самое интересное начинается с метода processJunctions(). Вначале создаётся подключение к БД в методе openPostGisStore:

protected DataStore openPostGisStore() {

    ...

    DataStore ds = DataStoreFinder.getDataStore(this.postgisParams);

    ...

}

Затем получаем список дорог - FeatureIterator, и обходим его:

void processJunctions() {
    DataStore dataStore = null;
    FeatureIterator<SimpleFeature> roads = null;

    try {
        dataStore = openPostGisStore();
        roads = getFeatureIterator(dataStore, roadsFile.getName());

        ...

        while (roads.hasNext()) {
            SimpleFeature road = roads.next();
            ...
        }
    }

    ...

}

Метод getFeatureIterator реализован в классе PostgisReader.

Для соединения с БД и чтения геоданных, используется GeoTools, подключаем библиотеки:

<dependency>
  <groupId>org.geotools</groupId>
  <artifactId>gt-main</artifactId>
  <version>19.4</version>
</dependency>
<dependency>
  <groupId>org.geotools.jdbc</groupId>
  <artifactId>gt-jdbc-postgis</artifactId>
  <version>19.4</version>
</dependency>

Получаем объект соответствующий строке в БД:

SimpleFeature road = roads.next();

Нам необходимо получить координаты геометрии дороги (массив точек), для этого используем метод getCoords(SimpleFeature feature):

public abstract class PostgisReader implements DataReader {

    ...

    protected List<Coordinate[]> getCoords(SimpleFeature feature) {
        ArrayList<Coordinate[]> ret = new ArrayList<>();

        ...

        Object coords = feature.getDefaultGeometry();

        ...

        if (coords instanceof LineString) {
            ret.add(((LineString) coords).getCoordinates());
        } else if (coords instanceof MultiLineString) {
            MultiLineString mls = (MultiLineString) coords;
            int n = mls.getNumGeometries();
            for (int i = 0; i < n; i++) {
                ret.add(mls.getGeometryN(i).getCoordinates());
            }
        }
        return ret;
    }

    ...

}

И в цикле обрабатываем все точки линии. Все обработанные точки хранятся в специальном массиве (для карты дорог России понадобится сохранить порядка 60 миллионов объектов):

public class OSMPostgisReader extends PostgisReader implements TurnCostParser.ExternalInternalMap {

    private GHObjectIntHashMap<Coordinate> coordState = new GHObjectIntHashMap<>(10_000_000, 0.7f);

    ...
}

Если точка попадает в него впервые, у неё статус COORD_STATE_UNKNOWN, а если она уже встречалась ранее, то у неё статус COORD_STATE_PILLAR, что означает, что это узловая точка, - она встречается в нескольких разных линия, а значит в этой точке можно повернуть на другую дорогу, ей присваивается некоторый порядковый номер, начиная с 1, по количеству найденных узлов (повторно узлы не обрабатываются, т.е. точка на перекрёстке семи дорог будет помечена как узловая один раз, и этого достаточно):

while (roads.hasNext()) {

    ...

    for (Coordinate[] points : getCoords(road)) {

        ...

        for (int i = 0; i < points.length; i++) {
            Coordinate c = points[i];

            ...

            int state = coordState.get(c);
            if (state >= FIRST_NODE_ID) {
                continue;
            }

            if (i == 0 || i == points.length - 1 || state == COORD_STATE_PILLAR) {
                int nodeId = nextNodeId++;
                coordState.put(c, nodeId);
                saveTowerPosition(nodeId, c);
            } else if (state == COORD_STATE_UNKNOWN) {
                coordState.put(c, COORD_STATE_PILLAR);
            }

            ...

        }
    }
}

Иными словами в этом методе - мы получаем список перекрёстков.

Запускается после processJunctions, и начинается аналогично: с подключения к БД, получения списка дорог и обхода их в цикле, разложения геометрии дороги на координаты, и перебор этих координат.

Его задача создать рёбра графа дорог и вычислить их длину. Рёбрами графа дорог будут не сами дороги, а те их участки, которые зажаты между найденными ранее точками перекрёстков.

Преобразование дорог в рёбра графа

Помимо перекрёстков существует множество других точек, из которых состоит линия, они позволяют вычислить её длину, поэтому все точки между перекрёстками, сохраняются в массиве pillars:

void processRoads() {

    ...

    while (roads.hasNext()) {

        ...

        for (Coordinate[] points : getCoords(road)) {

            ...

            List<Coordinate> pillars = new ArrayList<>();
            for (Coordinate point : points) {

                ...

                if (state >= FIRST_NODE_ID) {
                    // Получить расстояние и приблизитльный центр

                    ...

                    double distance = getWayLength(startTowerPnt, pillars, point);
                    addEdge(fromTowerNodeId, toTowerNodeId, road, distance, estmCentre, pillarNodes);

                    ...

                } else {
                    pillars.add(point);
                }

                ...

            }
        }
    }

    ...
}

А когда дойдём до перекрёстка (условие if (state >= FIRST_NODE_ID)), - вычисляется длина ребра:

protected double getWayLength(Coordinate start, List<Coordinate> pillars, Coordinate end) {
    double distance = 0;

    Coordinate previous = start;
    for (Coordinate point : pillars) {
        distance += distCalc.calcDist(lat(previous), lng(previous), lat(point), lng(point));
        previous = point;
    }
    distance += distCalc.calcDist(lat(previous), lng(previous), lat(end), lng(end));

    ...

    return distance;
}

Для найденного ребра затем создаётся объект класса ReaderWay, в который передаются параметры дороги:

private void addEdge(int fromTower, int toTower, SimpleFeature road, double distance,
                         GHPoint estmCentre, PointList pillarNodes) {
    ...

    ReaderWay way = new ReaderWay(id);
    way.setTag("estimated_distance", distance);
    way.setTag("estimated_center", estmCentre);

    ...

    // Тип дороги
    Object type = road.getAttribute("fclass");
    if (type != null) {
        way.setTag("highway", type.toString());
    }

    // Максимальная скорость
    Object maxSpeed = road.getAttribute("maxspeed");
    if (maxSpeed != null && !maxSpeed.toString().trim().equals("0")) {
        way.setTag("maxspeed", maxSpeed.toString());
    }

    ...

}

В конце настройки регистрируем созданную дорогу в encodingManager:

encodingManager.handleWayTags(way, acceptWay, tempRelFlags);
...
encodingManager.applyWayTags(way, edge);

Здесь и обрабатываются свойства дороги для определения скорости и направления в ребре графа.

На всю Россию получилось примерно 14.5 миллионов рёбер.

Он присутствует в реализации, и накладывает ограничение на проезд, например запрет поворота налево (см. OSMTurnRelation), однако не используется из-за отсутствия в скачанных мною данных, полей:

restriction - тип ограничения;
restriction_to - по отношению к какой дороге это ограничение накладывается.

Если хотите чтобы заработал, надо искать другой источник данных или задавать самостоятельно, (я скачал shape c geofabrik.de, но об этом ниже). И не забыть также изменить SQL представление (о представлении тоже ниже).

Результат

К счастью проходить всю процедуру построения графа дорог не придётся при каждом запуске приложения, после построения, граф будет благополучно сохранён в указанную директорию. При перезапуске, приложение обратится к этой директории и загрузит индекс из файлов.

На построение графа дорог всей России потребовалось примерно 10 ГБ оперативной памяти, поэтому не забывайте про -Xms.

Как это использовать?

В первую очередь читайте README автора, но свои пять копеек так же вставлю.

Подготовка данных

Для начала нам нужно где-то взять данные, удобно скачать shape c geofabrik, и загрузить файл gis_osm_roads_free_1.shp (название может немного отличаться) в свою БД, предварительно создав в ней таблицу для дорог (поля соответствуют тем, что представлены в shape файле):

CREATE TABLE public.gis_osm_roads (
    osm_id varchar(10) NULL,
    code int2 NULL,
    fclass varchar(28) NULL,
    "name" varchar(100) NULL,
    ref varchar(100) NULL,
    oneway varchar(1) NULL,
    maxspeed int2 NULL,
    layer float8 NULL,
    bridge varchar(1) NULL,
    tunnel varchar(1) NULL,
    geom geometry(MULTILINESTRING, 4326) NULL,
    CONSTRAINT gis_osm_roads_pkey PRIMARY KEY (osm_id)
);

CREATE INDEX gis_osm_roads_geom_idx ON public.gis_osm_roads USING gist (geom);

В fclass содержится значение тега highway, можете выбрать только те типы дорог, которые вас интересуют, а лишние удалить чтобы не занимали место и не тратили время.

Скачанные геоданные имеют тип MULTILINESTRING, мне было удобнее работать с LINESTRING, поэтому я сначала гружу во временный слой gis_osm_roads, а потом осуществляю конвертацию с помощью ST_LineMerge в другой слой - gis_roads (gis_osm_roads можно после этого удалять):

INSERT INTO gis_roads (fclass,"name",oneway,maxspeed,bridge,tunnel,geom)
(SELECT fclass,"name",oneway,maxspeed,bridge,tunnel,ST_LineMerge(geom) FROM gis_osm_roads)

Вы можете не конвертировать из MULTILINESTRING в LINESTRING, построитель графа и маршрутизатор умеют работать с обоими типами. Я произвожу конвертацию потому что, при добавлении новых данных в слой, мне удобнее работать с LINESTRING .

Таблица не обязательно должна однозначно соответствовать полям в скачанном файле, я добавил в неё несколько дополнительных полей, например дата загрузки date_load, и удалил то, что посчитал лишним, например ref. Ключ создал свой - gid (т.к. вставка данных предполагается не только за счёт импорта с OSM, но и из своих источников), osm_id по сути уже и не нужен. Вы можете аналогично создавать и удалять поля. Для построителя в первую очередь важны fclass, geom, maxspeed, oneway, на основе которых создадим представление:

CREATE OR REPLACE VIEW public.roads_view
AS SELECT gis_roads.gid AS osm_id,
    gis_roads.maxspeed,
    gis_roads.oneway,
    gis_roads.fclass,
    gis_roads.name,
    gis_roads.geom
   FROM gis_roads;

Поля bridge и tunnel не нужны для прокладки маршрута, т.к. для GraphHopper важно наличие общей точки, а не тип, однако эти поля важны для поиска пересечений при вставке новых линий, - логично, мост или эстакада не должны иметь точек пересечения с дорогой над которой они проложены.

Я загрузил дороги Калининградской области - она занимает меньше места среди других shape файлов. Если не хочется мучаться с загрузкой, то контейнер с загруженными данными можно взять с Docker Hub: tkachenkoivan/road-data.

Итак, данные получены. Переходим к построению графа.

Индексирование и построение маршрута

Разобранный далее код, можно увидеть на GitHub: пример построения маршрута.

Создаём объект, для индексирования и построения маршрута:

GraphHopper hopper = new GraphHopperPostgis().forServer();

Выполняем настройку:

параметры подключения к БД,
указываем имя представления, в котором присутствуют данные - roads_view,
директорию, где будут храниться построенные индексы,
encoder.

Поскольку мы решили строить автомобильные маршруты, то указываем имя для класса CarFlagEncoder:

GraphHopperConfig graphHopperConfig = new GraphHopperConfig();
graphHopperConfig.putObject("db.host", host);
graphHopperConfig.putObject("db.port", port);
...
graphHopperConfig.putObject("datareader.file", "roads_view");
graphHopperConfig.putObject("graph.location", dir);
graphHopperConfig.putObject("graph.flag_encoders", "car");

Используем параметры для индексирования графа дорог, или загрузки из файлов, если он уже был ранее проиндексирован:

hopper.init(graphHopperConfig);
hopper.importOrLoad();

Вызывается метод init, класса GraphHopperPostgis.

Теперь можем построить маршрут, указывая в запросе точки, которые хотим посетить:

GHRequest request = new GHRequest();
for (int i = 0; i < points.size(); i++) {
    request.addPoint(new GHPoint(points.get(i)[0], points.get(i)[1]));
}
request.setProfile("my_car");

GHResponse response = hopper.route(request);

Маршрут построен!

Как обрабатывать появление новых данных?

Чтение из БД для маршрутизации мы подсмотрели у Georepublic, спасибо им, однако там ничего нет о появлении новых данных. В целом это не проблема, если в качестве источника используется OSM, можно:

раз в какой-то период, например месяц, брать новую выгрузку OSM;
удалять из своей БД все данные;
заменять их новой выгрузкой;
перестраивать граф дорог.

Давайте подумаем что делать, если нам такой сценарий не подходит, например по той причине, что у нас свой анонимный источник данных о дорогах.

Саму вставку данных разбирать не будем, оставим без ответа вопрос о том, как эти данные в таблицу попали: может их загрузили из shape-файла, может этот слой можно редактировать через GeoServer, может геометрии были созданы через SQL выражения… здесь пусть каждый извращается как умеет.

Разберём что делать с новыми данными после того как они оказались в слое - как сделать так, чтобы новые данные учитывались при построении маршрута. А учитываться они будут в том случае, если имеют общие точки с другими линиями, в местах пересечений. Иными словами: нам эти точки предстоит создать, если их там ещё нет.

Вначале подключите net.postgis:

<dependency>
  <groupId>net.postgis</groupId>
  <artifactId>postgis-jdbc</artifactId>
  <version>2.3.0</version>
  <type>jar</type>
</dependency>

Поиск пересечений

Создадим функцию поиска пересечений, воспользуемся ST_Intersection:

private List<Map<String, Object>> findIntersect(List<Long> tempIds) {
    if (tempIds.isEmpty()) {
        return new ArrayList<>();
    }
    String ids = StringUtils.join(tempIds, ',');
    String sql = String.format(
                """
                SELECT
                        ST_Intersection(temps.geom, mains.geom) intersects,
                        temps.gid temps_id,
                        mains.gid mains_id,
                        temps.geom temps_way,
                        mains.geom mains_way
                FROM
                        road_temp AS temps,
                        road_temp AS mains
                WHERE temps.gid IN (%s)
                  AND temps.gid <> mains.gid
                  AND ST_Intersects(temps.geom, mains.geom) IS TRUE
                """, ids);
    return jdbcTemplate.queryForList(sql);
}

В WHERE temps.gid IN (...) передаются идентификаторы добавленных линий, добавлены они сразу в основной слой, поэтому необходима проверка temps.gid <> mains.gid, чтобы не обрабатывать пересечения с самим собой. Чтобы исключить всякие мосты и тоннели, добавляйте подобные условия:

AND (mains.bridge IS null OR mains.bridge = 'F')

Пересечения нашли с помощью SQL.

Обработка пересечений

Перебираем в цикле найденные пересечения:

List<Map<String, Object>> intersects = findIntersect(tempIds);
for (Map<String, Object> intersect : intersects) {
    // Идентификатор рассматриваемых линии
    Long tempId = ((Number) intersect.get("temps_id")).longValue();
    Long mainId = ((Number) intersect.get("mains_id")).longValue();

    ...

    // Геометрия пересечения
    PGgeometry pgGeom = (PGgeometry) intersect.get("intersects");
    Geometry geom = pgGeom.getGeometry();

    switch (geom.getTypeString()) {
        ...
    }
}

Здесь всё зависит от того, какого типа геометрия пересечения, подробнее они будут разобраны ниже, в примерах. Но всё сводится к одной цели - иметь точки с одинаковыми координатами на месте пересечения.

Модификация линий

Найдя факт пересечения линий, все эти линии необходимо модифицировать создав в них точки на месте пересечения.

Линия представляет собой массив точек, какую точку вставить мы уже знает, - точку пересечения, осталось найти место в массиве куда вставлять.

Зная координаты точки пересечения, мы можем воспользоваться функцией ST_LineLocatePoint, которая возвращает значение с плавающей точкой от 0 до 1, представляющее местоположение точки на линии:

String sql = String.format("SELECT ST_LineLocatePoint(geom, ?) FROM %s WHERE gid = %d", layerName, lineId);
double part = jdbcTemplate.queryForObject(sql, Double.class, new PGgeometry(intersectPoint));

Теперь нужно понять сколько точек в массиве располагается на этом участке, для этого воспользуемся ST_NumPoints:

int pointCount = 1;
if (part != 0) {
    // Количество точек в этой части линии
    sql = String.format("SELECT ST_NumPoints(ST_LineSubstring(geom, 0, %s)) FROM %s WHERE gid = %d", part + "", layerName, lineId);
    pointCount = jdbcTemplate.queryForObject(sql, Integer.class);
}

Теперь мы знает точку, после которой необходимо вставить найденную точку пересечения, при условии что координаты этих точек не совпадают, Для вставки воспользуемся функцией ST_AddPoint:

Point existPoint = tempWay.getPoints()[pointCount - 1];
if (existPoint.x != intersectPoint.x || existPoint.y != intersectPoint.y) {
    // Если отсутствует, - то создать
    sql = String.format("UPDATE %s SET geom = ST_AddPoint(geom, ?, %d) WHERE gid = %d", layerName, pointCount - 1, lineId);
    jdbcTemplate.update(sql, new PGgeometry(intersectPoint));
}

Здесь tempWay - это полученная из БД линия, чтобы ещё раз убедиться что координаты точки в указанной позиции не совпадают с добавляемой точкой пересечения.

Получение tempWay:

sql = String.format("SELECT geom FROM %s WHERE gid = %d", layerName, lineId);
LineString tempWay = (LineString) jdbcTemplate.queryForObject(sql, PGgeometry.class).getGeometry();

Теперь рассмотрим несколько примеров.

Примеры

Данные, для моделируемых ситуаций я выложил в репозиторий GitHub Tkachenko-Ivan/shape-example-graphhopper, здесь они сохранены в shape-файлы, в README представлены схематичные иллюстрации содержимого, и дано текстовое представление данных. Текстовое представление можно использовать чтобы не грузить shape, а создать линии сразу в БД, с помощью ST_LineFromText, например:

INSERT INTO road_temp (gid,geom) VALUES (63,ST_LineFromText('LINESTRING (66.08940600324757 57.261858384708496, 66.09133689803114 57.26600914483714)',4326))

Пересекающиеся линии

Сначала добавим две линии, которые пересекают одну из существующих линий, и пересекаются между собой. Точки, на местах пересечения не созданы - необходимо их создать. Например добавление 1 и 3 к линии 2.

Пересекающиеся линии

Мы должны обработать новые линии и создать точки на местах пересечений, при том, как на месте пересечений двух новых линий между собой, так и на месте пересечения с уже добавленной ранее линией.

Если линии пересекаются, то точки, на местах пересечений, должны быть добавлены в обе линии:

case "POINT" -> {
    // Модифицируем временную линию
    lineModificate(tempId, (Point) geom);
    // Модифицируем постоянную линию
    lineModificate(mainId, (Point) geom);

Как хранить сеть дорог в БД для построения маршрута?

Оглавление

Как это работает?

GraphHopperPostgis - фасад для работы с графом дорог

Результат

Как это использовать?

Подготовка данных

Индексирование и построение маршрута

Как обрабатывать появление новых данных?

Поиск пересечений

Обработка пересечений

Модификация линий

Примеры

Пересекающиеся линии