pgr_findCloseEdges - pgRouting Manual (3.8)
pgr_findCloseEdges
pgr_findCloseEdges
- Finds the close edges to a point geometry.
Availability
Version 3.8.0
-
Error messages adjustment.
-
partialoption is removed. -
Function promoted to official.
Version 3.4.0
-
New proposed function.
Description
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.
-
EMPTY SETis returned on dryrun executions
Boost Graph Inside
Signatures
Summary
[cap,
dryrun]
(edge_id,
fraction,
side,
distance,
geom,
edge)
One point
[cap,
dryrun]
(edge_id,
fraction,
side,
distance,
geom,
edge)
- Example :
-
Get two close edges to points of interest with \(pid = 5\)
-
cap => 2
SELECT
edge_id, fraction, side, distance,
distance, ST_AsText(geom) AS point, ST_AsText(edge) As edge
FROM pgr_findCloseEdges(
$$SELECT id, geom FROM edges$$,
(SELECT geom FROM pointsOfInterest WHERE pid = 5),
0.5, cap => 2);
edge_id fraction side distance distance point edge
---------+----------+------+----------+----------+----------------+---------------------------
5 0.8 l 0.1 0.1 POINT(2.9 1.8) LINESTRING(2.9 1.8,3 1.8)
8 0.9 r 0.2 0.2 POINT(2.9 1.8) LINESTRING(2.9 1.8,2.9 2)
(2 rows)
Many points
[cap,
dryrun]
(edge_id,
fraction,
side,
distance,
geom,
edge)
- Example :
-
For each points of interests, find the closest edge.
SELECT
edge_id, fraction, side, distance,
ST_AsText(geom) AS point,
ST_AsText(edge) AS edge
FROM pgr_findCloseEdges(
$$SELECT id, geom FROM edges$$,
(SELECT array_agg(geom) FROM pointsOfInterest),
0.5);
edge_id fraction side distance point edge
---------+----------+------+----------+----------------+---------------------------
1 0.4 l 0.2 POINT(1.8 0.4) LINESTRING(1.8 0.4,2 0.4)
6 0.3 r 0.2 POINT(0.3 1.8) LINESTRING(0.3 1.8,0.3 2)
12 0.6 l 0.2 POINT(2.6 3.2) LINESTRING(2.6 3.2,2.6 3)
15 0.4 r 0.2 POINT(4.2 2.4) LINESTRING(4.2 2.4,4 2.4)
5 0.8 l 0.1 POINT(2.9 1.8) LINESTRING(2.9 1.8,3 1.8)
4 0.7 r 0.2 POINT(2.2 1.7) LINESTRING(2.2 1.7,2 1.7)
(6 rows)
Parameters
|
Parameter |
Type |
Description |
|---|---|---|
|
|
Edges SQL as described below. |
|
|
point |
|
The point geometry |
|
points |
|
An array of point geometries |
|
tolerance |
|
Max distance between geometries |
Optional parameters
|
Parameter |
Type |
Default |
Description |
|---|---|---|---|
|
|
|
\(1\) |
Limit output rows |
|
|
|
|
|
Inner Queries
Edges SQL
|
Column |
Type |
Description |
|---|---|---|
|
|
ANY-INTEGER |
Identifier of the edge. |
|
|
|
The
|
Result columns
Returns set of
(edge_id,
fraction,
side,
distance,
geom,
edge)
|
Column |
Type |
Description |
|---|---|---|
|
|
|
Identifier of the edge.
|
|
|
|
Value in <0,1> that indicates the relative position from the first end-point of the edge. |
|
|
|
Value in
|
|
|
|
Distance from the point to the edge. |
|
|
|
Original
|
|
|
|
|
Additional Examples
One point in an edge
SELECT edge_id, fraction, side, distance, ST_AsText(geom) geom, ST_AsText(edge) edge
FROM pgr_findCloseEdges(
$$SELECT 1 AS id, ST_MakeLine(ST_makePoint(2,0), ST_MakePoint(2,3)) AS geom$$,
ST_MakePoint(0,1.5), 5);
edge_id fraction side distance geom edge
---------+----------+------+----------+--------------+-------------------------
1 0.5 l 2 POINT(0 1.5) LINESTRING(0 1.5,2 1.5)
(1 row)
![digraph D {
subgraph cluster0 {
label="data";
point [shape=circle;style=filled;color=green;fontsize=8;width=0.3;fixedsize=true];
point [pos="0,1.5!"]
sp, ep [shape=circle;fontsize=8;width=0.3;fixedsize=true];
sp[pos="2,0!"]
ep[pos="2,3!"]
sp -> ep:s
}
subgraph cluster1 {
label="results";
geom [shape=circle;style=filled;color=green;fontsize=8;width=0.3;fixedsize=true];
geom [pos="3,1.5!"]
np11 [shape=point;color=black;size=0;fontsize=8;fixedsize=true];
np11 [pos="5,1.5!";xlabel="fraction=0.5"];
sp1, ep1 [shape=circle;fontsize=8;width=0.3;fixedsize=true];
sp1[pos="5,0!"]
ep1[pos="5,3!"]
sp1:n -> np11:s [dir=none]
np11:n -> ep1:s
geom -> np11 [color=red,label="edge"];
}
}](images/graphviz-fa6963e344bd45fa1ba83b7ac3a7594034eb0427.png)
-
The green node is the original point.
-
geomhas the value of the original point. -
The geometry
edgeis a line that connects the original point with the edge \(sp \rightarrow ep\) edge. -
The point is located at the left of the edge.
One point dry run execution
Using the query from the previous example:
-
Returns
EMPTY SET. -
dryrun => true-
Generates a PostgreSQL
NOTICEwith the code used. -
The generated code can be used as a starting base code for additional requirements, like taking into consideration the SRID.
-
SELECT edge_id, fraction, side, distance, ST_AsText(geom) geom, ST_AsText(edge) edge
FROM pgr_findCloseEdges(
$$SELECT 1 AS id, ST_MakeLine(ST_makePoint(2,0), ST_MakePoint(2,3)) AS geom$$,
ST_MakePoint(0,1.5), 5, dryrun => true);
NOTICE:
WITH
edges_sql AS (SELECT 1 AS id, ST_MakeLine(ST_makePoint(2,0), ST_MakePoint(2,3)) AS geom),
point_sql AS (SELECT unnest('{01010000000000000000000000000000000000F83F}'::geometry[]) AS point),
results AS (
SELECT
id::BIGINT AS edge_id,
ST_LineLocatePoint(geom, point) AS fraction,
CASE WHEN ST_Intersects(ST_Buffer(geom, 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, 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)
Many points in an edge
-
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.
SELECT edge_id, fraction, side, distance, ST_AsText(geom) geom, ST_AsText(edge) edge
FROM pgr_findCloseEdges(
$$SELECT 1 AS id, ST_MakeLine(ST_makePoint(1,0), ST_MakePoint(1,3)) AS geom$$,
ARRAY[ST_MakePoint(0,2), ST_MakePoint(3,1)]::GEOMETRY[], 5);
edge_id fraction side distance geom edge
---------+----------------+------+----------+------------+---------------------
1 0.666666666667 l 1 POINT(0 2) LINESTRING(0 2,1 2)
1 0.333333333333 r 2 POINT(3 1) LINESTRING(3 1,1 1)
(2 rows)
![digraph G {
subgraph cluster0 {
p1,p2 [shape=circle;style=filled;color=green;fontsize=8;width=0.3;fixedsize=true];
p1 [pos="0,2!"]
p2 [pos="3,1!"]
sp, ep [shape=circle;fontsize=8;width=0.3;fixedsize=true];
sp[pos="1,0!"]
ep[pos="1,3!"]
sp -> ep:s
}
subgraph cluster1 {
g1, g2 [shape=circle;style=filled;color=green;fontsize=8;width=0.3;fixedsize=true];
g1 [pos="4,2!"]
g2 [pos="7,1!"]
np11,np21 [shape=point;color=black;size=0;fontsize=8;fixedsize=true];
np11 [pos="5,2!";xlabel="fraction=0.63"];
np21 [pos="5,1!";xlabel="fraction=0.33"];
sp1, ep1 [shape=circle;fontsize=8;width=0.3;fixedsize=true];
sp1[pos="5,0!"]
ep1[pos="5,3!"]
sp1:n -> np21:s [dir=none]
np21:n -> np11:s [dir=none]
np11:n -> ep1:s
g1 -> np11 [color=red;label="edge"];
g2 -> np21 [color=red;label="edge"]
}
}](images/graphviz-9e125b327a66860f05bc0fe6496652d2c3a6e1a1.png)
Many points dry run execution
-
Returns
EMPTY SET. -
dryrun => true-
Do not process query
-
Generate a PostgreSQL
NOTICEwith the code used to calculate all columns
-
SELECT edge_id, fraction, side, distance, ST_AsText(geom) geom, ST_AsText(edge) edge
FROM pgr_findCloseEdges(
$$SELECT 1 AS id, ST_MakeLine(ST_makePoint(1,0), ST_MakePoint(1,3)) AS geom$$,
ARRAY[ST_MakePoint(0,2), ST_MakePoint(3,1)]::GEOMETRY[], 5, dryrun=>true);
NOTICE:
WITH
edges_sql AS (SELECT 1 AS id, ST_MakeLine(ST_makePoint(1,0), ST_MakePoint(1,3)) AS geom),
point_sql AS (SELECT unnest('{010100000000000000000000000000000000000040:01010000000000000000000840000000000000F03F}'::geometry[]) AS point),
results AS (
SELECT
id::BIGINT AS edge_id,
ST_LineLocatePoint(geom, point) AS fraction,
CASE WHEN ST_Intersects(ST_Buffer(geom, 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, 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 - Proposed
SELECT * FROM pgr_withPoints(
$e$ SELECT * FROM edges $e$,
$p$ SELECT edge_id, 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.
Points of interest
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.
|
Column |
Description |
|---|---|
|
|
A unique identifier. |
|
|
Identifier of the nearest segment. |
|
|
Is it on the left, right or both sides of the segment
|
|
|
Where in the segment is the point located. |
|
|
The geometry of the points. |
|
|
The distance between
|
|
|
A segment that connects the
|
|
|
A point on segment
|
CREATE TABLE pointsOfInterest(
pid BIGSERIAL PRIMARY KEY,
edge_id BIGINT,
side CHAR,
fraction FLOAT,
distance FLOAT,
edge geometry,
newPoint geometry,
geom geometry);
IF v > 3.4 THEN
Points of interest fill up
Inserting 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));
Filling the rest of the table.
UPDATE pointsofinterest SET
edge_id = poi.edge_id,
side = poi.side,
fraction = round(poi.fraction::numeric, 2),
distance = round(poi.distance::numeric, 2),
edge = poi.edge,
newPoint = ST_EndPoint(poi.edge)
FROM (
SELECT *
FROM pgr_findCloseEdges(
$$SELECT id, geom FROM edges$$,(SELECT array_agg(geom) FROM pointsOfInterest), 0.5) ) AS poi
WHERE pointsOfInterest.geom = poi.geom;
Any other additional modification: In this manual, point \(6\) can be reached from both sides.
UPDATE pointsOfInterest SET side = 'b' WHERE pid = 6;
The points of interest:
SELECT
pid, ST_AsText(geom) geom,
edge_id, fraction AS frac, side, distance AS dist,
ST_AsText(edge) edge, ST_AsText(newPoint) newPoint
FROM pointsOfInterest;
pid geom edge_id frac side dist edge newpoint
-----+----------------+---------+------+------+------+---------------------------+--------------
1 POINT(1.8 0.4) 1 0.4 l 0.2 LINESTRING(1.8 0.4,2 0.4) POINT(2 0.4)
4 POINT(0.3 1.8) 6 0.3 r 0.2 LINESTRING(0.3 1.8,0.3 2) POINT(0.3 2)
3 POINT(2.6 3.2) 12 0.6 l 0.2 LINESTRING(2.6 3.2,2.6 3) POINT(2.6 3)
2 POINT(4.2 2.4) 15 0.4 r 0.2 LINESTRING(4.2 2.4,4 2.4) POINT(4 2.4)
5 POINT(2.9 1.8) 5 0.8 l 0.1 LINESTRING(2.9 1.8,3 1.8) POINT(3 1.8)
6 POINT(2.2 1.7) 4 0.7 b 0.2 LINESTRING(2.2 1.7,2 1.7) POINT(2 1.7)
(6 rows)
See Also
Indices and tables