[mapserver-users] Any pointers on calculating the shortest route between 2 points?

[Ben Madin]

Adrian,

I think you could look at pgRouting (http://pgrouting.postlbs.org/)  
and especially work through the tutorials. There are functions for  
building network topology in it.

I guess it does mean using postgis, but if you aren't already, I think  
it is worth the time to at least look into it.

good luck.

cheers

Ben

On 24/08/2009, at 5:47 PM, Adrian Popa wrote:

> Hello everybody,
>
> Sorry if this question is not specific to mapserver, but I was  
> wondering if I could get some pointers on where to start with this  
> problem.
>
> So, I have a layer with street numbers for some cities, and I want  
> to be able to display the route between 2 such points. I've done  
> something similar in the past by using Boost (as a perl module) and  
> loading the network as a graph and using Dijkstra algorithm to  
> calculate the shortest path between 2 points. The problem is - the  
> data I had clearly defined the nodes of the graph (vertexes) and the  
> edges (links) between the nodes, so I was able to easily build the  
> graph and interpret the results.
> The data I have now looks like this (for a record):
>
> OGRFeature(Streets_geocoding):1123
> Name (String) = West St
> FromLeft (Integer) = 3
> ToLeft (Integer) = 5
> FromRight (Integer) = 12
> ToRight (Integer) = 32
> Link_ID (Real) =  588532637
> Judet (String) = TIMIS
> Localitate (String) = TIMISOARA
> L_PostCode (String) = 300609
> R_PostCode (String) = 300609
> Style = PEN(w:2px,c:#ff00ff,id:"mapinfo-pen-2.ogr-pen-0")
> LINESTRING (21.17921 45.751309999999997,21.18102 45.753790000000002)
>
> The problem is I have lots of small links (street segments) but  
> without an obvious way to link them together (maybe Link_ID is  
> something useful - I'll look into it).
>
> My question is: In your opinion - how is "routing" implemented on  
> maps (e.g. on GPS receivers) - Do the maps have special information,  
> or should I manage with what I have?
>
> Any pointers are helpful, thanks
>
> Regards,
> Adrian

-- 

Ben Madin
REMOTE INFORMATION

t : +61 8 9192 5455
f : +61 8 9192 5535
m : 0448 887 220
Broome   WA   6725

ben at remoteinformation.com.au



							Out here, it pays to know...


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/mapserver-users/attachments/20090824/9f413c23/attachment.html