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

[Stephen Woodbridge]

Adrian,

Look at pgRouting. http://pgrouting.postlbs.org/

-Steve


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
> 
> _______________________________________________
> mapserver-users mailing list
> mapserver-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/mapserver-users