[Routing] OpenGPScout

a.leupin at hispeed.ch a.leupin at hispeed.ch
Mon Nov 19 11:58:52 GMT 2007


Hi Marcus,
here some answers to your remarks
>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA1
>
>Andreas Leupin schrieb:
>> Hello all,
>> I have just renewed my webpage on www.leupinfo.ch/OpenGPScout concerning
>> the Open Source Project "OpenGPScout" (Translation of most of the page
>> to english, new pdf-files about the concepts).
>> I would be interested especially in your opinions about the main
>> pdf-file and the concepts roughly described there...
>
>Hello Andreas,
>
>I had a look at the data-format you described.
>> 
>> a) road-segments (minimum data - additional data to be stored in other files)
>> 
>> - node reference at the "beginning" of the segment ("0"-end):   3 bytes (2 bytes actual node reference, 1 byte for the relativ definition of the tile, on which the node is)
>
>How do you number your tiles that 1 byte is enough to reference a tile?
>Are 2 bytes enough to reference a node? How do you encode them?
>(There are way more then 2^16 nodes in OSM so directly storing their id
>is no option.)
>

The reference of the tile is relative to the actual tile - with 1 byte I have  the possibility to reference +/- 7 tiles in either direction, what should IMHO be enough, because no single road-segment is longer than this...
2 bytes for the reference of a node also is enough, because I know additionally the reference of the tile, which the node is located on. With tiles having an expansion of 0.008 x 0.008 radians there shouldn't be more than the appr. 65000 nodes or road-segments per tile, that I can reference with a short-integer... 

>> - node reference at the "end" of the segment ("1"-end):   3 bytes (2 bytes actual node reference, 1 byte for the relativ definition of the tile, on which the node is)
>> - Definition of the position of the segment within the nodes: 1 byte (this information is used for a faster execution of the routing algorithm)
>> - velocity- and road category: 1 byte ( 4 bites respectively)
>> - length or driving time for the segment: 1.5 bytes (resolution appr. 5m or 5 s, to be discussed)
>
>Why are you storing these values? Do you use a condensed road-network
>with all nodes that are not end-nodes or intersections removed?
>

In principal I do not need the one byte defining the segment within the node. I need the other data to calculate not only the shortest, but also the fastest route (assuming, that I store the shape of the road segments in a separate file, which is - however - not used for the routing calculation itself...). Wether it is more conveniant to use the length or the driving-time as the relevent cost-factor for a road-segment is arbitrary

>> - allowed direction, driving restrictions, suitable vehicle categories etc.: 1.5 bytes
>> - reserved for additional informations: 1 Byte
>> 
>> 11 bytes in total per segment (fixed length)
>> 
>> 
>> b) nodes (minimum data), 
>> 
>> fixed length:
>> - number of incoming/outgoing road segments: 1 byte (3 bits for the number of segments (maximum of 8), 5 bits for the type of node (e.g. turn-about etc.))
>> - coordinates of the node: 3 bytes (together with the tile reference the position is defined to about  2.5 m)
>
>How do you encode your coordinates?
>

To get the coordinates I need the (absolute) tile reference of the tile the node is on. Because I have tiles with a defined extension (0.008 x 0.008 radians) it is possible to calculate the coordinates of the lower-left corner of every tile knowing its reference. Then I need 1.5 bites to define the coordinates of a node relatively to this lower left corner.

>> - Adjacent end of the road segments: 1 byte (1 bit per segment, 0 = "0"-end, 1 = "1"-end)
>> 
>> variable length:
>> - reference to a incoming/outgoing segment: 2 bytes per segment
>> - Which other segments can be reached from the actual segment:  1 byte per incoming/outgoing segment  (used for coding turn-restrictions etc.)
>> - Definition of the tile on which the segment is mainly located: 1 byte per 2 incoming/outgoing segments (??)
>
>
>
>Marcus

I hope, this answers your questions

Andreas
>-----BEGIN PGP SIGNATURE-----
>Version: GnuPG v1.4.6 (GNU/Linux)
>Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>
>iD8DBQFHQSOxf1hPnk3Z0cQRAhmLAJsFI7WcSfIIxAcVLav6Xsvr0AMOtgCg2IOc
>TscvIw3S6mmYj871B1+f9x8=
>=BOCr
>-----END PGP SIGNATURE-----
>
>_______________________________________________
>Routing mailing list
>Routing at openstreetmap.org
>http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
>
>




More information about the Routing mailing list