Hello,
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.
- 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]);
See:
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
http://postgis.refractions.net/docs/ST_Reverse.html
http://postgis.refractions.net/docs/ST_Distance.html
http://postgis.refractions.net/docs/ST_StartPoint.html
http://postgis.refractions.net/docs/ST_EndPoint.html
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]);
}
- 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:
A----------P-----------B
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);`
http://postgis.refractions.net/docs/ST_Line_Substring.html
http://postgis.refractions.net/docs/ST_Line_Locate_Point.html
B. likewise we need to trim the last segment, it has also been flipped if needed. And this problem is:
A---------P------------B
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,
-Steve
[http://imaptools.com/](http://imaptools.com/)