-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 David Lynch schrieb: > On Fri, Oct 10, 2008 at 12:32, flo Detig <[EMAIL PROTECTED]> > wrote: >> ps: some random thoughts: What about even more layers? In case of >> greedy (dijkstra-/a*-style) BFS you could start 'searching' until >> the first higher-layer-node appears, for instance a >> residential-junction. After that stay on that layer and only >> examine 'arcs' to other junctions until you reach the first >> 'secondary-layer-junction', after which you can ignore
I thought about such a thing but found that to only work out if you are loading complete layers into memory. If you load single ways with their nodes and attriutes from your data-store you can stick to Dijkstra/A* and know to get an optimal result even in cases where there is a higher-order-road near to start- and one near to end- node but both are in the opposide direction of the short direct connection from start to end. Checking out the ways with the lower cost, e.g. length*(1-order) will take care of all the layering you need. Here it makes sense to use the order of the road (motorway,motorway-link,trunk,trunk-link,...,track) to order the ways in your storage, so that higher order roads are feched faster and cached longer then lower order ones. > > I'm working on testing an idea that works backwards from the > destination and forwards from the origin at the same time and stops > when they intersect each other. That sounds like it would be a > solution to your problem. I think this will be slower then to go from target to start because it cripples your caching. In your case you have half your memory filled with cached roads from the target and half from the start, both with reduced hit-rates compared to a single cache storing local roads around the one area you are currently examining. Marcus -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFI8Ml+f1hPnk3Z0cQRAofbAJ46V8C5KWjk2rNToGy4nIcAgsyFXwCeI3A5 8pdrOQAN7RtaAcuCXhnGbuE= =H1Vi -----END PGP SIGNATURE----- _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
