[pgrouting-users] pgrouting - Driving Direction - foss4g2010 WORKSHOP

Hey Thank you Stephen for you suggestions.

Well, it is about 5 and half day that I am trying to implement the suggestions that Stephen gave me. But no solution yet.
The thing is I am trying to implement his suggestion from the message below on the pgrouting foss4g2010 workshop in order to see how it works.
I tried to combine the pgrouting workshop from : http://www.pgrouting.org/docs/ol-workshop/index.html tying to do some minor change but no success. http://www.pgrouting.org/docs/ol-workshop/ch09.html

Is there anyone working on it or had the chance to get the same result that Stephen got on his tool?

I am still having a hard time to implement it. I need to get a GeoJSON file back with the path determined by the pgroutitng.

P.S. The foss4gg2010 is based on OSM in BARCELONA.

On Tue, Jan 25, 2011 at 2:40 AM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

On 1/24/2011 5:44 PM, Cleber Arruda wrote:

Hi Stephen how are you? I hope you are fine and enjoying life.
Well, I am doing my master thesis in Sweden in Geomatics as I mentioned to you on the phone.
My Master thesis topic is the development of routing network using pgrouting and OSM.
So, I have been looking for the solution for this problem since October 2010. I have stopped the written part of my thesis and started the technical part. I have to finish write the application - the routing using pgrouting - just the one you have on http://gis.imaptools.com/routing/leaddog/?zoom=10&lat=33.85667&lon=35.52978&layers=B0TTTF&start=35.492313%2033.826188&stop=35.595811%2033.906827&method=STS&lang=eng).

I would appreciate if you can guide me through the steps to find the best route and draw the segment/path correctly from the start point to the end point.
Well, I am sending you a print screen of what I have got so far.

Hi Cléber,

So the process for dealing with the segments is as follows.

  1. we assume that the list of segments is in the correct order from start to end of the route, but any given segment might be flipped backwards. For example the segment is loaded as A->B but in the graph we traverse it from B->A. We will always get the segment in the result as A->B. So this is the process to flip the segments. For this pseudo-code I will use the following notation:

S[n] - segment n
S[n].A - is the point at the start of the segment
S[n].B - is the point at the end of the segment

A. check if we need to flip the first segment, If the start of the 1st segment is connected to the 2nd segment we need to flip it:

if (S[0].A == S[1].A or S[0].A == S[1].B) then reverse(S[0]);

http://postgis.refractions.net/docs/index.html – main postgis reference manual
http://www.postgresql.org/docs/ – main postgresql docs
You might want to look for plpgsql language examples


You can translate S[0].A == S[1].A into something like:

distance(st_startpoint(seg0), st_startpoint(seg1)) < tolerance

B. now we need to check the rest of the segments assuming S[0]

for (i=1; i<count(S); i++) {
if(S[i-1].B == S[i].B) then reverse(S[i]);

  1. now all the segments are order correctly from start to finish. There are some corner cases that you need to check for and deal with, like the start and end are on the same segment and there is only one segment in the result. You might need to check for gaps between the segments, but if the data was prepared correctly you should not need to worry about this. Now we need to trim the first and last segments. Look at the postGIS linear referencing functions for the tools to do this.

A. first we trim the start, we assume “start” is the start point for the route. We have already flipped it if that was needed. We can think of the problem like this:


where A->B is S[0] and P is our "start point. We know that the 2nd segment is connected to B so we want P->B:

S[0] = `**ST_Line_Substring**(`S[0]`, ST_Line_Locate_Point(S[0], start)``, 1.0);`


B. likewise we need to trim the last segment, it has also been flipped if needed. And this problem is:


Where A->B is the last segment and the n-1 segment is connect to A so we want A->P in this case:

S[n] = **ST_Line_Substring**(S[n], 0.0, ``**ST_Line_Locate_Point**(S[n], end)``);

So this is the basic algorithm. You can see it is fairly simple and straight forward. The trick is converting this into plpgsql language. You typically do not work with arrays in plpgsql, but with record sets and set returning function. A lot of people that are more familiar with PHP, get the results back in PHP and post process the data there.

See what you can do with this. I'm also going to post this to the pgRouting list so other can help and learn for this. If you are not subscribed to the list you should be as there are lots of people there that can help if I'm not available.

Thanks for your call today and best regards,

Thanks and take care.
I hope that together we strive to achieve excellence for a better world in this wonderful field and for all newcomer generations.

Cléber D. Arruda
Kämnärsvägen 33C
226 46
Lund - Sweden
Phone +46737762526
E-mail: cleverdo@gmail.com

Peace and Love Always.

Cléber D. Arruda
Kämnärsvägen 33C
226 46
Lund - Sweden
Phone +46737762526
E-mail: cleverdo@gmail.com

Peace and Love Always.