Supported versions: latest (3.8) 3.7 3.6 3.5 3.4 main dev

pgr_findCloseEdges

pgr_findCloseEdges - Finds the close edges to a point geometry.

Availability

Version 3.8.0

• Error messages adjustment.

• partial option 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 SET is returned on dryrun executions

Boost Graph Inside

Signatures

Summary

pgr_findCloseEdges(Edges SQL, point, tolerance, [options])

pgr_findCloseEdges(Edges SQL, points, tolerance, [options])

options: [cap, dryrun]

Returns set of (edge_id, fraction, side, distance, geom, edge)

OR EMPTY SET

One point

pgr_findCloseEdges(Edges SQL, point, tolerance, [options])

options: [cap, dryrun]

Returns set of (edge_id, fraction, side, distance, geom, edge)

OR EMPTY SET

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

pgr_findCloseEdges(Edges SQL, points, tolerance, [options])

options: [cap, dryrun]

Returns set of (edge_id, fraction, side, distance, geom, edge)

OR EMPTY SET

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	TEXT	Edges SQL as described below.
point	POINT	The point geometry
points	POINT[]	An array of point geometries
tolerance	FLOAT	Max distance between geometries

Optional parameters

Parameter	Type	Default	Description
cap	INTEGER	$1$	Limit output rows
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.

Inner Queries

Edges SQL

Column	Type	Description
id	ANY-INTEGER	Identifier of the edge.
geom	geometry	The LINESTRING geometry of the edge.

Result columns

Returns set of (edge_id, fraction, side, distance, geom, edge)

Column	Type	Description
edge_id	BIGINT	Identifier of the edge. When $cap=1$, it is the closest edge.
fraction	FLOAT	Value in <0,1> that indicates the relative position from the first end-point of the edge.
side	CHAR	Value in [r, l] indicating if the point is: At the right r of the segment. When the point is on the line it is considered to be on the right. At the left l of the segment.
distance	FLOAT	Distance from the point to the edge.
geom	geometry	Original POINT geometry.
edge	geometry	LINESTRING geometry that connects the original point to the closest point of the edge with identifier edge_id

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)

• The green node is the original point.

• geom has the value of the original point.

• The geometry edge is a line that connects the original point with the edge $sp\to 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 NOTICE with 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\to 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)

Many points dry run execution

• Returns EMPTY SET.

• dryrun => true

  • Do not process query

  • Generate a PostgreSQL NOTICE with 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
pid	A unique identifier.
edge_id	Identifier of the nearest segment.
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.
distance	The distance between geom and the segment edge_id.
edge	A segment that connects the geom of the point to the closest point on the segment edge_id.
newPoint	A point on segment edge_id that is the closest to geom.

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

• withPoints - Category

• Sample Data

Indices and tables

• Index

• Search Page