I have to create layers of land coverage from one point to anywhere around on a given street network for a given distance (ex: FROM house, DISTANCE 30000m)

An important factor to understand; I need the result to be exactly superposed over my network, and the coverage to represent only the parts of the road (let say, the addresses) that can be reached from the network for the given distance. Nothing more. I need to be precise, because it will be used for emergency services and efficiency analysis over the covered network. And to add to the fun, the tool must not only give the right answer, but do it in a decent length of time, as it will ultimately be open to other uses on a public web interface (so no, I don't only need an application that will generate the right routing over a night of work!)

The point is not to find the shortest way to get to a known point, so basic pgrouting tools can't get me a direct answer.

I developped a working algorithm, and it works well on long routes, but as soon a I enter a "real" network (as for a city, or even a village), it crashes... well, it simply run for hours.

Basically, my algorithm goes like this:

First, we link our network table to our previous results to make sure we don't take a route that as been looked uppon, unless we have more "remaining distance" to cover at this point, which mean that our new route is better.

FOR a in EXECUTE 'SELECT aa.ogc_fid, aa.'||col_contr||' as cost, aa.the_geom, aa.source, aa.target

   FROM '||table_name||' aa LEFT JOIN temp res ON res.ogc_fid = aa.ogc_fid AND res.dist > '||distance||' 
    WHERE (aa.source = '||debut||' 
            OR aa.target = '||debut||')
            AND (ARRAY[aa.ogc_fid] &&  ARRAY['||array_to_string(fromSegment,',')||']) = false
            AND res.ogc_fid is null' 


After that (I'll short the code), IF(distance > a.cost) THEN

We insert the informations in the result table, and launch back the function from this node, which developps a tree.

ELSE (we don't have enough "remaining distance" to cover the line)

We return a st_line_substring of the lenght we can cover, and the function stops

So it's a reccursive function that tries to cover every possible routes from the startpoint to the given distance...

Any idea about how to improve it's speed? I think the answer would be to modify the fist FOR statement... but after hours of brain boiling, I have to admit that I can't do it alone!


Some new details Beautiful network Suppose this fictive (and horrible, sorry, not on my computer) network, with the blue point as a startpoint for a given distance.

As wonderful, but with colors! Driving_distance would give a result such as this (red dots being end vertex for the distance, and green ones intermediate vertex on the path).

The problem I face here (but still, not on my computer, can't try it tonight, maybe I'm wrong) is that I need a very precise and stuck-on-the-network polyline result. With these dots, I guess I could recreate the path, using some kind of point_to_line function, but it would not work for complexe polylines that are not straight from startpoint to endpoint (like, if the road makes an "S"...).

Same problem with isocrone:

In red dress? The coverage here is not what I need, simply because it covers spaces that cannot be reached on the real network (like the segment in the pink ellipse, which is pass the terminal red dot).

(Sorry about the pictures, I'll probably give you some real screenshots of the problem tomorrow)

5 Answers 5


pgRouting driving_distance function returns not only vertex(node)_id, but also edge(link)_id and cost. (See Official document - 'Examples' part and yellow nodes/links of bellow image.) driving distance result image

So, I think that you can find red point efficiently from driving_distance result like...

for [edge(link) which is not listed in result and connect listed vertex(node)]
  calculate (distance - cost) point from (start/target) point

Not sure I understand your function, but isn't "Driving Distance" computation what you want to do? This already exists in pgRouting: http://www.pgrouting.org/docs/1.x/dd.html

  • I just added a comment in the question above answering the thing about Driving_distance, though it gave me an idea I'll put to the test tomorrow...
    – Horizen
    Commented Jul 16, 2012 at 3:36
  • Oh, and a problem that brings Driving_distance is that it stops on the fartest vertex it can on the network... while the real distance is very often not on a vertex, but on the line itself! (I hope I'm not just missing something here though!)
    – Horizen
    Commented Jul 16, 2012 at 12:29

Is it something like this you are trying to create? This shows how far you can get in 1,2,3 minutes on a network.

Picture of network

  • Well, it looks like it yes. I have to be able to point a fire station (for example) and get it's coverage for a given distance (let say, 10k, 15k...). So if we could switch the driving time of this to an effective distance, it would make it! Could you tell me more? (And I have to give that note: The problem is not the idea of the how to do it, but how to do it in a relatively fast way :) )
    – Horizen
    Commented Jul 16, 2012 at 12:23
  • By "effective distance" do you mean shortest path instead? This was all created by our RW Net 4 software, not pgRouting. Commented Jul 16, 2012 at 16:12
  • Hum, no, I really need to know every routes that can be reached, and to what length, from the startpoint over the given distance. Shortest path would only give one, and needs a endpoint... Sorry for my ignorance, but... RW?
    – Horizen
    Commented Jul 16, 2012 at 17:22
  • So you want the endpoint of the lines on my map? You could extract that easily from the output, but I think the map above would be better? "Shortest path" doesn't mean a single path. It just refers to the route criteria: shortest / fastest or something else. RW Net 4 can be found here: www.routeware.dk. An SDK we sell. Commented Jul 16, 2012 at 19:45
  • Well... the result I want will look almost exactly as your map, but I would use other criteras. The problem here though is to build the algorithm to do so on a postgreSQL DB, using pgRouting (I already got a license of arcGIS which does exactly this, but we want to go opensource)
    – Horizen
    Commented Jul 17, 2012 at 0:04

Ok, thanks group!

Me and my partner finally made it today. I still have work to do in cleaning the code, but be assured that I'll post a summary of the technique here as soon as possible.

A glimpse of the solution for now: Our function was working "in depth", building a single route as long as possible, and then unfolding the branches of the tree backward.

It was working, but was awfully long.

What we have now works "in width", using a FIFO (first in, first out) array technique. It is now thousands of times faster, and the result is exactly what we wanted!

More details later... Thanks again for your help!

By the way, I dropped the Driving_distance pgRouting function a bit too fast. I now believe that you're right, it could be done with it, even though it would need a good amount of post-process work to give me what I was looking for. Still, a good way to look at for any similar problem!


It sounds that what you want is an isochrone polygon where the cost is the geometric length instead of the usual travel distance in time.

You should look at the answers for Drive-time polygons.

  • I added a case in the question (3rd picture) that shows a problem I think isochrones will give me. Am I wrong to think that in this case (above), the answer won't be precise?
    – Horizen
    Commented Jul 16, 2012 at 3:38
  • You are it will be included. Nevertheless, the libraries that you use to generate the isochrone polygon (take pgrouting as an example) also return edges and nodes for the end points (this is the previous step required to generate the polygon afterall). It is not clear to me why you don't just mark the returned edges as the solution (in your 3rd image, the end of that edge would not have been returned in the list of edges fully traversed) Commented Jul 17, 2012 at 15:08

Your Answer

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

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