[OSM-dev] Some help with proj.4

Stefan de Konink skinkie at xs4all.nl
Sun Apr 8 12:01:33 BST 2007


On Sun, 8 Apr 2007, Frederik Ramm wrote:

> > I'm in exactly the same situation. Target is a free car routing thingie.
> > Why I mentioned cairo is simple, there are virtually no embedded 3D
> > systems.
>
> Just chipping in here; I am also very interested in the routing topic,
> but focusing on "route planning", i.e. the computational aspects of
> finding optimal routes from A to B on OpenStreetMap data - at the moment
> I do not care about live navigation capabilities or real-time operation,
> at the moment I'd be happy if my program gave me *any* route that is
> driveable ;-)

It is actually 'very' simple. Lets take the A* algorithm. There are vector
paths for roads. There needs to be some heuristics defined for the actual
routing but that is more like an optimalization.

Because we know which roads are primary, highway, etc. we have also
knowledge about what are the fastest roads. (Excluding traffic jam
information).


First, we don't want to store every road in memory. So exporting roads
we want to search to something like sqlite in a data format that defines
junctions (graph) and how to draw them.

For the search we query this data and take an heuristic approach. And
query SQLite in a smart way.

Something like:

SELECT * FROM junctions WHERE (start = $myfrom AND end = $myto) OR
(start = $myfrom AND end = $myto AND direction=2);

Where you get back the next junctions to take.


Todo:

- Define storage format (it is nice to have extra features like water
somewhere too)
- A way to walk roads: direction independant
- Junction recognition: only store from junction to junction
- Diff between updates (OSM changes quick you want to be able to update
SQLite data quick too)




Stefan





More information about the dev mailing list