[OSRM-talk] calculation of jump distances

[Daniel Patterson]

Hi Bryan,

  OSRM uses an R-Tree (https://en.wikipedia.org/wiki/R-tree) to do a
nearest neighbour search (
https://en.wikipedia.org/wiki/Nearest_neighbor_search).  Every segment
(line between two OSM nodes) is indexed in the R-Tree, and we snap to the
closest straight line, measured with the Haversine distance method.

  One thing that might be coming into play is OSRM's "small component"
snapping behaviour - how OSRM behaves when your start and end point are not
actually connected (e.g. one point on an island, one on the mainland).

  There's an older blog post here:


https://blog.mapbox.com/robust-navigation-with-smart-nearest-neighbor-search-dbc1f6218be8

  that describes this behaviour.  It's possible this is coming into play
for some locations, but you'd need to look very closely at your data and
the failing requests to really understand what's going on.

daniel

On Wed, Jan 17, 2018 at 7:10 AM, Sayer, Bryan <BSayer at s-3.com> wrote:

> Hi Daniel,
>
>
>
> Thanks for the advice. We use the Stata implementation on a secure network
> so I can’t try any of the usual options that are available over the
> internet. I will double check that I have the order (longitude, latitude)
> but I have over 450 million routes all over the USA (every populated tract
> to every hospital, with certain restrictions in Hawaii and Alaska), so I
> imagine if I had them reversed I would have really strange results.
>
>
>
> I can check the area size of the tracts. I suppose some tracts might not
> have any roads, but generally tracts are defined by roads or natural
> elements like rivers. I only use tracts with non-zero population, so it
> seems like every tract I use should have a road in it. It seems to me that
> it should never be the case that the jump distance from the tract centroid
> to the starting point should exceed the largest dimension of the tract, or
> really one-half of that distance.
>
>
>
> It is not a large number of routes with these large jump distances, just a
> few.
>
>
>
> When you say “the first thing that happens is that the nearest point on
> the road network is found” how is the nearest road network found? That
> is, what is the algorithm? Does it spiral out from the point until a road
> is hit?
>
>
>
>
>
> Bryan Sayer
>
> Statistician
>
> Social & Scientific Systems, Inc.
>
> Monday-Friday 9:30 to 5:30
>
> (301) 628-1576
>
> https://www.s-3.com/
>
>
>
>
>
> *From:* Daniel Patterson [mailto:daniel at mapbox.com]
> *Sent:* Tuesday, January 16, 2018 5:24 PM
> *To:* Mailing list to discuss Project OSRM <osrm-talk at openstreetmap.org>
> *Subject:* Re: [OSRM-talk] calculation of jump distances
>
>
>
> Hi Bryan,
>
>
>
>   OSRM stores the road network in memory.  When you supply a coordinate to
> start/finish a route, the first thing that happens is that the nearest
> point on the road network is found.  Routing then happens from those
> "snapped" points.
>
>
>
>   If you've got big rural areas, and you're using large regional
> centroids, then I suspect the snapping is starting or finishing your routes
> on roads you don't expect.
>
>
>
>   Several hundred KM is pretty weird though, unless your road network is
> *really* sparse.  Do you have your coordinate the correct way around in
> your requests?  The order should be <longitude>,<latitude> for every pair -
> getting this wrong is often the source of really weird results.
>
>
>
>   Try making a single request with `overview=full&geometries=geojson`,
> then plot the full route geometry on http://geojson.io/ or something to
> see if it even looks reasonable.
>
>
>
> daniel
>
>
>
> On Tue, Jan 16, 2018 at 1:43 PM, Sayer, Bryan <BSayer at s-3.com> wrote:
>
> Hi,
>
>
>
> We are calculating distances between an U.S. census tract centroid and
> hospitals. A tract averages about 4,000 people, but can vary in area.
> Obviously, the centroid is likely to not be on a street, and thus a jump
> distance has to be calculated to get to a street.
>
>
>
> Our question is what is the general algorithm for getting to the starting
> point? We definitely end up with some very large numbers (several hundred
> kilometers) on some jump distances, which seems incorrect.
>
>
>
> Bryan Sayer
>
>
> ****WARNING**** This information may be confidential. It is intended only
> for the addressee(s) identified above. If you are not the addressee(s), or
> an employee or agent of the addressee(s), please note that any
> dissemination, distribution, or copying of this communication is strictly
> prohibited. If you have received this information in error, please destroy
> the information and notify the sender of the error. Thank you.
>
>
> _______________________________________________
> OSRM-talk mailing list
> OSRM-talk at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk
>
>
>
> ****WARNING**** This information may be confidential. It is intended only
> for the addressee(s) identified above. If you are not the addressee(s), or
> an employee or agent of the addressee(s), please note that any
> dissemination, distribution, or copying of this communication is strictly
> prohibited. If you have received this information in error, please destroy
> the information and notify the sender of the error. Thank you.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20180118/f77a5819/attachment.html>