Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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' 

LOOP

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!

Thanks

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)

share|improve this question
add comment

5 Answers 5

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

share|improve this answer
    
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 Jul 16 '12 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 Jul 16 '12 at 12:29
add comment

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
share|improve this answer
add comment

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

share|improve this answer
    
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 Jul 16 '12 at 12:23
    
By "effective distance" do you mean shortest path instead? This was all created by our RW Net 4 software, not pgRouting. –  Uffe Kousgaard Jul 16 '12 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 Jul 16 '12 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. –  Uffe Kousgaard Jul 16 '12 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 Jul 17 '12 at 0:04
add comment
up vote 1 down vote accepted

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 technic 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 technic. 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!

share|improve this answer
add comment

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.

share|improve this answer
    
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 Jul 16 '12 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) –  Ragi Yaser Burhum Jul 17 '12 at 15:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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