Network Walking in PostGIS21 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.
Visually, the network looks like this:
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.
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.
And here’s the function in action, generating the downstream path from segment 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!