start/end at nearest routable way

[emiltin]

consider this route: http://map.project-osrm.org/yn. if you move the start marker a bit south, just past the gate on the little path, you get "no route is possible". this is technically correct.

but i think it would be more useful if osrm would simply start at the nearest useful location.

the area on the map is filled with these small paths with gates. this mean that when you move the marker around, a lot of the time you get "no route possible", which is frustrating.

[DennisOSRM]

Yes, good catch.

The plan is to make these small segments only available on z16-z18 where you see them and (perhaps) know where you are dragging your mouse.

On 05.06.2012 08:31, Emil Tin wrote:

consider this route: http://map.project-osrm.org/yn. if you move the start marker a bit south, just past the gate on the little path, you get "no route is possible". this is technically correct.

but i think it would be more useful if osrm would simply start at the nearest useful location.

the area on the map is filled with these small paths with gates. this mean that when you move the marker around, a lot of the time you get "no route possible", which is frustrating.

[emiltin]

hmm yes a workaround perhaps. how would it work?

considering a more general solution - gates and other barriers effectives divides the map into separate islands. if the start end end markers are on separate islands, no route is possible. for practical use, it would make sense to move the marker the user is dragging to the nearest point generating a route, which would be the nearest point on the same island as the opposite marker is on.

i know you're doing some work on seperating the map into regions for speed reasons - could this be related?

[DennisOSRM]

hmm yes a workaround perhaps. how would it work?

Exploring connected components and then marking the small ones as such. The lookup of a nearest edge will then also get the zoom level as parameter and gracefully ignore edges from small components in certain zoom levels.

considering a more general solution - gates and other barriers effectives divides the map into separate islands. if the start end end markers are on separate islands, no route is possible. for practical use, it would make sense to move the marker the user is dragging to the nearest point generating a route, which would be the nearest point on the same island as the opposite marker is on.

The solution would be to start a route computation from several edges in the area simultaneously and then selecting a smallest one.

i know you're doing some work on seperating the map into regions for speed reasons - could this be related?

For memory reasons, speed will only be affected indirectly.

[emiltin]

if you're already marking separate "islands", you could just look for nearest point on the island the oppositve marker is in?

another idea - perhaps instead of zoom level you could use the distance between start/end?

[DennisOSRM]

if you already marking separate "islands", you could just look for nearest point on the island the oppositve marker is in?

It's not necessarily clear in which 'island' a marker is in. Think of start and end marker between just the same two regions.

nother idea - perhaps instead of zoom level you could use the distance between start/end?

That's a good idea, too.

[emiltin]

is a point not always closests to one specific way - and thus in a specfic island?

[DennisOSRM]

is a point not always closests to one specific way - and thus in a specfic island?

Think of a point right in the middle between two ways. Distances to both are equal.

[emiltin]

true. the same problem must exist when doing the standard 'nearest way' locaation?

[karussell]

Hi Dennis (maybe you know me ;))

I've implemented a very cheap (in terms of memory usage) location-to-id index which could solve this problem. But is is in Java: https://github.com/karussell/GraphHopper/blob/master/core/src/main/java/de/jetsli/graph/storage/Location2IDQuadtree.java

also see the unit test(s) for how to use it. Or ask me ;) also if you have questions regarding the spatial key stuff: http://karussell.wordpress.com/2012/05/23/spatial-keys-memory-efficient-geohashes/

[DennisOSRM]

Hallo Peter! Nice to hear from you!

I've implemented a very cheap (in terms of memory usage) location-to-id index which could solve this problem. But is is in Java: https://github.com/karussell/GraphHopper/blob/master/core/src/main/java/de/jetsli/graph/storage/Location2IDQuadtree.java

Thanks for the info. The problem here is different in two aspects. First, the index is in external memory and second it's more about flagging edges two be part of a 'small' component than of looking up a nearest neighbor.

also see the unit test(s) for how to use it. Or ask me ;) also if you have questions regarding the spatial key stuff: http://karussell.wordpress.com/2012/05/23/spatial-keys-memory-efficient-geohashes/

Geohashes and space-filling curves in general work quite nicely for point data. Unfortunately, the problem becomes harder for weak- and strongly intersecting line segments. We query for a point location, but the underlying data is segments. The problem is closely related to finding a corresponding Voronoi-Cell of edge segments in 2D-space.

Looking up date is generally fast. For the OSRM demo, we have a SSD that keeps the external-memory data structure for that and a single lookup is done in about 200 microseconds.

[karussell]

First, the index is in external memory

why is that a problem? E.g. when using memory mapped files this should make a difference in implementation. Or am I understanding this completely wrong?

and second it's more about flagging edges two be part of a 'small' component than of looking up a nearest neighbor.

ok, I see the underlying structure is quite different in your case

[DennisOSRM]

First, the index is in external memory why is that a problem? E.g. when using memory mapped files this should make a difference in implementation. Or am I understanding this completely wrong?

In external memory you need to minimize the number of memory accesses. Usually, only a small constant number accesses is feasible.

and second it's more about flagging edges two be part of a 'small' component than of looking up a nearest neighbor.

ok, I see the underlying structure is quite different in your case

[DrVanScott]

Some time ago i implemented an "hack" for this problem (My problem was, that start and end points were calculated and not set by a human, so chances to hit one island (or two - on each point) were rather high. First of all i created a slightly modified version of the "nearest" plugin, which takes an additional parameter to get the nearest, 2nd-nearest, 3rd-nearest point. I also increased the "lookup radius" (the number of observed tiles) of that code. The rest of the hack was implemented client side:

The routing problem "A to B" was devided in two seperate routes "A to F, F to B" where F is a fixed point, for which i made sure that it is "generally reachable". So looking at A-F or F-B, i am able to check wheather A, B or both are on a "island". For detected islands i then used iteratively the modified nearest plugin to search for a best alternative. Finally route A-B is calculated.

[emiltin]

would filtering according to zoom depth / route length be done using road class, or island size?

[DennisOSRM]

Island size, but one could think about both. The intuition is that island size is much more important and that there is little use to select the freeway from a 10 edge component. Where shall it lead anyway ;-)

[emiltin]

that makes sense

[DennisOSRM]

Working on this issue right now. Edges from small components shall only be selected if the user is zoomed in, i.e. >=z14. This will give a much more consistent look and feel. If things go well, it may be online by Saturday.

[emiltin]

sounds good!

[DennisOSRM]

This is now implemented.