[pgrouting-users] Re: driving distance

Stephen Woodbridge woodbri at swoodbridge.com
Wed Jun 1 17:30:15 EDT 2011

On 6/1/2011 4:54 PM, Ryan Dalton wrote:
> I had a similar thought/question that I wanted to run by the list to
> make sure my thinking is sound and hopefully answer one more piece of my
> puzzle.  I am very new to pgRouting, but have been playing around with
> it enough to come up with some of my own ways of doing things.  If I am
> missing any key concepts that make my thinking incorrect or if there are
> more efficient ways to complete the process, I am open to critique.
> My thought was to use the *alphashape *function in pgRouting to generate
> the polygons based upon the cost field.  If the cost field were in
> distance units, it would create a polygon of X distance.  If cost were
> in time, it would create a polygon of X time.  Then, to get something
> similar to Peter's request, couldn't you simply select the underlying
> road segments that are completely within the polygon?  While it wouldn't
> give you the exact roads available for travel, it would theoretically be
> very close, right?  Am I missing any key concepts that would make this
> thought process incorrect?

Yes, this will work fine as far as it goes. It is possible to have 
islands that you can not reach within the polygon and to have multiple 
polygons that are disconnected except by a road segment. So depending on 
your use cases what you describe may work, just as circle might work 
from some use cases. If you need the possible routes then this will 
obviously not work as you pointed out. Also be aware that the alpha 
shape is probably calculated based on the node and not the shape of the 
segments that represent the edges in the graph. This may or may not 
matter again depending on your use case.


> The code I am using for a single polygon is:
> /SELECT the_geom /
> /FROM points_as_polygon('SELECT id, ST_X(the_geom) AS x, ST_Y(the_geom)
> AS y FROM a_drive_dist WHERE cost <= 5');/
> Lastly, my code above gives me a single polygon representing a cost of
> 5.  How would I change this code to generate multiple polygons in the
> same layer representing cost units of 0-5, 5-10, 10-15, and so on?  I
> have in my head something like the SELECT...GROUP BY function but for
> continuous values.  Thanks!
> Ryan
>     ---------- Forwarded message ----------
>     From: Peter Schmiedeskamp <peter at thoughtspot.net
>     <mailto:peter at thoughtspot.net>>
>     To: pgrouting-users at lists.osgeo.org
>     <mailto:pgrouting-users at lists.osgeo.org>
>     Date: Wed, 25 May 2011 10:18:21 -0700
>     Subject: [pgrouting-users] PgRouting and sub-networks / catchments
>     Dear PgRouting list,
>     I posted this question to the gis.stackexchange.com
>     <http://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
>     ---------- Forwarded message ----------
>     From: Stephen Woodbridge <woodbri at swoodbridge.com
>     <mailto:woodbri at swoodbridge.com>>
>     To: pgrouting-users at lists.osgeo.org
>     <mailto:pgrouting-users at lists.osgeo.org>
>     Date: Wed, 25 May 2011 14:05:50 -0400
>     Subject: Re: [pgrouting-users] PgRouting and sub-networks / catchments
>     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.
>     Work-a-rounds:
>     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 this.
>     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
> _______________________________________________
> 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