[OSRM-talk] OSRM 5.14.3 set kilometers long ways as small elements

[François Lacombe]

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 <daniel at mapbox.com>:

> 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 <
> fl.infosreseaux at gmail.com> wrote:
>
>> Hi Daniel,
>>
>> 2018-03-26 19:48 GMT+02:00 Daniel Patterson <daniel at mapbox.com>:
>>
>>> 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
>> OSRM-talk at openstreetmap.org
>> https://lists.openstreetmap.org/listinfo/osrm-talk
>>
>>
>
> _______________________________________________
> OSRM-talk mailing list
> OSRM-talk at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20180328/fbe532eb/attachment.html>