[Routing] generalized routing format

[Tristram Gräbener]

Hello,

I think we'll have to develop two different formats :
* one binary with maybe indexes, some mmap-able structure, etc. For
dynamic loading of the graph etc.
* one more general

I'm personnaly more interested in the general model (I'm working on
multimodal transportation, and I need different graph structures for
cycling, foot, car etc.)
What I would like is something exportable into a database (postgis for
example, but any should work)

The tables would be

Nodes[node_id, lon, lat]
Links[link_id, source*, target*, geometry, way]
Properties [way,  key, value]

The nodes isn't really needed.
What I call a link, would be le nodes of degree 2 merged (or ways
splitted) and thus the arcs needed for routing.
The geometry column is a format used by GIS databases (called "well
known text", generaly also in a binary format) allowing to use
geographical indexes
The properties allow to handle any future property that will be added
to the osm data.

This allows :
* using pgrouting (a cost and rcost column might be missing, but as
that cost depends on the user [distance ? time for a car, a bike ?] it
shouldn't be included by default
* using ogr2ogr to convert to any other GIS format
* graphical rendering with the geometry information
* using spatial sql-request if you have a spatial database

It's quite versatile, there is no assumption about the future use of
the data (except routing). Of course it's not the best for embended
systems, and won't probably be well suited if you want to load the
graph progressively (routing through the world)

On Wed, Oct 15, 2008 at 11:23 PM, Marcus Wolschon <Marcus at wolschon.biz> wrote:
> On Wed, 15 Oct 2008 23:45:46 +0200, flo Detig <florian_detig at yahoo.de>
> wrote:
>> Marcus Wolschon wrote:
>>> I think it would be better to discuss basic
>>> storage and indexes first before going on
>>> about special optimizations.
>>>
>> I agree with that.
>> Is there some lowest common denominator for a generalized routing format?
>
> We have the OSM-XML that definately contains all data but is unusable for
> large maps and supports no indexed access.
> We have a MySQL and a PostGIS -schema that need no on-disk -format.
> Some kind of on-disk-format that supports:
> * getWaybyID(), getNodebyID(), getRelationbyID()
> * getWaysForNodeID()
> * getAttributeofNodeID(AttribName)
> * getAttributeofWayID(AttribName)
> * getRelationsofWayID()
> * getRelationsofNodeID()
> and most important:
> * getNodesbyBoundingBox(north,south,east,west)
> would be nice.
>
> If it where uncompressed, so it can be mmapped() that would
> help in avoiding having to write your own caching-strategy.
>
> optional:
> * mutable format
> to support updating parts of the map without having to
> re-generate the complete map-file (potentially very, very large).
> * getWaybyBoundingBoxAndAttribute(n,s,e,w, attribName,
> allowedAttribValues[])
> * keep wayIDs and nodeIDs as well as all nodes that originally belonged
>  to a way from OSM, so osm-xml-diff -files can be applied to update the
> map.
>
> The format need not consist of only a single file.
> e.g. indexes can be in separate files and ways, nodes, relations and
> attributes
> each in their own file. This can make it easier to grow an index
> and make the files for way,node,relation contain only records of a
> fixed size.
> You may also separate the (possibly normalized) data required for routing
> from the
> larger data-set required for realtime map-rendering with or without
> doublicating information between the 2.
>
>> Something everyone could use / need who works on routing osm data?
>> There is a nice visual description by Michael Josenhans in the wiki
>> http://wiki.openstreetmap.org/index.php/OSM_Routing_Data_Layer
>> As a first step merge the intermediate nodes of degree two?
>> Is this simple enough to fit everyone?
>
> No. You need to have nodes of degree 2 somewhere in your
> routing-application
> because the application need not only do routing but also render the map
> to show the route to the user.
> (Giving a user only a list of [nodeID, wayID, nodeID]-tupels will serve no
> one.)
>
> Marcus
>
>
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/routing
>