Intersection Consolidation

[tedsteiner]

I think it would significantly speed up routing if intersections within a certain radius in a map could be consolidated into a single node.

OpenStreetMap treats divided highways as separate one-way roads. This means that when divided highways cross one another, this results in 4 intersections rather than just 1. If we could represent this as a single intersection, Dijkstra's algorithm would route faster. Also, the intersections found in an environment would be more useful for higher-level tasks, such as displaying directions ("turn left, turn right").

The way to approach this is probably to add a new node in the center of an intersection to the global list of nodes, and replace all nodes within a certain distance of it that belong to highways with references to the new node, instead. These existing nodes shouldn't be deleted, in case we want to do a "refinement" step on the routing, and they should still be used for plotting.

[garborg]

This sounds great -- it would be nice to do it after there are tests for respecting turn restrictions, but maybe it would be just as easy to add turn restriction adherance later (if it's not being handled -- haven't gotten that far in testing).

[tedsteiner]

I never thought of turn restrictions. That's a good idea. I found this page very helpful when I was doing the routing code, have you seeing it? http://wiki.openstreetmap.org/wiki/Routing#Highway-type

Right now I have the highway speeds set very arbitrarily (I just picked them), so if this is to be used for realistic routing we might need to look into finding more accurate speed data. Especially because I don't think the speeds translate well to other countries. I picked them to look reasonable for Boston, just as a start/default.

[garborg]

Thanks for the link -- I hadn't seen at least that section of the page, but I've wondered about speed data.

[garborg]

I'll try to look into in more, but I think highways speeds might not be realistic within the U.S., either -- no real evidence -- just doing a similar analysis to something I'd approximated with commercial maps before, and it looked like small roads were incurring significantly higher cost using the library.

Worth looking into what OSM routers do.

[tedsteiner]

Yeah, I just guessed these. And I think I might have intentionally differentiated the road styles when I was testing some routing stuff. So it wouldn't surprise me if they're not optimally set yet.

[yeesian]

Worth looking into what OSM routers do.

just for future reference: Project OSRM and Pandana