[pgrouting-users] Re: Hi It's Cleber Arruda from Sweden.

Stephen Woodbridge woodbri at swoodbridge.com
Mon Jan 24 20:40:23 EST 2011


On 1/24/2011 5:44 PM, Cleber Arruda wrote:
> 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 
> <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]);

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]);
}

2. 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/
|
> 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 at gmail.com <mailto:cleverdo at gmail.com>
>
> Peace and Love Always.
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20110124/ae2a59b8/attachment-0001.html


More information about the Pgrouting-users mailing list