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

[Adrian Popa]

Thank you both,

I wasn't aware of it. I will look into it.

Regards,
Adrian

Stephen Woodbridge wrote:
> 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
>