[OSM-talk] routing across open spaces

Anthony osm at inbox.org
Tue Nov 30 23:08:27 GMT 2010

On Tue, Nov 30, 2010 at 1:24 PM, Felix Hartmann <extremecarver at gmail.com> wrote:
> I don't think routing over areas will ever work well. It might work for 2-3
> areas and that is already really difficult for calculation. Just routing
> onto an open space is no problem, but calculating a route over a longer
> distance, would mean that for any place the time it needs and the way to
> take have to be calculated as a way, before using it for autorouting. Hence
> in the end the only thing that will work, is that there are invisible ways
> for routing with very low priority added to the map, because everything else
> won't be feasible for longer distances.

Why low priority?  Just take the n ways which connect to the area, and
run http://www.loria.fr/~lazard/Publications/Curvature-constrained_shortest_path_in_a_convex_polygon/Curvature-constrained_shortest_path_in_a_convex_polygon.html

> As long as there is no consensus or widespread use, of how map rendering
> should add such invisible ways, no area should be considered to be
> routable.....

How can there ever be widespread use if no areas are considered
routable?  Sounds like a chicken and egg problem to me.

> Real polygon routing is AFAIK with the currently developed algos impossible
> (but also does not exist in reality.

I don't understand what you mean by "real polygon routing".  We're
talking about a router here, so the only route that matters is the
shortest path through the area which takes you from one way connected
to an area to another way connected to an area.  Given n such ways,
there are n choose 2 such paths, which can be calculated via the
algorithm I linked to above.

More information about the talk mailing list