[Routing] propose a new data structure for routing

Frederik Ramm frederik at remote.org
Tue Mar 25 15:35:22 GMT 2008


Hi Digitalmobilemap Digitalmobilemap,

> I want to propose a standard routing design model for OSM internal  
> database, not for my application.

I think the OSM database should concentrate on collecting "first- 
hand" data. Anything *derived* from that does not have to be stored  
in the central database, it can be stored in some sort of external  
service (if it should be used by everyone) or locally with the  
routing app.

Storing derived data - e.g. the length of a way - in the database  
itself would mean that we'd either have to keep it up to date with  
triggers, or every editor uploading a changed version of the way  
would need to be aware of that extra info and update it accordingly.  
Why should we burden the central database with that?

The same with your idea of specially marking "routing nodes". First  
of all, not everything that is a routing node for cars is also a  
routing node for bicycles. And second, the "routing node" property  
would either have to be kept in sync by triggers or all editors would  
have to do it. I'd much rather have the routing software compute  
whatever it needs for itself.

I don't think that rouing on live network data is very important;  
routing on data that is a day old should be sufficient. So the  
routing software has all the time in the world to bring the data into  
a format it wants to use.

>>> In order to do routing with OSM data, we need to have routing nodes
>>> and graph data in osm database.
>>
>> No
>
> I am talking about building a graph data (relations or links  
> between a routing node to other routing nodes) in OSM database. If  
> you say No need a graph data  then how we do routing? Every routing  
> application need graph data.

I said "no" to graph data *in the OSM database*. Of course you need  
graph data. You just don't need it in the central database.

> Right now, OSM just capture one-way direction from a point to a  
> point within a way only. It has not yet capture a relation between  
> a way to routing nodes. It has not yet capture which point id is a  
> junction between ways.

These things can be computed from our existing data, they do not need  
to be stored explicitly.

> I don't like the idea that everyone build their own graph data for  
> OSM and write their own routing application.

I like that idea very much. Why force everybody to go along with a  
routing data model that one person (or group of people) has thought  
out? It may not be ideal for the routing application the individual  
has in mind... why can't everybody do what's best for him? We're all  
open source, so if you write a routing app and don't want to to re- 
invent the wheel then just take someone else's code - but if you  
happen to want to re-invent the wheel because you have special  
requirements, then you can do it.

> If you decide OSM is not for routing and wait for others to build  
> routing solutions for OSM, it may become a mess routing solutions.  
> I thought this routing email list is for building internal routing  
> solution for OSM. But it is not. This routing email list is for  
> building routing solution outside OSM's core, isn't it.

The core competency of OSM is collecting the data that makes up a  
free world map. We do some auxiliary stuff as well, for example we  
provide a slippy map. We do that mainly to "showcase" what our data  
can be used for, not because we believe that it is our goal to  
provide rendered maps. The same is probably true for routing; if we  
could easily provide some sort of routing app on our web site, we  
might do that to showcase our data, but in the end, routing is a  
possible *application* of our data, and not something we need to do  
ourselves.

So yes, basically I think you're right, this list is about how to do  
routing with OSM data, not about how to do routing inside our central  
database.

> I disagree with you that  whether a certain node is a routing node  
> is duplicate information.


> Not all my propose data structure is DERIVED data. only estimated  
> travel times is derived from distance and maxspeed. The relation  
> between way and routing nodes, the relation from a routing node to  
> other routing nodes and the distance between routing nodes ARE NOT  
> DERIVED data.

Then maybe I misunderstood what you mean by routing node. I thought:  
A routing node is any node where you can chose between two or more  
roads, i.e. a node in the routing graph. Currently, if I want to have  
a list of all routing nodes, I need to analyse our data and find out  
whether one node is used by more than two ways that represent roads,  
or at least that's what I thought. Then, the information whether  
something is a routing node would clearly be derived. - If you say  
your routing nodes are not derived, then what additional information  
comes into play? I.e. when would a node where three roads meet NOT be  
a routing node, or when would a node in the middle of a road BE a  
routing node?

> You are not convinced by my arguments because you are thinking I am  
> proposing the routing solution for the benefit of my routing  
> application. You are thinking of I am expecting OSM to pre-compute  
> or to pre-optimize graph data for my routing application. But it is  
> not the case.

No, I think that you want to create a framework for all routing  
applications to use but I think it is BETTER to let every routing  
application choose their own framework instead of forcing them all to  
use whatever we currently thing is best!

Bye
Frederik

-- 
Frederik Ramm  ##  eMail frederik at remote.org  ##  N49°00'09" E008°23'33"







More information about the Routing mailing list