[Routing] propose a new data structure for routing

[Marcus Wolschon]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Digitalmobilemap Digitalmobilemap schrieb:
| The purpose of these new routing nodes is to make routing data
official support
| by osm data.
|
| Right now, osm dos not have any properly way to model or capture routing
| information. So each and every routing applications have its own way to
| implement routing solutions.

Actually they all implement some form of reading OSM-XML-Data into their
internal data-format and they all need all the other data too because
they also have to render a visual map to the user.
* you need to transfer more data to the application (think mobile)
* the information is completely redundand
* you need to select what gets included (motorways? cycle-ways?
~  field-tracks? public transport? pedestrian-stairs?)

|> What is your reason for violating the first
|> normal-form of database-design?
| The reason why i dont want routing node refer to node id to get lat
and lon is
| because:
|
| 1. if routing node need to refer to node id to get lat lon then you
need to
| store billion of node in memory and search though billion of node just
to get
| the lat/lon of a routing node --> it will slow down the routing algorithmn
|
| 2. if routing node has lat/lon by itself it will be very easy to clip
a set of
| routing node within a bound. For example: if i want to calculate a
route within
| london city, i just need to run this ssql statement:

* we are talking about the data-format on the wire, not in-memory or
~  on-disk. You are free to store the coordinates however you like to
~  and get rid of any indirection while loading new map-data.

| select * from routing_node_table
| where lat and lon within london's boundary

This is much too simplified (imagine the memory-management for routing
from Peking to London) but again, you are free to store your coordinates
in your own, local database however you like to. External applications
never do SQL-queries to the osm-database(s) anyway. The data-format you
see is actually our API for editors and data-export/import.

If you want your application to run faster by not considering the nodes,
fine. Many use an internal data-format without any osm-primitives. But
this is your internal data-format.
If you want others to use it, write a specification for it and a library
that others can use in their routing- and navigation-apps.

| Why not standardlize routing information in one place and every routing
| applications refer to the same place? Right now, OSM can not calculate
routing
| by itself.

* OSM cannot even render visual maps by itself. That's what we have
~  renderers for. OSM is a database where we collect data independend
~  of it's purpose.
* Every routing-application is different. While one can only route
~  on a tiny map in memory the next uses a huge local PostGIS-database.
~  While one does routing for pedestrians another does for bicycles and
~  the third for only the most usual types of cars.
* For a routing-application OSM is just one data-source. There may be
~  other maps to use. (e.g. The garmin-map-format is well known and
~  can be used if the user purchased that map.)

| Routing information should be part of OSM as a whole. The main purpose
of OSM is
| to model the map in the real life and anything belong to the map.
|
| If OSM does not have proper way to capture routing information then
its data
| model is not completed.

It does have. The data-format of it's API is optimised for simple
editors but it captures all the data needed for routing too.

While it is nice to have a condensed map that is only usefull for
routing, this is:
* as well done outside the OSM-API-Code
* uses more bandwith for data that is 100% redundand
* usefull only for one type of routing-application
* not usefull anymore for the local rendering of maps
~  that a routing-application must also do.

| traveltime is just an pre-estimated factor, it can be adjust by the
routing
| application at run time by using parameter.

* Actually this is not a linear relation at all.
~ If you want half your routing-application done
~ by OSM then write a service that given a street-address
~ returns a route with coordinates and driving-instructions.
* Travel-Time is not the onl metric. With your condensed data
~  it is no longer possible to route by "shortest route" or
~  "most fuel-efficient route" or even by a better metric for
~  "fastest route". "avgSpeed(highway-type) * distance" is
~  not the best we can do.

| <<<
| Also the selection of osm-ways that are relevant for
| routing depends on your vehicle. Bicycles and motor-
| scooters cannot use motorways. Heavy trucks cannot
| use certain bridges...
|  >>>
|
| the routing application need to be flexiable enough to handle the
distance and
| traveltime factors. By changing it at the run time, the routing
applciation
| can calculate relevant route for each type of vehicle.

* you transmit much more data then is actually considered for routing
(As there are routers for bicycles and pedestrians aout 90% of the ways
~ may be returned while you only need 30% in theory and for one your only
~ the single motorway that connects your start-area to the target-area.)

Your data may be usefull to a few routing- and navigation-applications
to have in parallel to the full map (for map-rendering) so feel free
to implement it as an external converter or better as a library with
an efficient data-retrieval from local disk/database.
All the data is there and doing filtering on tags, polygon-
simplification and merging of nodes into the ways is trivial to do.


Marcus
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFH31jpf1hPnk3Z0cQRAl+qAJsHt1XQYhZFQIEIA7ip+ZGdg54ZPwCcC/qZ
eeI9BgL/rN/CVQpNCzWUlxY=
=l13z
-----END PGP SIGNATURE-----