Thanks! I was wondering if some of these might be islands. I haven’t had time to check out the details of ones with extra large jump distances yet, but I’ll try to do that in the next few days.
Bryan Sayer (301) 628-1576 From: Daniel Patterson [mailto:dan...@mapbox.com] Sent: Thursday, January 18, 2018 12:25 PM To: Sayer, Bryan <bsa...@s-3.com> Cc: Mailing list to discuss Project OSRM <osrm-talk@openstreetmap.org> Subject: Re: [OSRM-talk] calculation of jump distances 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 <bsa...@s-3.com<mailto:bsa...@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<tel:(301)%20628-1576> https://www.s-3.com/ From: Daniel Patterson [mailto:dan...@mapbox.com<mailto:dan...@mapbox.com>] Sent: Tuesday, January 16, 2018 5:24 PM To: Mailing list to discuss Project OSRM <osrm-talk@openstreetmap.org<mailto:osrm-talk@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 <bsa...@s-3.com<mailto:bsa...@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@openstreetmap.org<mailto:OSRM-talk@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. ****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@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
