Hi Daniel, Basically, as I understand things, I should aim to reduce my "small elements" as to make them accessible from Tarjan SCC snapping.
It would probably make orsm-routed less fast to answer is you change your snapping algorithm, while I'd love you move toward this :) All the best François 2018-03-27 17:10 GMT+02:00 Daniel Patterson <[email protected]>: > Hi François, > > > I don't understand why flagging part of the graph as "small element" > prevent a route to be found. > > I guess you could describe this as a bug. What OSRM is trying to do is > always return a route. The current approach makes sure to snap the input > coordinates to edges on the same "strongly connected component", which > (usually) guarantees a route will be found. > > There's an older blog post by Denis here: https://blog.mapbox.com/ > robust-navigation-with-smart-nearest-neighbor-search-dbc1f6218be8 > that explains the behaviour/problem that this snapping is intended to > solve. > > This behaviour makes sense for fully disconnected components - islands, > parks, etc. > > However, in your case, the components are weakly connected - there is a > one-way path in, and an A->B route could be found, but a B->A route would > not. > > This situation isn't really handled by the current approach. The Tarjan > SCC algorithm flags *strongly connected* graph regions (full connectivity > in both directions). We would need to do something quite different I think > in order to do correct snapping for weakly connected components as you have > in your graph. > > Generally in OSM, there aren't too many of these, and where they are, > they're usually a mapping error (one-way roads with no exits, etc). Given > that, I'm not sure it's worth spending time improving this behaviour for > use with OSM data. > > daniel > > > On Tue, Mar 27, 2018 at 1:58 AM, François Lacombe < > [email protected]> wrote: > >> Hi Daniel, >> >> 2018-03-26 19:48 GMT+02:00 Daniel Patterson <[email protected]>: >> >>> Hi François, >>> >>> Yes, oneways onto your custom road network sound like exactly the kind >>> of thing that the small component algorithm ( >>> https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected >>> _components_algorithm) would flag. If your custom network is <1000 >>> nodes, it would've been flagged previously. >>> >>> If you are only routing from the normal network *onto* your custom >>> network, then changing the component size like you've done is the correct >>> fix here. Just be aware, if you start on your custom network, and try to >>> return to the main network, you will get "NoRoute" errors, but it sounds >>> like that won't be a problem for you. >>> >> >> This is indeed what I look for, no problem to get "No route" errors, but >> only when network topology doesn't allow me to find one. >> I don't understand why flagging part of the graph as "small element" >> prevent a route to be found. >> >> I would agree to a potential downgrade of small elements versus normal >> ones, but a route have to be returned when it exists, haven't you? >> >> >>> I'm not sure what's up with the turn icons in the debug viewer - make >>> sure you've zoomed in far enough, turn icons only show up from Z12 and >>> higher. >>> >> >> Yes, I look between zoom 12 and 14 >> Still no turn icons >> >> I'm wondering if it's only a display issue or a more serious problem in >> my data processing. >> Anyway, osrm gives me routes with turns and intersections so this sounds >> to be only a display issue. >> >> >> All the best >> >> François >> >> _______________________________________________ >> OSRM-talk mailing list >> [email protected] >> https://lists.openstreetmap.org/listinfo/osrm-talk >> >> > > _______________________________________________ > OSRM-talk mailing list > [email protected] > https://lists.openstreetmap.org/listinfo/osrm-talk > >
_______________________________________________ OSRM-talk mailing list [email protected] https://lists.openstreetmap.org/listinfo/osrm-talk
