On Tue, 3 Nov 2009 08:20:54 +0100, Dennis Luxen <lu...@kit.edu> wrote: >> I've always asked myself why we wouldn't try some quadtree algoritm >> for >> parsing/routing/filing our data... > > Well, Quad-Trees don't help you much when it comes to routing. It's a > data structure that helps answering queries that ask for a nearest > neighbor to some coordinate. For routing it is the easiest to use a > simple adjancy list representation for the graph.
Actually it does. Because before you can do the actual routing you have to find the nearest Street the driver can actually be on and you have to find all the target-locations. For navigation as opposed to route-finding you also need to continously render a moving map and for that you need to answer range-queries VERY fast. This part is actually more demanding on the datastructures used then simply getting all ways a node is connected to, the next+prev node along a way and some tags on the ways/nodes you are evaluating in your routing-application. Also because the rendering is a realtime-case while route-calculation happens usually only once. > And when it comes to > a serious routing scenario, where you have millions of edges and nodes > then you need to do specialized preprocessing. Dijkstras classical > algorithm and related heuristics don't scale that well on large data > sets. There are several exact speedup-techniques for that problem. Can you please point out a few and maybe even add links to them on the "Routine" wiki-page? This may be interesting for a lot of readers. > Again, a Quadtree is an index structure that answers neighborhood > queries fast like "Whats the nearest neighbor to coordinate xy?" or > "What is all information we have for a certain region or tile?". As I pointed out. Very usefull. It need not be the only index. > Routing on the other hand implies some connection between the nodes > that is easier (meaning: more efficiently) to exploit than a spatial > index. On the other hand, I have to acknowledge that there is > scientific work, that speeds up Dijkstras algorithm by employing tree- > like data structures but only among other algorithmic techniques. (Another index by ID and a backward-reference from node to way and from node/way/relation to relation are a very, very good thing for the route-calculation.) Marcus _______________________________________________ Routing mailing list Routing@openstreetmap.org http://lists.openstreetmap.org/listinfo/routing
