[OSM-dev] Some help with proj.4

Dirk-Lüder Kreie osm-list at deelkar.net
Sun Apr 8 18:40:09 BST 2007

Hash: SHA1

Stefan de Konink schrieb:
> Hi Frederik,
> On Sun, 8 Apr 2007, Frederik Ramm wrote:
>> I don't want to be rude here but the words "dream on" have just crossed
>> my mind ;-)
>> Maybe I, in turn, see too many difficulties where there are none, but I
>> do not believe that simply applying a standard path finding algorithm
>> will do the trick, at least not on usual hardware, because of the sheer
>> size of the graph.
> Nothing is simple until you implement it :) Maybe doing some prototyping
> in Prolog/Mercury/Haskell will give us an idea how 'hard' it is. (And
> maybe how much caching we can use.) For serveral homework assignments in
> Prolog we needed to implement trainrouting with A*, ofcourse OSM is
> bigger graph ;)
> So before we are going to flame how hard it can be ;) Lets think about a
> way how to 'strip' roads from the OSM into junctions with graphs. Then the
> theoretical stuff can be applyed on the practical side.

Some Ideas about how you can reduce the size of the Problem:

1. the graph nodes are relatively close to each other (few shortcuts for
 groups of nodes)

2. the optimal route will be in an area between the start and endpoint
that doesn't extend too far to the sides. (except for short routes)

Disclaimer: I have next to no knowledge of graph theory.

Dirk-Lüder "Deelkar" Kreie

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


More information about the dev mailing list