[RouterGeocoder] Poly line features

Stephen Woodbridge woodbri at swoodbridge.com
Sat Mar 28 01:45:13 EDT 2009

Ashraf Hossain wrote:
> Hello steve,
> Thanks a lot for your comments.
> I think your thinking and my thinking is almost same.
> I was also thinking about the router library that should be added in
> the mapserver.
> "Yes, this all sounds good. The other missing piece you might want to
> consider adding and supporting is turn restrictions."
> --> Can you tell me some more details about this?

Typically turn restrictions are stored at the node where the restriction
is applied and each restriction needs to consist of parent,
grand-parent, ... as needed to describe the restriction. For example:

                  |    (divided highway)

At E you might have:
not F from B, C  (no U-turn, but C-B-E-H, G-B-E-H or G-B-E-F ok)

We might also want to consider that there are different classes of 
vehicles, like emergency, trucks, auto, bicycle, pedestrian, etc. and 
there may be different sets of restrictions based on time of day and/or 
vehicle class if you want to get pedantic about it. So we might want to 
be able to store different turn restriction based on the class of the 
problem being solved.

> And another issue,
> In routergeocoder group I got a reference of a research which proves
> that Dijkstra is not efficient for high performance routing server and
> the researcher proposed a new algorithm. I missed that link and I
> failed to get access the the group emails of that days.
> Can anyone send me that paper? I am too much interested about that.

There are a lot of algorithms like Dijkstra, A* Search, Shooting Star, 
bi-directional search, etc. You might want to look at the Boost Graph 
Library which implements many of these algorithms in C++ and this might 
be a good starting point for the development of a routing engine.

pgRouting uses the Boost libraries for example.

Depending on whether or not you plan to release your code as part of the 
OpenRouter project you might want to consider licensing. The Boost 
Libraries have a liberal licensing policy which is more acceptable to 
commercial organizations that might be will to supply funding once the 
project gets started. These same organization tend to shy away from GPL 
licenses because it potentially pollutes other code they might want to 
bundle with it. We have had a lot of discussions about licensing and the 
PAGC project just change their license to an MIT-style license and we 
have some people trying to drum up some funding to help offset some of 
the developers efforts. This has worked similarly well with the 
mapserver project.

> Steve  thanks  alot for your comments again. I will be more happy if
> you guide me to develop router geocoder library.

We are happy to help on this list and hope you have plans for 
contributing code back to the list.

Best regards,

> With Regards
> Roni
>> Hello Roni,
>> Ashraf Hossain wrote:
>>> We can make a graph builder which will create 3 things.
>>> 1. Connectivity information for polylines.
>>>    It will contain the the vertex numbers for each polyline feature.
>>> 2. Graph file for the whole polyline layer.
>>>     Vertex edge collection.
>>> 3. Weight matrix for the graph.
>>> Primarily this can be created from the shape file and the dbf(may be
>>> there contain a minimization parameter information like
>>> routingtime,secured road,cost ...etc.)file. Later it will support all
>>> kind of format.
>> Yes, this all sounds good. The other missing piece you might want to
>> consider adding and supporting is turn restrictions.
>> While this data can all be generated from shapefile data and data in other
>> formats, the data required for routing is usually in a different format to
>> be efficient during the routing phase. Therefore it might make sense to
>> define these data structures a schema that can then be mapped to data
>> structures in an implementation language. This would make for a more modular
>> approach that would allow us to decouple the structure from the physical
>> storage and make the code more modular and reusable.
>>> There will be a routing layer in the mapserver which will read the
>>> information from this files and then can draw the shortest paths.
>> While this would be an interesting possibility, have a generic routing
>> engine as a library, would allow us to plug it into mapserver, or any number
>> of other applications. Basically mapserver only needs the resulting polyline
>> and their are lots of ways we could pass that to mapserver.
>>> There will be a text driving direction generator class which can be
>>> showed in the client side.
>> Correct, In fact if you are using OpenLayers as a client, then a simple Ajax
>> call from the client to generate the route can return the route and the
>> driving directions in XML for display. Here is a demo I put together using
>> pgRouting with some of my own mods:
>> http://imaptools.com/leaddog/routing/dd.html
>> To use it zoom into one of the citys, or click one of the city links on the
>> left then select a start and end and display the route and directions. If
>> you use FireFox and FireBug you can see the requests and responses.
>> Sometimes it fails to route so change the start and ends until it does.
>>> And finally there will be another request for the navigation client
>>> support.
>>> From the index tree of the polyline it will select the source
>>> feature(like feature info ) and same for the destination.
>>> We then can use the shortest path algorithm for generating the shortest
>>> path.
>> Yes, this is exactly what I do in the demo linked above.
>>> Please help me if I done any mistake.
>>> In the second or third phase I want to add the Bus and car hybrid
>>> routing(google already implemented this).
>> There are lots of additional feature that can be added. If you have data for
>> public transit systems and walkways then you can do route planning for
>> pedestrians also.
>> Best regards,
>>  -Steve
>>> With Regards
>>> Roni

More information about the Routergeocoder mailing list