pgr_extractVertices – Propuesto

pgr_extractVertices — Extrae la información de los vértices

Advertencia

Funciones propuestas para la próxima versión mayor.

  • No están oficialmente en la versión actual.

  • Es probable que oficialmente formen parte del próximo lanzamiento:

    • Las funciones hacen uso de ENTEROS y FLOTANTES

    • Probablemente el nombre no cambie. (Pero todavía puede)

    • Es posible que la firma no cambie. (Pero todavía puede)

    • Probablemente la funcionalidad no cambie. (Pero todavía puede)

    • Se han hecho pruebas con pgTap. Pero tal vez se necesiten más.

    • Es posible que la documentación necesite un refinamiento.

Disponibilidad

  • Versión 3.3.0

    • Clasicado como función propuesta

  • Versión 3.0.0

    • Nueva función experimental

Descripción

Esta es una función auxiliar para extraer la información de vértices del conjunto de aristas de un grafo.

  • Cuando se proporciona el identificador de arista, también se calcularán las aristas de entrada y salida

Firmas

pgr_extractVertices(SQL de aristas, [dryrun])
REGRESA CONJUNTO DE (id, in_edges, out_edges, x, y, geom)
OR EMTPY SET
Ejemplo:

Extraer la información del vértice

SELECT  * FROM pgr_extractVertices(
  'SELECT id, geom FROM edges');
 id | in_edges | out_edges |       x        |  y  |                    geom
----+----------+-----------+----------------+-----+--------------------------------------------
  1 |          | {6}       |              0 |   2 | 010100000000000000000000000000000000000040
  2 |          | {17}      |            0.5 | 3.5 | 0101000000000000000000E03F0000000000000C40
  3 | {6}      | {7}       |              1 |   2 | 0101000000000000000000F03F0000000000000040
  4 | {17}     |           | 1.999999999999 | 3.5 | 010100000068EEFFFFFFFFFF3F0000000000000C40
  5 |          | {1}       |              2 |   0 | 010100000000000000000000400000000000000000
  6 | {1}      | {2,4}     |              2 |   1 | 01010000000000000000000040000000000000F03F
  7 | {4,7}    | {8,10}    |              2 |   2 | 010100000000000000000000400000000000000040
  8 | {10}     | {12,14}   |              2 |   3 | 010100000000000000000000400000000000000840
  9 | {14}     |           |              2 |   4 | 010100000000000000000000400000000000001040
 10 | {2}      | {3,5}     |              3 |   1 | 01010000000000000000000840000000000000F03F
 11 | {5,8}    | {9,11}    |              3 |   2 | 010100000000000000000008400000000000000040
 12 | {11,12}  | {13}      |              3 |   3 | 010100000000000000000008400000000000000840
 13 |          | {18}      |            3.5 | 2.3 | 01010000000000000000000C406666666666660240
 14 | {18}     |           |            3.5 |   4 | 01010000000000000000000C400000000000001040
 15 | {3}      | {16}      |              4 |   1 | 01010000000000000000001040000000000000F03F
 16 | {9,16}   | {15}      |              4 |   2 | 010100000000000000000010400000000000000040
 17 | {13,15}  |           |              4 |   3 | 010100000000000000000010400000000000000840
(17 rows)

Parámetros

Parámetro

Tipo

Descripción

SQL de aristas

TEXT

SQL de aristas como se describe a continuación

Parámetros opcionales

Parámetro

Tipo

x Defecto

Descripción

dryrun

BOOLEAN

false

  • Cuando verdadero, no procesar y recibir un AVISO de la consulta resultante.

Consultas Internas

SQL aristas

Cuando se conoce la geometría de línea

Columna

Tipo

Descripción

id

BIGINT

(Opcional) identificador de la arista.

geom

LINESTRING

Geometría de la arista.

Esta consulta interna tiene prioridad sobre las dos consultas internas siguientes, por lo que se omiten otras columnas cuando aparece la columna “”geom””.

  • Columnas ignoradas:

    • startpoint

    • endpoint

    • source

    • target

Cuando se conoce la geometría de vértices

Para utilizar esta consulta interna, la columna geom no debe formar parte del conjunto de columnas.

Columna

Tipo

Descripción

id

BIGINT

(Opcional) identificador de la arista.

startpoint

POINT

Geometría POINT del vértice inicial.

endpoint

POINT

Geometría POINT del vértice final.

Esta consulta interna tiene prioridad sobre la siguiente consulta interna, por lo que otras columnas son ignoradas cuando aparecen las columnas startpoint y endpoint.

  • Columnas ignoradas:

    • source

    • target

Cuando se conocen identificadores de vértices

Para utilizar esta consulta interna, las columnas geom, startpoint y endpoint no deben formar parte del conjunto de columnas.

Columna

Tipo

Descripción

id

BIGINT

(Opcional) identificador de la arista.

source

ANY-INTEGER

Identificador del primer vértice de la arista.

target

ANY-INTEGER

Identificador del segundo vértice de la arista.

Columnas de Resultados

Columna

Tipo

Descripción

id

BIGINT

Identificador de vértice

in_edges

BIGINT[]

Arreglo de identificadores de las aristas que tienen el vértice id como primer punto final.

  • NULL When the id no forma parte de la consulta interna

out_edges

BIGINT[]

Arreglo de identificadores de las aristas que tienen el vértice id como segundo punto final.

  • NULL When the id no forma parte de la consulta interna

x

FLOAT

Valor X de la geometría del punto

  • NULL Cuando no se proporciona geometría

y

FLOAT

Valor X de la geometría del punto

  • NULL Cuando no se proporciona geometría

geom

POINT

Geometría del punto

  • NULL Cuando no se proporciona geometría

Ejemplos Adicionales

Ejecución de Dryrun

Para obtener la consulta generada que se usa para obtener la información de vértices, utilice dryrun := true.

Los resultados se pueden usar como código base para realizar un refinamiento basado en las necesidades de desarrollo de back-end.

SELECT  * FROM pgr_extractVertices(
  'SELECT id, geom FROM edges',
  dryrun => true);
NOTICE:
        WITH

        main_sql AS (
          SELECT id, geom FROM edges
        ),

        the_out AS (
          SELECT id::BIGINT AS out_edge, ST_StartPoint(geom) AS geom
          FROM main_sql
        ),

        agg_out AS (
          SELECT array_agg(out_edge ORDER BY out_edge) AS out_edges, ST_x(geom) AS x, ST_Y(geom) AS y, geom
          FROM the_out
          GROUP BY geom
        ),

        the_in AS (
          SELECT id::BIGINT AS in_edge, ST_EndPoint(geom) AS geom
          FROM main_sql
        ),

        agg_in AS (
          SELECT array_agg(in_edge ORDER BY in_edge) AS in_edges, ST_x(geom) AS x, ST_Y(geom) AS y, geom
          FROM the_in
          GROUP BY geom
        ),

        the_points AS (
          SELECT in_edges, out_edges, coalesce(agg_out.geom, agg_in.geom) AS geom
          FROM agg_out
          FULL OUTER JOIN agg_in USING (x, y)
        )

        SELECT row_number() over(ORDER BY ST_X(geom), ST_Y(geom)) AS id, in_edges, out_edges, ST_X(geom), ST_Y(geom), geom
        FROM the_points;
 id | in_edges | out_edges | x | y | geom
----+----------+-----------+---+---+------
(0 rows)

Creación de una topología de ruteo

Asegurarse de que la base de datos no tiene vertices_table

DROP TABLE IF EXISTS vertices_table;
NOTICE:  table "vertices_table" does not exist, skipping
DROP TABLE

Limpieza de las columnas de la topología de ruteo que se creará

UPDATE edges
SET source = NULL, target = NULL,
x1 = NULL, y1 = NULL,
x2 = NULL, y2 = NULL;
UPDATE 18

Crear la tabla de vértices

  • When the LINESTRING has a SRID then use geom::geometry(POINT, <SRID>)

  • For big edge tables that are been prepared,

    • Create it as UNLOGGED and

    • After the table is created ALTER TABLE .. SET LOGGED

SELECT  * INTO vertices_table
FROM pgr_extractVertices('SELECT id, geom FROM edges ORDER BY id');
SELECT 17

Inspeccionar la tabla de vértices

SELECT *
FROM vertices_table;
 id | in_edges | out_edges |       x        |  y  |                    geom
----+----------+-----------+----------------+-----+--------------------------------------------
  1 |          | {6}       |              0 |   2 | 010100000000000000000000000000000000000040
  2 |          | {17}      |            0.5 | 3.5 | 0101000000000000000000E03F0000000000000C40
  3 | {6}      | {7}       |              1 |   2 | 0101000000000000000000F03F0000000000000040
  4 | {17}     |           | 1.999999999999 | 3.5 | 010100000068EEFFFFFFFFFF3F0000000000000C40
  5 |          | {1}       |              2 |   0 | 010100000000000000000000400000000000000000
  6 | {1}      | {2,4}     |              2 |   1 | 01010000000000000000000040000000000000F03F
  7 | {4,7}    | {8,10}    |              2 |   2 | 010100000000000000000000400000000000000040
  8 | {10}     | {12,14}   |              2 |   3 | 010100000000000000000000400000000000000840
  9 | {14}     |           |              2 |   4 | 010100000000000000000000400000000000001040
 10 | {2}      | {3,5}     |              3 |   1 | 01010000000000000000000840000000000000F03F
 11 | {5,8}    | {9,11}    |              3 |   2 | 010100000000000000000008400000000000000040
 12 | {11,12}  | {13}      |              3 |   3 | 010100000000000000000008400000000000000840
 13 |          | {18}      |            3.5 | 2.3 | 01010000000000000000000C406666666666660240
 14 | {18}     |           |            3.5 |   4 | 01010000000000000000000C400000000000001040
 15 | {3}      | {16}      |              4 |   1 | 01010000000000000000001040000000000000F03F
 16 | {9,16}   | {15}      |              4 |   2 | 010100000000000000000010400000000000000040
 17 | {13,15}  |           |              4 |   3 | 010100000000000000000010400000000000000840
(17 rows)

Creación de la topología de ruteo en la tabla de aristas

Actualizar de la información de source

WITH
out_going AS (
  SELECT id AS vid, unnest(out_edges) AS eid, x, y
  FROM vertices_table
)
UPDATE edges
SET source = vid, x1 = x, y1 = y
FROM out_going WHERE id = eid;
UPDATE 18

Actualización de la información de target

WITH
in_coming AS (
  SELECT id AS vid, unnest(in_edges) AS eid, x, y
  FROM vertices_table
)
UPDATE edges
SET target = vid, x2 = x, y2 = y
FROM in_coming WHERE id = eid;
UPDATE 18

Inspección de la topología de ruteo

SELECT id, source, target, x1, y1, x2, y2
FROM edges ORDER BY id;
 id | source | target | x1  | y1  |       x2       | y2
----+--------+--------+-----+-----+----------------+-----
  1 |      5 |      6 |   2 |   0 |              2 |   1
  2 |      6 |     10 |   2 |   1 |              3 |   1
  3 |     10 |     15 |   3 |   1 |              4 |   1
  4 |      6 |      7 |   2 |   1 |              2 |   2
  5 |     10 |     11 |   3 |   1 |              3 |   2
  6 |      1 |      3 |   0 |   2 |              1 |   2
  7 |      3 |      7 |   1 |   2 |              2 |   2
  8 |      7 |     11 |   2 |   2 |              3 |   2
  9 |     11 |     16 |   3 |   2 |              4 |   2
 10 |      7 |      8 |   2 |   2 |              2 |   3
 11 |     11 |     12 |   3 |   2 |              3 |   3
 12 |      8 |     12 |   2 |   3 |              3 |   3
 13 |     12 |     17 |   3 |   3 |              4 |   3
 14 |      8 |      9 |   2 |   3 |              2 |   4
 15 |     16 |     17 |   4 |   2 |              4 |   3
 16 |     15 |     16 |   4 |   1 |              4 |   2
 17 |      2 |      4 | 0.5 | 3.5 | 1.999999999999 | 3.5
 18 |     13 |     14 | 3.5 | 2.3 |            3.5 |   4
(18 rows)

_images/Fig1-originalData.png

Topología generada

Crossing edges

To get the crossing edges:

SELECT a.id, b.id
FROM edges AS a, edges AS b
WHERE a.id < b.id AND st_crosses(a.geom, b.geom);
 id | id
----+----
 13 | 18
(1 row)

_images/crossing_edges.png

That information is correct, for example, when in terms of vehicles, is it a tunnel or bride crossing over another road.

It might be incorrect, for example:

  1. When it is actually an intersection of roads, where vehicles can make turns.

  2. When in terms of electrical lines, the electrical line is able to switch roads even on a tunnel or bridge.

When it is incorrect, it needs fixing:

  1. For vehicles and pedestrians

    • If the data comes from OSM and was imported to the database using osm2pgrouting, the fix needs to be done in the OSM portal and the data imported again.

    • In general when the data comes from a supplier that has the data prepared for routing vehicles, and there is a problem, the data is to be fixed from the supplier

  2. For very specific applications

    • The data is correct when from the point of view of routing vehicles or pedestrians.

    • The data needs a local fix for the specific application.

Once analyzed one by one the crossings, for the ones that need a local fix, the edges need to be split.

SELECT ST_AsText((ST_Dump(ST_Split(a.geom, b.geom))).geom)
FROM edges AS a, edges AS b
WHERE a.id = 13 AND b.id = 18
UNION
SELECT ST_AsText((ST_Dump(ST_Split(b.geom, a.geom))).geom)
FROM edges AS a, edges AS b
WHERE a.id = 13 AND b.id = 18;
         st_astext
---------------------------
 LINESTRING(3.5 2.3,3.5 3)
 LINESTRING(3 3,3.5 3)
 LINESTRING(3.5 3,4 3)
 LINESTRING(3.5 3,3.5 4)
(4 rows)

The new edges need to be added to the edges table, the rest of the attributes need to be updated in the new edges, the old edges need to be removed and the routing topology needs to be updated.

Adding split edges

For each pair of crossing edges a process similar to this one must be performed.

The columns inserted and the way are calculated are based on the application. For example, if the edges have a trait name, then that column is to be copied.

Para llos cálculos de pgRouting

  • factor based on the position of the intersection of the edges can be used to adjust the cost and reverse_cost columns.

  • Capacity information, used on the Flow - Familia de funciones functions does not need to change when splitting edges.

WITH
first_edge AS (
  SELECT (ST_Dump(ST_Split(a.geom, b.geom))).path[1],
    (ST_Dump(ST_Split(a.geom, b.geom))).geom,
    ST_LineLocatePoint(a.geom,ST_Intersection(a.geom,b.geom)) AS factor
  FROM edges AS a, edges AS b
  WHERE a.id = 13 AND b.id = 18),
first_segments AS (
  SELECT path, first_edge.geom,
    capacity, reverse_capacity,
    CASE WHEN path=1 THEN factor * cost
         ELSE (1 - factor) * cost END AS cost,
    CASE WHEN path=1 THEN factor * reverse_cost
         ELSE (1 - factor) * reverse_cost END AS reverse_cost
  FROM first_edge , edges WHERE id = 13),
second_edge AS (
  SELECT (ST_Dump(ST_Split(b.geom, a.geom))).path[1],
    (ST_Dump(ST_Split(b.geom, a.geom))).geom,
    ST_LineLocatePoint(b.geom,ST_Intersection(a.geom,b.geom)) AS factor
  FROM edges AS a, edges AS b
  WHERE a.id = 13 AND b.id = 18),
second_segments AS (
  SELECT path, second_edge.geom,
    capacity, reverse_capacity,
    CASE WHEN path=1 THEN factor * cost
         ELSE (1 - factor) * cost END AS cost,
    CASE WHEN path=1 THEN factor * reverse_cost
         ELSE (1 - factor) * reverse_cost END AS reverse_cost
  FROM second_edge , edges WHERE id = 18),
all_segments AS (
  SELECT * FROM first_segments
  UNION
  SELECT * FROM second_segments)
INSERT INTO edges
  (capacity, reverse_capacity,
    cost, reverse_cost,
    x1, y1, x2, y2,
    geom)
(SELECT capacity, reverse_capacity, cost, reverse_cost,
  ST_X(ST_StartPoint(geom)), ST_Y(ST_StartPoint(geom)),
  ST_X(ST_EndPoint(geom)), ST_Y(ST_EndPoint(geom)),
  geom
  FROM all_segments);
INSERT 0 4

Añadiendo nuevos vértices

After adding all the split edges required by the application, the newly created vertices need to be added to the vertices table.

INSERT INTO vertices (in_edges, out_edges, x, y, geom)
(SELECT nv.in_edges, nv.out_edges, nv.x, nv.y, nv.geom
FROM pgr_extractVertices('SELECT id, geom FROM edges') AS nv
LEFT JOIN vertices AS v USING(geom) WHERE v.geom IS NULL);
INSERT 0 1

Actualizar la topología de aristas

/* -- set the source information */
UPDATE edges AS e
SET source = v.id
FROM vertices AS v
WHERE source IS NULL AND ST_StartPoint(e.geom) = v.geom;
UPDATE 4
/* -- set the target information */
UPDATE edges AS e
SET target = v.id
FROM vertices AS v
WHERE target IS NULL AND ST_EndPoint(e.geom) = v.geom;
UPDATE 4

Removing the surplus edges

Once all significant information needed by the application has been transported to the new edges, then the crossing edges can be deleted.

DELETE FROM edges WHERE id IN (13, 18);
DELETE 2

There are other options to do this task, like creating a view, or a materialized view.

Actializar la topología de vértices

To keep the graph consistent, the vertices topology needs to be updated

UPDATE vertices AS v SET
in_edges = nv.in_edges, out_edges = nv.out_edges
FROM (SELECT * FROM pgr_extractVertices('SELECT id, geom FROM edges')) AS nv
WHERE v.geom = nv.geom;
UPDATE 18

Checking for crossing edges

There are no crossing edges on the graph.

SELECT a.id, b.id
FROM edges AS a, edges AS b
WHERE a.id < b.id AND st_crosses(a.geom, b.geom);
 id | id
----+----
(0 rows)

Graphs without geometries

Using this table design for this example:

CREATE TABLE wiki (
  id SERIAL,
  source INTEGER,
  target INTEGER,
  cost INTEGER);
CREATE TABLE

Insert the data

INSERT INTO wiki (source, target, cost) VALUES
(1, 2, 7),  (1, 3, 9), (1, 6, 14),
(2, 3, 10), (2, 4, 15),
(3, 6, 2),  (3, 4, 11),
(4, 5, 6),
(5, 6, 9);
INSERT 0 9

Find the shortest path

To solve this example pgr_dijkstra is used:

SELECT * FROM pgr_dijkstra(
  'SELECT id, source, target, cost FROM wiki',
  1, 5, false);
 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
   1 |        1 |    1 |    2 |    9 |        0
   2 |        2 |    3 |    6 |    2 |        9
   3 |        3 |    6 |    9 |    9 |       11
   4 |        4 |    5 |   -1 |    0 |       20
(4 rows)

To go from \(1\) to \(5\) the path goes thru the following vertices: \(1 \rightarrow 3 \rightarrow 6 \rightarrow 5\)

graph G {
 rankdir="LR";
 1 [color="red"];
 5 [color="green"];
 1 -- 2 [label="  (7)"];
 5 -- 6 [label="  (9)", color="blue"];
 1 -- 3 [label="  (9)", color="blue"];
 1 -- 6 [label="  (14)"];
 2 -- 3 [label="  (10)"];
 2 -- 4 [label="  (13)"];
 3 -- 4 [label="  (11)"];
 3 -- 6 [label="  (2)", color="blue"];
 4 -- 5 [label="  (6)"];
}

Información de vertices

To obtain the vertices information, use pgr_extractVertices – Propuesto

SELECT id, in_edges, out_edges
FROM pgr_extractVertices('SELECT id, source, target FROM wiki');
 id | in_edges | out_edges
----+----------+-----------
  3 | {2,4}    | {6,7}
  5 | {8}      | {9}
  4 | {5,7}    | {8}
  2 | {1}      | {4,5}
  1 |          | {1,2,3}
  6 | {3,6,9}  |
(6 rows)

Ver también

Índices y tablas