Supported versions:

`pgr_findCloseEdges`¶

pgr_findCloseEdges - Finds the close edges to a point geometry.

_images/boost-inside.jpeg — Adentro: Boost Graph¶

Disponibilidad

Versión 3.4.0
- New proposed signatures:
  - pgr_findCloseEdges (One point)
  - pgr_findCloseEdges (Many points)

Descripción¶

pgr_findCloseEdges - An utility function that finds the closest edge to a point geometry.

The geometries must be in the same coordinate system (have the same SRID).
The code to do the calculations can be obtained for further specific adjustments needed by the application.
EMTPY SET is returned on dryrun executions

Firmas¶

Resumen

pgr_findCloseEdges(Edges SQL, punto, tolerancia, [options])
pgr_findCloseEdges(Edges SQL, puntos, tolerancia, [options])
options: [cap, partial, dryrun]

REGRESA CONJUNTO DE (edge_id, fraction, side, distance, geom, edge)

OR EMPTY SET

One point¶

pgr_findCloseEdges(Edges SQL, punto, tolerancia, [options])

options: [cap, partial, dryrun]

REGRESA CONJUNTO DE (edge_id, fraction, side, distance, geom, edge)

OR EMPTY SET

Ejemplo:: Con valores predeterminados

Default: cap => 1
- Maximum one row answer.
Default: partial => true
- With less calculations as possible.
Default: dryrun => false
- Process query
Returns
- values on edge_id, fraction, side columns.
- NULL on distance, geom, edge columns.

SELECT  *
FROM pgr_findCloseEdges(
  $$SELECT id, geom FROM edges$$,
  (SELECT geom FROM pointsOfInterest WHERE pid = 5),
  0.5);
 edge_id | fraction | side | distance | geom | edge
---------+----------+------+----------+------+------
       5 |      0.8 | l    |          |      |
(1 row)

Many points¶

pgr_findCloseEdges(Edges SQL, puntos, tolerancia, [options])

options: [cap, partial, dryrun]

REGRESA CONJUNTO DE (edge_id, fraction, side, distance, geom, edge)

OR EMPTY SET

Ejemplo:: Find at most \(2\) edges close to all vertices on the points of interest table.

One answer per point, as small as possible.

SELECT edge_id, round(fraction::numeric, 2) AS fraction, side, ST_AsText(geom) AS original_point
FROM pgr_findCloseEdges(
  $$SELECT id, geom FROM edges$$,
  (SELECT array_agg(geom) FROM pointsOfInterest),
  0.5);
 edge_id | fraction | side | original_point
---------+----------+------+----------------
       1 |     0.40 | l    | POINT(1.8 0.4)
       6 |     0.30 | r    | POINT(0.3 1.8)
      12 |     0.60 | l    | POINT(2.6 3.2)
      15 |     0.40 | r    | POINT(4.2 2.4)
       5 |     0.80 | l    | POINT(2.9 1.8)
       4 |     0.70 | r    | POINT(2.2 1.7)
(6 rows)

Columns edge_id, fraction, side and geom are returned with values.

geom contains the original point geometry to assist on deterpartialing to which point geometry the row belongs to.

Parámetros¶

Parámetro	Tipo	Descripción
SQL de aristas	`TEXT`	SQL de aristas descritas más adelante.
punto	`POINT`	The point geometry
puntos	`POINT[]`	An array of point geometries
tolerancia	`FLOAT`	Max distance between geometries

Parámetros opcionales¶

Parámetro	Tipo	x Defecto	Descripción
`cap`	`INTEGER`	\(1\)	Limit output rows
`partial`	`BOOLEAN`	`true`	When `true` only columns needed for withPoints- Categoría are calculated. When `false` all columns are calculated
`dryrun`	`BOOLEAN`	`false`	When `false` calculations are performed. When `true` calculations are not performed and the query to do the calculations is exposed in a PostgreSQL `NOTICE`.

Consultas Internas¶

SQL aristas¶

Columna	Tipo	Descripción
`id`	ENTEROS	Identificador de la arista.
`geom`	`geometry`	The `LINESTRING` geometry of the edge.

Columnas de Resultados¶

Regresa conjunto de (edge_id, fraction, side, distance, geom, edge)

Columna	Tipo	Descripción
`edge_id`	`BIGINT`	Identificador de la arista. When \(cap = 1\), it is the closest edge.
`fraction`	`FLOAT`	Value in <0,1> that indicates the relative postition from the first end-point of the edge.
`side`	`CHAR`	Value in `[r, l]` indicating if the point is: In the right `r`. In the left `l`. When the point is on the line it is considered to be on the right.
`distance`	`FLOAT`	Distance from point to edge. `NULL` when `cap = 1` on the One point signature
`geom`	`geometry`	`POINT` geometry One Point: Contains the point on the edge that is `fraction` away from the starting point of the edge. Many Points: Contains the corresponding original point
`edge`	`geometry`	`LINESTRING` geometry from the original point to the closest point of the edge with identifier `edge_id`

One point results

The green nodes is the original point
The geometry geom is a point on the \(sp \rightarrow ep\) edge.
The geometry edge is a line that connects the original point with geom

digraph G {
splines=false;
subgraph cluster0 {
point [shape=circle;style=filled;color=green];
geom [shape=point;color=black;size=0];
sp, ep;

edge[weight=0];
point -> geom [dir=none; penwidth=0, color=red];
edge[weight=2];
sp -> geom -> ep [dir=none;penwidth=3 ];

{rank=same; point, geom}
}

subgraph cluster1 {
point1 [shape=circle;style=filled;color=green;label=point];
geom1 [shape=point;color=deepskyblue; xlabel="geom"; width=0.3];
sp1 [label=sp]; ep1 [label=ep];

edge[weight=0];
point1 -> geom1 [weight=0, penwidth=3, color=red,
label="edge"];
edge[weight=2];
sp1 -> geom1 -> ep1 [dir=none;weight=1, penwidth=3 ];

geom1 -> point1 [dir=none;weight=0, penwidth=0, color=red];
{rank=same; point1, geom1}
}
}

Many point results

The green nodes are the original points
The geometry geom, marked as g1 and g2 are the original points
The geometry edge, marked as edge1 and edge2 is a line that connects the original point with the closest point on the \(sp \rightarrow ep\) edge.

digraph G {
splines = false;
subgraph cluster0 {
p1 [shape=circle;style=filled;color=green];
g1 [shape=point;color=black;size=0];
g2 [shape=point;color=black;size=0];
sp, ep;
p2 [shape=circle;style=filled;color=green];

sp -> g1 [dir=none;weight=1, penwidth=3 ];
g1 -> g2 [dir=none;weight=1, penwidth=3 ];
g2 -> ep [weight=1, penwidth=3 ];

g2 -> p2 [dir=none;weight=0, penwidth=0, color=red, partiallen=3];
p1 -> g1 [dir=none;weight=0, penwidth=0, color=red, partiallen=3];
p1 -> {g1, g2} [dir=none;weight=0, penwidth=0, color=red;]

{rank=same; p1; g1}
{rank=same; p2; g2}
}
subgraph cluster1 {
p3 [shape=circle;style=filled;color=deepskyblue;label=g1];
g3 [shape=point;color=black;size=0];
g4 [shape=point;color=black;size=0];
sp1 [label=sp]; ep1 [label=ep];
p4 [shape=circle;style=filled;color=deepskyblue;label=g2];

sp1 -> g3 [dir=none;weight=1, penwidth=3 ];
g3 -> g4 [dir=none;weight=1, penwidth=3,len=10];
g4 -> ep1 [weight=1, penwidth=3, len=10];

g4 -> p4 [dir=back;weight=0, penwidth=3, color=red, partiallen=3,
label="edge2"];
p3 -> g3 [weight=0, penwidth=3, color=red, partiallen=3,
label="edge1"];
p3 -> {g3, g4} [dir=none;weight=0, penwidth=0, color=red];

{rank=same; p3; g3}
{rank=same; p4; g4}
}
}

Ejemplos Adicionales¶

One point examples ¶

At most two answers ¶

cap => 2
- Maximum two row answer.
Default: partial => true
- With less calculations as possible.
Default: dryrun => false
- Process query

SELECT *
FROM pgr_findCloseEdges(
  $$SELECT id, geom FROM edges$$,
  (SELECT geom FROM pointsOfInterest WHERE pid = 5),
  0.5, cap => 2);
 edge_id |      fraction      | side |      distance       | geom | edge
---------+--------------------+------+---------------------+------+------
       5 |                0.8 | l    | 0.10000000000000009 |      |
       8 | 0.8999999999999999 | r    | 0.19999999999999996 |      |
(2 rows)

Understanding the result

NULL on geom, edge
edge_id identifier of the edge close to the original point
- Two edges are withing \(0.5\) distance units from the original point: \({5, 8}\)
For edge \(5\):
- fraction: The closest point from the original point is at the \(0.8\) fraction of the edge \(5\).
- side: The original point is located to the left side of edge \(5\).
- distance: The original point is located \(0.1\) length units from edge \(5\).
For edge \(8\):
- fraction: The closest point from the original point is at the \(0.89..\) fraction of the edge \(8\).
- side: The original point is located to the right side of edge \(8\).
- distance: The original point is located \(0.19..\) length units from edge \(8\).

One answer, all columns ¶

Default: cap => 1
- Maximum one row answer.
partial => false
- Calculate all columns
Default: dryrun => false
- Process query

SELECT edge_id, round(fraction::numeric, 2) AS fraction, side, round(distance::numeric, 3) AS distance,
  ST_AsText(geom) AS new_point,
  ST_AsText(edge) AS original_to_new_point
FROM pgr_findCloseEdges(
  $$SELECT id, geom FROM edges$$,
  (SELECT geom FROM pointsOfInterest WHERE pid = 5),
  0.5, partial => false);
 edge_id | fraction | side | distance |  new_point   |   original_to_new_point
---------+----------+------+----------+--------------+---------------------------
       5 |     0.80 | l    |    0.100 | POINT(3 1.8) | LINESTRING(2.9 1.8,3 1.8)
(1 row)

Understanding the result

edge_id identifier of the edge closest to the original point
- From all edges within \(0.5\) distance units from the original point: \({5}\) is the closest one.
For edge \(5\):
- fraction: The closest point from the original point is at the \(0.8\) fraction of the edge \(5\).
- side: The original point is located to the left side of edge \(5\).
- distance: The original point is located \(0.1\) length units from edge \(5\).
- geom: Contains the geometry of the closest point on edge \(5\) from the original point.
- edge: Contains the LINESTRING geometry of the original point to the closest point on on edge \(5\) geom

At most two answers with all columns ¶

cap => 2
- Maximum two row answer.
partial => false
- Calculate all columns
Default: dryrun => false
- Process query

SELECT edge_id, round(fraction::numeric, 2) AS fraction, side, round(distance::numeric, 3) AS distance,
  ST_AsText(geom) AS new_point,
  ST_AsText(edge) AS original_to_new_point
FROM pgr_findCloseEdges(
  $$SELECT id, geom FROM edges$$,
  (SELECT geom FROM pointsOfInterest WHERE pid = 5),
  0.5, cap => 2, partial => false);
 edge_id | fraction | side | distance |  new_point   |   original_to_new_point
---------+----------+------+----------+--------------+---------------------------
       5 |     0.80 | l    |    0.100 | POINT(3 1.8) | LINESTRING(2.9 1.8,3 1.8)
       8 |     0.90 | r    |    0.200 | POINT(2.9 2) | LINESTRING(2.9 1.8,2.9 2)
(2 rows)

Understanding the result:

edge_id identifier of the edge close to the original point
- Two edges are withing \(0.5\) distance units from the original point: \({5, 8}\)
For edge \(5\):
- fraction: The closest point from the original point is at the \(0.8\) fraction of the edge \(5\).
- side: The original point is located to the left side of edge \(5\).
- distance: The original point is located \(0.1\) length units from edge \(5\).
- geom: Contains the geometry of the closest point on edge \(5\) from the original point.
- edge: Contains the LINESTRING geometry of the original point to the closest point on on edge \(5\) geom
For edge \(8\):
- fraction: The closest point from the original point is at the \(0.89..\) fraction of the edge \(8\).
- side: The original point is located to the right side of edge \(8\).
- distance: The original point is located \(0.19..\) length units from edge \(8\).
- geom: Contains the geometry of the closest point on edge \(8\) from the original point.
- edge: Contains the LINESTRING geometry of the original point to the closest point on on edge \(8\) geom

One point dry run execution ¶

Returns EMPTY SET.
partial => true
- Is ignored
- Because it is a dry run excecution, the code for all calculations are shown on the PostgreSQL NOTICE.
dryrun => true
- Do not process query
- Generate a PostgreSQL NOTICE with the code used to calculate all columns
  - cap and original point are used in the code

SELECT *
FROM pgr_findCloseEdges(
  $$SELECT id, geom FROM edges$$,
  (SELECT geom FROM pointsOfInterest WHERE pid = 5),
  0.5,
  dryrun => true);
NOTICE:
    WITH
    edges_sql AS (SELECT id, geom FROM edges),
    point_sql AS (SELECT '01010000003333333333330740CDCCCCCCCCCCFC3F'::geometry AS point)

    SELECT
      id::BIGINT AS edge_id,
      ST_LineLocatePoint(geom, point) AS fraction,
      CASE WHEN ST_Intersects(ST_Buffer(geom, 0.5, 'side=right endcap=flat'), point)
           THEN 'r'
           ELSE 'l' END::CHAR AS side,

        geom <-> point AS distance,
        ST_ClosestPoint(geom, point) AS new_point,
        ST_MakeLine(point, ST_ClosestPoint(geom, point)) AS new_line

    FROM  edges_sql, point_sql
    WHERE ST_DWithin(geom,  point, 0.5)
    ORDER BY geom <-> point LIMIT 1

 edge_id | fraction | side | distance | geom | edge
---------+----------+------+----------+------+------
(0 rows)

Many points examples ¶

At most two answers per point ¶

cap => 2
- Maximum two row answer.
Default: partial => true
- With less calculations as possible.
Default: dryrun => false
- Process query

SELECT edge_id, round(fraction::numeric, 2) AS fraction, side, round(distance::numeric, 3) AS distance,
  ST_AsText(geom) AS geom_is_original, edge
FROM pgr_findCloseEdges(
  $$SELECT id, geom FROM edges$$,
  (SELECT array_agg(geom) FROM pointsOfInterest),
  0.5, cap => 2);
 edge_id | fraction | side | distance | geom_is_original | edge
---------+----------+------+----------+------------------+------
       1 |     0.40 | l    |    0.200 | POINT(1.8 0.4)   |
       6 |     0.30 | r    |    0.200 | POINT(0.3 1.8)   |
      12 |     0.60 | l    |    0.200 | POINT(2.6 3.2)   |
      11 |     1.00 | l    |    0.447 | POINT(2.6 3.2)   |
      15 |     0.40 | r    |    0.200 | POINT(4.2 2.4)   |
       9 |     1.00 | l    |    0.447 | POINT(4.2 2.4)   |
       5 |     0.80 | l    |    0.100 | POINT(2.9 1.8)   |
       8 |     0.90 | r    |    0.200 | POINT(2.9 1.8)   |
       4 |     0.70 | r    |    0.200 | POINT(2.2 1.7)   |
       8 |     0.20 | r    |    0.300 | POINT(2.2 1.7)   |
(10 rows)

Understanding the result

NULL on edge
edge_id identifier of the edge close to a original point (geom)
- Two edges at most withing \(0.5\) distance units from each of the original points:
  - For POINT(1.8 0.4) and POINT(0.3 1.8) only one edge was found.
  - For the rest of the points two edges were found.
For point POINT(2.9 1.8)
- Edge \(5\) is before \(8\) therefore edge \(5\) has the shortest distance to POINT(2.9 1.8).
- For edge \(5\):
  - fraction: The closest point from the original point is at the \(0.8\) fraction of the edge \(5\).
  - side: The original point is located to the left side of edge \(5\).
  - distance: The original point is located \(0.1\) length units from edge \(5\).
- For edge \(8\):
  - fraction: The closest point from the original point is at the \(0.89..\) fraction of the edge \(8\).
  - side: The original point is located to the right side of edge \(8\).
  - distance: The original point is located \(0.19..\) length units from edge \(8\).

One answer per point, all columns ¶

Default: cap => 1
- Maximum one row answer.
partial => false
- Calculate all columns
Default: dryrun => false
- Process query

SELECT edge_id, round(fraction::numeric, 2) AS fraction, side, round(distance::numeric, 3) AS distance,
  ST_AsText(geom) AS geom_is_original,
  ST_AsText(edge) AS original_to_new_point
FROM pgr_findCloseEdges(
  $$SELECT id, geom FROM edges$$,
  (SELECT array_agg(geom) FROM pointsOfInterest),
  0.5, partial => false);
 edge_id | fraction | side | distance | geom_is_original |   original_to_new_point
---------+----------+------+----------+------------------+---------------------------
       1 |     0.40 | l    |    0.200 | POINT(1.8 0.4)   | LINESTRING(1.8 0.4,2 0.4)
       6 |     0.30 | r    |    0.200 | POINT(0.3 1.8)   | LINESTRING(0.3 1.8,0.3 2)
      12 |     0.60 | l    |    0.200 | POINT(2.6 3.2)   | LINESTRING(2.6 3.2,2.6 3)
      15 |     0.40 | r    |    0.200 | POINT(4.2 2.4)   | LINESTRING(4.2 2.4,4 2.4)
       5 |     0.80 | l    |    0.100 | POINT(2.9 1.8)   | LINESTRING(2.9 1.8,3 1.8)
       4 |     0.70 | r    |    0.200 | POINT(2.2 1.7)   | LINESTRING(2.2 1.7,2 1.7)
(6 rows)

Understanding the result

edge_id identifier of the edge closest to the original point
- From all edges within \(0.5\) distance units from the original point: \({5}\) is the closest one.
For the original point POINT(2.9 1.8)
- Edge \(5\) is the closest edge to the original point
- fraction: The closest point from the original point is at the \(0.8\) fraction of the edge \(5\).
- side: The original point is located to the left side of edge \(5\).
- distance: The original point is located \(0.1\) length units from edge \(5\).
- geom: Contains the geometry of the original point POINT(2.9 1.8)
- edge: Contains the LINESTRING geometry of the original point (geom) to the closest point on on edge.

Many points dry run execution ¶

Returns EMPTY SET.
partial => true
- Is ignored
- Because it is a dry run excecution, the code for all calculations are shown on the PostgreSQL NOTICE.
dryrun => true
- Do not process query
- Generate a PostgreSQL NOTICE with the code used to calculate all columns
  - cap and original point are used in the code

SELECT *
FROM pgr_findCloseEdges(
  $$SELECT id, geom FROM edges$$,
  (SELECT array_agg(geom) FROM pointsOfInterest),
  0.5,
  dryrun => true);
NOTICE:
WITH
edges_sql AS (SELECT id, geom FROM edges),
point_sql AS (SELECT unnest('{0101000000CDCCCCCCCCCCFC3F9A9999999999D93F:0101000000333333333333D33FCDCCCCCCCCCCFC3F:0101000000CDCCCCCCCCCC04409A99999999990940:0101000000CDCCCCCCCCCC10403333333333330340:01010000003333333333330740CDCCCCCCCCCCFC3F:01010000009A99999999990140333333333333FB3F}'::geometry[]) AS point),
results AS (
  SELECT
    id::BIGINT AS edge_id,
    ST_LineLocatePoint(geom, point) AS fraction,
    CASE WHEN ST_Intersects(ST_Buffer(geom, 0.5, 'side=right endcap=flat'), point)
         THEN 'r'
         ELSE 'l' END::CHAR AS side,
    geom <-> point AS distance,
    point,
    ST_MakeLine(point, ST_ClosestPoint(geom, point)) AS new_line
  FROM  edges_sql, point_sql
  WHERE ST_DWithin(geom, point, 0.5)
  ORDER BY geom <-> point),
prepare_cap AS (
  SELECT row_number() OVER (PARTITION BY point ORDER BY point, distance) AS rn, *
  FROM results)
SELECT edge_id, fraction, side, distance, point, new_line
FROM prepare_cap
WHERE rn <= 1

 edge_id | fraction | side | distance | geom | edge
---------+----------+------+----------+------+------
(0 rows)

Find at most two routes to a given point ¶

Using pgr_withPoints - Propuesto

SELECT * FROM pgr_withPoints(
  $e$ SELECT * FROM edges $e$,
  $p$ SELECT edge_id, round(fraction::numeric, 2) AS fraction, side
      FROM pgr_findCloseEdges(
        $$SELECT id, geom FROM edges$$,
        (SELECT geom FROM pointsOfInterest WHERE pid = 5),
        0.5, cap => 2)
  $p$,
  1, ARRAY[-1, -2]);
 seq | path_seq | end_pid | node | edge | cost | agg_cost
-----+----------+---------+------+------+------+----------
   1 |        1 |      -2 |    1 |    6 |    1 |        0
   2 |        2 |      -2 |    3 |    7 |    1 |        1
   3 |        3 |      -2 |    7 |    8 |  0.9 |        2
   4 |        4 |      -2 |   -2 |   -1 |    0 |      2.9
   5 |        1 |      -1 |    1 |    6 |    1 |        0
   6 |        2 |      -1 |    3 |    7 |    1 |        1
   7 |        3 |      -1 |    7 |    8 |    1 |        2
   8 |        4 |      -1 |   11 |    9 |    1 |        3
   9 |        5 |      -1 |   16 |   16 |    1 |        4
  10 |        6 |      -1 |   15 |    3 |    1 |        5
  11 |        7 |      -1 |   10 |    5 |  0.8 |        6
  12 |        8 |      -1 |   -1 |   -1 |    0 |      6.8
(12 rows)

A point of interest table ¶

Handling points outside the graph.

Puntos de interés ¶

Some times the applications work «on the fly» starting from a location that is not a vertex in the graph. Those locations, in pgRrouting are called points of interest.

The information needed in the points of interest is pid, edge_id, side, fraction.

On this documentation there will be some 6 fixed points of interest and they will be stored on a table.

Columna	Descripción
`pid`	A unique identifier.
`edge_id`	Identifier of the edge nearest edge that allows an arrival to the point.
`side`	Is it on the left, right or both sides of the segment `edge_id`
`fraction`	Where in the segment is the point located.
`geom`	The geometry of the points.
`newPoint`	The geometry of the points moved on top of the segment.

CREATE TABLE pointsOfInterest(
    pid BIGSERIAL PRIMARY KEY,
    edge_id BIGINT,
    side CHAR,
    fraction FLOAT,
    geom geometry,
    newPoint geometry);
CREATE TABLE

Geometría de los puntos de interés ¶

Inserting the data of the points of interest:

INSERT INTO pointsOfInterest (geom) VALUES
(ST_POINT(1.8, 0.4)),
(ST_POINT(4.2, 2.4)),
(ST_POINT(2.6, 3.2)),
(ST_POINT(0.3, 1.8)),
(ST_POINT(2.9, 1.8)),
(ST_POINT(2.2, 1.7));
INSERT 0 6

LLenado de puntos de interés ¶

Using pgr_findCloseEdges Calculating for visual purposes the points over the graph.

UPDATE pointsOfInterest AS p SET
  edge_id = q.edge_id,
  side = q.side,
  fraction = q.fraction,
  newPoint = ST_endPoint(q.edge)
FROM (SELECT * FROM pgr_findCloseEdges(
  $$SELECT id, geom FROM edges$$,
  (SELECT array_agg(geom) FROM pointsOfInterest),
  0.5, partial => false)) AS q
WHERE p.geom = q.geom;
UPDATE 6

A special case to arrive from both sides of the edge.¶

UPDATE pointsOfInterest SET side = 'b'
WHERE pid = 6;
UPDATE 1

Datos de puntos de interés ¶

SELECT pid, edge_id, side, fraction,
       ST_AsText(geom), ST_AsText(newPoint)
FROM pointsOfInterest
ORDER BY pid;
 pid | edge_id | side |      fraction      |   st_astext    |  st_astext
-----+---------+------+--------------------+----------------+--------------
   1 |       1 | l    |                0.4 | POINT(1.8 0.4) | POINT(2 0.4)
   2 |      15 | r    | 0.3999999999999999 | POINT(4.2 2.4) | POINT(4 2.4)
   3 |      12 | l    | 0.6000000000000001 | POINT(2.6 3.2) | POINT(2.6 3)
   4 |       6 | r    |                0.3 | POINT(0.3 1.8) | POINT(0.3 2)
   5 |       5 | l    |                0.8 | POINT(2.9 1.8) | POINT(3 1.8)
   6 |       4 | b    |                0.7 | POINT(2.2 1.7) | POINT(2 1.7)
(6 rows)

Conectando componentes desconectados ¶

Para obtener la conectividad del grafo:

SELECT * FROM pgr_connectedComponents(
  'SELECT id, source, target, cost, reverse_cost FROM edges'
);
 seq | component | node
-----+-----------+------
|         1 |    1
|         1 |    3
|         1 |    5
|         1 |    6
|         1 |    7
|         1 |    8
|         1 |    9
|         1 |   10
|         1 |   11
|         1 |   12
|         1 |   13
|         1 |   14
|         1 |   15
|         1 |   16
|         1 |   17
|         1 |   18
|         2 |    2
|         2 |    4
(18 rows)

In this example, the component \(2\) consists of vertices \(\{2, 4\}\) and both vertices are also part of the dead end result set.

This graph needs to be connected.

Nota

With the original graph of this documentation, there would be 3 components as the crossing edge in this graph is a different component.

Prepare storage for connection information ¶

ALTER TABLE vertices ADD COLUMN component BIGINT;
ALTER TABLE
ALTER TABLE edges ADD COLUMN component BIGINT;
ALTER TABLE

Save the vertices connection information ¶

UPDATE vertices SET component = c.component
FROM (SELECT * FROM pgr_connectedComponents(
  'SELECT id, source, target, cost, reverse_cost FROM edges'
)) AS c
WHERE id = node;
UPDATE 18

Save the edges connection information ¶

UPDATE edges SET component = v.component
FROM (SELECT id, component FROM vertices) AS v
WHERE source = v.id;
UPDATE 20

Get the closest vertex ¶

Using pgr_findCloseEdges the closest vertex to component \(1\) is vertex \(4\). And the closest edge to vertex \(4\) is edge \(14\).

SELECT edge_id, fraction, ST_AsText(edge) AS edge, id AS closest_vertex
FROM pgr_findCloseEdges(
  $$SELECT id, geom FROM edges WHERE component = 1$$,
  (SELECT array_agg(geom) FROM vertices WHERE component = 2),
  2, partial => false) JOIN vertices USING (geom) ORDER BY distance LIMIT 1;
 edge_id | fraction |                 edge                 | closest_vertex
---------+----------+--------------------------------------+----------------
      14 |      0.5 | LINESTRING(1.999999999999 3.5,2 3.5) |              4
(1 row)

The edge can be used to connect the components, using the fraction information about the edge \(14\) to split the connecting edge.

Conectando componentes ¶

There are three basic ways to connect the components

From the vertex to the starting point of the edge
From the vertex to the ending point of the edge
From the vertex to the closest vertex on the edge
- This solution requires the edge to be split.

The following query shows the three ways to connect the components:

WITH
info AS (
  SELECT
    edge_id, fraction, side, distance, ce.geom, edge, v.id AS closest,
    source, target, capacity, reverse_capacity, e.geom AS e_geom
  FROM pgr_findCloseEdges(
    $$SELECT id, geom FROM edges WHERE component = 1$$,
    (SELECT array_agg(geom) FROM vertices WHERE component = 2),
    2, partial => false) AS ce
  JOIN vertices AS v USING (geom)
  JOIN edges AS e ON (edge_id = e.id)
  ORDER BY distance LIMIT 1),
three_options AS (
  SELECT
    closest AS source, target, 0 AS cost, 0 AS reverse_cost,
    capacity, reverse_capacity,
    ST_X(geom) AS x1, ST_Y(geom) AS y1,
    ST_X(ST_EndPoint(e_geom)) AS x2, ST_Y(ST_EndPoint(e_geom)) AS y2,
    ST_MakeLine(geom, ST_EndPoint(e_geom)) AS geom
  FROM info

  UNION

  SELECT closest, source, 0, 0, capacity, reverse_capacity,
    ST_X(geom) AS x1, ST_Y(geom) AS y1,
    ST_X(ST_StartPoint(e_geom)) AS x2, ST_Y(ST_StartPoint(e_geom)) AS y2,
    ST_MakeLine(info.geom, ST_StartPoint(e_geom))
  FROM info
  /*
  UNION
  -- This option requires splitting the edge
  SELECT closest, NULL, 0, 0, capacity, reverse_capacity,
    ST_X(geom) AS x1, ST_Y(geom) AS y1,
    ST_X(ST_EndPoint(edge)) AS x2, ST_Y(ST_EndPoint(edge)) AS y2,
    edge
  FROM info */
  )

INSERT INTO edges
  (source, target,
    cost, reverse_cost,
    capacity, reverse_capacity,
    x1, y1, x2, y2,
    geom)
(SELECT
    source, target, cost, reverse_cost, capacity, reverse_capacity,
    x1, y1, x2, y2, geom
  FROM three_options);
INSERT 0 2

Checking components ¶

Ignoring the edge that requires further work. The graph is now fully connected as there is only one component.

SELECT * FROM pgr_connectedComponents(
  'SELECT id, source, target, cost, reverse_cost FROM edges'
);
 seq | component | node
-----+-----------+------
|         1 |    1
|         1 |    2
|         1 |    3
|         1 |    4
|         1 |    5
|         1 |    6
|         1 |    7
|         1 |    8
|         1 |    9
|         1 |   10
|         1 |   11
|         1 |   12
|         1 |   13
|         1 |   14
|         1 |   15
|         1 |   16
|         1 |   17
|         1 |   18
(18 rows)

Ver también¶

Índices y tablas

pgr_findCloseEdges¶

Descripción¶

Firmas¶

One point¶

Many points¶

Parámetros¶

Parámetros opcionales¶

Consultas Internas¶

SQL aristas¶

Columnas de Resultados¶

Ejemplos Adicionales¶

Ver también¶

`pgr_findCloseEdges`¶