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

Daniel Patterson daniel at mapbox.com
Tue Mar 27 15:10:20 UTC 2018


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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20180327/4c42bfb9/attachment.html>


More information about the OSRM-talk mailing list