> 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. 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. 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?". 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. > We've been discussing quadtrees at the VUB.ac.be in the years 1987 and > further. And they are still in use in many applications. --Dennis _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
