13

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.

Improve this question
1
  • One option that occurs to me is to somehow split my polylines into lots of points. That gets me closer to the right answer, but seems pretty hacky, and still doesn't quite get me there.
    – Peter
    May 18, 2011 at 14:29

3 Answers 3

Reset to default
2

One thought that I had was to 1) run the driving_distance routine and 2) use the "points_as_polygon" routine from pgRouting (that calls the alphashape function) to generate the smallest polygon(s) at given cost distances based upon the points the driving_distance routine returns. Then you could select all streets within the polygons which would give you a general idea of travel.

If you haven't been following the discussion on the pgRouting users list, they have been discussing more options lately (May & June 2011 threads).

Improve this answer
1
  • 1
    Interesting user list discussions. Too bad the driving_distance function is buggy.
    – underdark ♦
    Jun 10, 2011 at 19:44
1

Since this is really a graph problem, what you need is the connectivity/topology + cost information. For pg_routing, that is the table that you send to the shortest path algorithms. This article has information on how to build one (I assume you already have one). Sorry I can't give your the exact function in pg_routing that does this, but writing one should be doable. However, I can tell you that if you keep calling the shortest_path over and over your are doing the algorithm below over and over and trashing the result - not efficient at all.

Your solution then becomes walking every edge while adding them to a "walked list" and computing a cost until your budget (i.e distance) is overdrawn. If the budget is acceptable (i.e the budget has not been overdrawn), you also add the geometry to an "acceptable list geometry bag". You only have to process each edge exactly once. For the very last edged (where your budgets are overdrawn), you need to get the length and interpolate the exact distance that you want to travel, then add the result to the "acceptable list". Your result is a union of that geometry bag.

Improve this answer
2
  • 1
    There is a subtlety in the last step: some edges could be reached from either of its endpoints. This can cause portions of both ends to be included or even the entire edge, even though traversing the whole edge from either one of the endpoints would exceed the budget limit. E.g., consider travel from point a along an undirected graph with unit-length edges {(a,b), (a,c), (b,c)} and a budget of 1.6. You can reach either b or c at a cost of 1, with 0.6 left to spend. This makes every point along edge (b,c) accessible.
    – whuber
    Jun 17, 2011 at 20:52
  • You are correct :) +1
    – Ragi Yaser Burhum
    Jun 17, 2011 at 21:57
1

"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?"

As you only have to consider a small region (1km radius at max), you could probably get away with splitting the links into multiple small pieces (depending on the accuracy you want to achieve) and creating the necessary nodes. The resulting "high-resolution" networks should be still manageable.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.