[pgrouting-users] PgRouting and sub-networks / catchments

Stephen Woodbridge woodbri at swoodbridge.com
Wed May 25 14:05:50 EDT 2011

Hi Peter,

pgRouting has a driving distance function which kind of does what you 
want but not quite. I am trying to do something similar so I can 
describe what you need to do and the problems are that I have found so far.

1. if you do a Dijkstra solutions from a given node, it will generate 
the shortest path tree from that start node.

Problem: driving distance almost give you this as it returns:
vertex_id, edge_id, cost (to that vertex from the start).
In theory you should be able to reconstruct the tree from this 
information, but there appears to be a bug in pgRouting where it does 
not return all the edges and you end up with multiple disconnected trees 
in the reconstruction of the tree because of the missing edge records.

1. wait for a bug fix
2. fix it yourself if you have the skill
3. clone the driving distance code and make a new function that returns:
vertex_id, parent_id, edge_id, cost and then reconstruct the tree from 

2. assuming you can get the Dijkstra tree, write a DFS (depth first 
search) of the tree the collects the edges and of one of you outbound paths

3. create a linestring from the outbound path, maybe something like
    select st_memunion(the_geom) from edges where gid in (list of edge 
ids from DFS);

4. trim the linestring to your cutoff distance. look at the linear 
referencing functions.

So bottom line, there is no canned solution for this today. Search the 
dev list for subject "Driving Directions Revisited" for my discussion on 
the bug above.

I would like to see a function that returns a setof paths from a start 
node to a cutoff distance as you describe. Or a set of tools that make 
the Dijkstra solution available for additional post processing.

-Steve W

On 5/25/2011 1:18 PM, Peter Schmiedeskamp wrote:
> Dear PgRouting list,
> I posted this question to the gis.stackexchange.com site a few days
> ago, but haven't had any responses. I'm reposting here in hopes that
> someone on this list may be able to help.
> I have a polyline shapefile representing a road network and a second
> shapefile containing points. I would like to use PostGIS (presumably
> PgRouting) to identify sub-networks or service areas radiating from
> these points.
> Essentially, I am hoping to ask the question, "Starting from point X,
> how far could I walk in any given direction, given a total travel
> budget of 1 km, following the road network?" The result would be a set
> of clipped polylines representing the total range of travel
> possibility, given a 1 km travel budget.
> For reference, this GRASS analysis appears to be exactly what I want
> to do (except I want to do this in PostGIS):
> http://www.gdf-hannover.de/lit_html/grass60_v1.2_en/node57.html#sec:optalloc
> This next example appears to be almost what I want to do, except it
> seems to answer the question "which nodes could I travel to given a
> travel budget of X distance?"
> http://underdark.wordpress.com/2011/02/12/drive-time-isochrones/
> The second is not quite the answer I'm looking for, as I want the
> polylines clipped to my travel distance--I don't care if I make it all
> the way to a node.
> Cheers,
> Peter
> P.S. If anyone is interested in why this sort of analysis is useful,
> this journal article (hurray for open access journals!) explains how
> network buffers are more appropriate for some urban transportation
> planning applications. When you're dealing with pedestrians in areas
> with large superblocks, this also helps explain why distances to nodes
> are not quite accurate enough.
> Oliver, Lisa N, Nadine Schuurman, and Alexander W Hall. 2007.
> Comparing circular and network buffers to examine the influence of
> land use on walking for leisure and errands. International journal of
> health geographics 6, no. 1 (January): 41. doi:10.1186/1476-072X-6-41.
> http://www.ij-healthgeographics.com/content/6/1/41
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users

More information about the Pgrouting-users mailing list