Detect unreachable destination, route to closest alternative
Brought to you by:
james22
Menu
▾
▴
#621 Detect unreachable destination, route to closest alternative
Especially with barrier support it happens more often that a destination way is unreachable for route calculation. In large midlets this will cause GpsMid on current mobile devices to calculate virtually forever. GpsMid should instead earlier detect this situation, maybe display a warning and then route to the closest reachable way.
Wondering what a good and quickly implementable logic for this would be.
Well this should be solved; but while it's unsolved, I think it's a bad workaround to disable barriers for this problem. Disabling barries can result in wrong routes which aren't obviously, shouldn't have that. For unreachable destinations, it'll be relatively soon obvious to the user that a route won't be found.
One idea for solving:
1) Take an arbitrary (routable) point P 1 km away (or maybe starting from 500m, if fails, try again with 1km) from destination to check if that can be routed to destination
2) Try to calculate a route from P to destination; keep track of the shortest (as the crow flies) distance to destination
3) If it succeeds in some short time or resource limit, fine, calculate route normally to destination
4) If finding route from P to destination fails, route to place with the shortest distance found in 2)
Another idea to avoid an extra route calculation every time:
1) Investigate the route connections the destination route node has.
2) If the destination has connections to only very few of other route nodes, it's probably an "island" from routability point of view. Go apply what's described above (take an arbitray point ..)
Don't really the route node structures however, so don't know if the second part will work.
Talking about islands, there area also the real islands, for which a 1km distance may not be enough. Some islands are reachable by car e.g. in winter via an ice road, so maybe have "winter routing mode" :-) Then there's routing via ferries or cable ferries, don't know if GpsMid does that.
One approach to solve this just for barriers would be to have barriers be routable but with a very high cost. But that's not such a good solution as there are the real islands and islands from point of view of routing which wouldn't be handled by that.
> Well this should be solved; but while it's unsolved, I think it's a bad
workaround to disable barriers for this problem
Believe me, it's better to disable - I told some unexperienced GPSMid user to route to a certain POI blocked by a barrier - right before the service way leading to the POI and GosMid did not route there but with the big map calculate virtually forever.
Btw this was Android, cancelling the route calcuatation crashes GpsMid.
Anyway - I see this issue as a much frequent issue than some times suggesting a wrong route which might always happen, that some street is currently not useable due to street work or some event.
Even considered to say there should do a new release after 0.8 without barriers again. Got no time for doing a complex algorithm now.
Considered something similiar like your suggestion to try routing from the closest detected mainstreet node if any to see if the destination is reachable. However actually could always happen in theroy that you would have to travel to the complete map to get to the destination from there.
Ideally I think Osm2GpsMid would have to detect "unconnected islands" and for each route node it would be know in which routing island it is. Route Nodes from two different islands would never have a routing solution. Well not so ideal actually, as it would require quite many resources to store the island number for each route mode and each route node. Also would probably be heavy for Osm2GpsMid to calculate the island numbers.
Your other idea has the problem that if the destination route node is connected via one ways we won't easily find the reverse connections to travel back as the reverse connections are not in the route data.
> One approach to solve this just for barriers would be to have barriers be
routable but with a very high cost. But that's not such a good solution as
there are the real islands and islands from point of view of routing which
wouldn't be handled by that.
Yes, this would be just a solution for routing, however it'll cause to always cross the barrier if there's no alternative, i.e. it'll always route to the actually barriered destination way rather than to the closest non-barriered alternative.
What kind of situations have you run into the problem in? Routing to a mall, an amenity, public building, a housenumber, something else? Knowing this might help to decide what would be the best place to route to, when destination is unreachable.
If route mode is car, would be reasonable to route to a nearby parking place if it's planned the car will be parked, or route to a nearest place where the driver can stop, if the plan is just to drop someone near the place.
If route mode is an amenity / public building / whatever, it might have a relation or other map tagging which describes where to enter the location. Could have several entrances, and then would be good to choose the nearest one.
I've run into this once, in the Turku castle (tourist attraction), there was a road which wasn't connected to the road network, probably another ticket open on this.
"Your other idea has the problem that if the destination route node is
connected via one ways we won't easily find the reverse connections to
travel back as the reverse connections are not in the route data."
Hmm - my plan was to just use this to test if the destination is a routing island or not, and then use the normal routing code to find the route, so I don't see a problem, but maybe I'm not quite understanding what you're saying.
I've canceled routing plenty of times on Android for recalc, never had a crash. Based on the map drawing crashes, I'm guessing it was an out of memory issue.
> Hmm - my plan was to just use this to test if the destination is a routing
island or not, and then use the normal routing code to find the route, so I
don't see a problem, but maybe I'm not quite understanding what you're
saying.
But how do you want to detect if it's a routing island?
Each route node just knows to which other route nodes you can travel to, but you don't know how to travel back from a given route node (i.e. the destination route node).
So you mean that the destination route node may not have any connections away from destination, even though there are routable ways away from the destination? Would there then be another origin route node at the same place? I thought route nodes were found by coordinates.
I'm assuming here that there aren't that many places where there's only a way leading there but no way leading out. (like black holes or /dev/nulls) or vice versa. Though I can think of at least one case which might be like this - the driveway to a ferry, if it happens that one place is used for departures and another for arrivals.
> I thought route nodes were found by coordinates.
Route Nodes contain a list of connections pointing to other route node ids you can travel to.
Finding them by coordinates is possible also but takes much longer.
> 'm assuming here that there aren't that many places where there's only a
way leading there but no way leading out. (like black holes or /dev/nulls)
or vice versa. Though I can think of at least one case which might be like
this - the driveway to a ferry, if it happens that one place is used for
departures and another for arrivals.
Yes, there might be some kind ofl barrier for driving in on a oneway but it might be unbarriered to leave the destination again using another oneway.
"Yes, there might be some kind ofl barrier for driving in on a oneway but it might be unbarriered to leave the destination again using another oneway"
Yes, but I'd think that's an exception rather than a rule. Do you know if my suggestion to test the destination route node for routes out would work? (The destination node route node is calculated anyway)
If we can detect the case for most cases, a simple first step would be to show a warning "No route can be found to destination, showing the selected destination so you select a routable destination nearby" and show the dest instead of routing to it.
Yes, I expect this to work if you find a reasonable criteria to decide when the destination is actually detected.
However, I would prefer to have GpsMid decide to route to the closest alternative automatically. This will most frequently be the barrier itself.
Yes, I expect this to work if you find a reasonable criteria to decide when the destination is actually detected.
However, I would prefer to have GpsMid decide to route to the closest alternative automatically. This will most frequently be the barrier itself.