Paul Ramsey

Open source software developer and information technology professional.
Occasional blowhard.

Network Walking in PostGIS

21 Jul 2010

One of the new features in PostgreSQL 8.4 was the “WITH RECURSIVE” clause available for queries. It allows you to define a subquery based on a recursive term — fancy language for a function that calls itself. One of the favorite uses of recursion is walking a network. Geospatial applications use networks all the time: electrical grids, stream systems, and storm sewers are all directed networks (they have unidirectional flow).

Here’s an example of network walking using a simple collection of segments. As is common in many GIS applications, the segment are implicitly connected — their end points are coincident with the start points of other segments.

CREATE TABLE network ( 
  segment geometry, 
  id integer primary key 
  );

INSERT INTO network VALUES ('LINESTRING(1 1, 0 0)', 1);
INSERT INTO network VALUES ('LINESTRING(2 1, 1 1)', 2);
INSERT INTO network VALUES ('LINESTRING(1 2, 1 1)', 3);
INSERT INTO network VALUES ('LINESTRING(3 1, 2 1)', 4);
INSERT INTO network VALUES ('LINESTRING(3 2, 2 1)', 5);
INSERT INTO network VALUES ('LINESTRING(2 3, 1 2)', 6);
INSERT INTO network VALUES ('LINESTRING(1 3, 1 2)', 7);
INSERT INTO network VALUES ('LINESTRING(4 2, 3 2)', 8);
INSERT INTO network VALUES ('LINESTRING(3 4, 2 3)', 9);
INSERT INTO network VALUES ('LINESTRING(2 4, 2 3)', 10);
INSERT INTO network VALUES ('LINESTRING(1 4, 1 3)', 11);
INSERT INTO network VALUES ('LINESTRING(4 3, 4 2)', 12);
INSERT INTO network VALUES ('LINESTRING(4 4, 3 4)', 13);

CREATE INDEX network_gix ON network USING GIST (segment);

Visually, the network looks like this:

Network

To walk our network, use a WITH clause that starts with one segment, then repeatedly adds the next downstream segment to the collection. In our case, the “next downstream segment” is defined as a segment whose start point is close to the end point of the current segment. We’ll walk down from segment 6.

WITH RECURSIVE walk_network(id, segment) AS (
  SELECT id, segment 
    FROM network 
    WHERE id = 6
  UNION ALL
  SELECT n.id, n.segment
    FROM network n, walk_network w
    WHERE ST_DWithin(
      ST_EndPoint(w.segment),
      ST_StartPoint(n.segment),0.01)
)
SELECT id
FROM walk_network

Which returns:

 id
---
  6
  3
  1
(3 rows)

From 6 to 3 to 1, correct! Once we have our walker producing the results we want, we can wrap more PostGIS and PostgreSQL functions around the walker to produce a finished product. Here’s a function that takes in an edge identifier and outputs a linestring based on the downstream path.

CREATE OR REPLACE FUNCTION downstream(integer)
RETURNS geometry
LANGUAGE sql
AS '
WITH RECURSIVE walk_network(id, segment) AS (
    SELECT id, segment FROM network WHERE id = $1
  UNION ALL
    SELECT n.id, n.segment
    FROM network n, walk_network w
    WHERE ST_DWithin(ST_EndPoint(w.segment),ST_StartPoint(n.segment),0.01)
  )
SELECT ST_MakeLine(ST_EndPoint(segment))
FROM walk_network
' IMMUTABLE;

And here’s the function in action, generating the downstream path from segment 12.

SELECT ST_AsText(Downstream(12));
            st_astext
---------------------------------
 LINESTRING(4 2,3 2,2 1,1 1,0 0)
(1 row)

Check the generated path against our network picture – looks good!

Path 12

Recent Posts