<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Elephant;
panose-1:2 2 9 4 9 5 5 2 3 3;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p
{mso-style-priority:99;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#44546A;
font-weight:normal;
font-style:normal;
text-decoration:none none;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif;color:#44546A">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif;color:#44546A"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Elephant",serif;color:#44546A">Bryan Sayer<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#44546A">(301) 628-1576<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif;color:#44546A"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> Daniel Patterson [mailto:daniel@mapbox.com]
<br>
<b>Sent:</b> Thursday, January 18, 2018 12:25 PM<br>
<b>To:</b> Sayer, Bryan <BSayer@s-3.com><br>
<b>Cc:</b> Mailing list to discuss Project OSRM <osrm-talk@openstreetmap.org><br>
<b>Subject:</b> Re: [OSRM-talk] calculation of jump distances<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">Hi Bryan,<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"> OSRM uses an R-Tree (<a href="https://en.wikipedia.org/wiki/R-tree">https://en.wikipedia.org/wiki/R-tree</a>) to do a nearest neighbour search (<a href="https://en.wikipedia.org/wiki/Nearest_neighbor_search">https://en.wikipedia.org/wiki/Nearest_neighbor_search</a>).
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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"> 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).<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"> There's an older blog post here:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"> <a href="https://blog.mapbox.com/robust-navigation-with-smart-nearest-neighbor-search-dbc1f6218be8">https://blog.mapbox.com/robust-navigation-with-smart-nearest-neighbor-search-dbc1f6218be8</a><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"> 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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">daniel<o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Wed, Jan 17, 2018 at 7:10 AM, Sayer, Bryan <<a href="mailto:BSayer@s-3.com" target="_blank">BSayer@s-3.com</a>> wrote:<o:p></o:p></p>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-family:"Calibri",sans-serif;color:#44546A">Hi Daniel,</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-family:"Calibri",sans-serif;color:#44546A"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-family:"Calibri",sans-serif;color:#44546A">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.</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-family:"Calibri",sans-serif;color:#44546A"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-family:"Calibri",sans-serif;color:#44546A">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.</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-family:"Calibri",sans-serif;color:#44546A"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-family:"Calibri",sans-serif;color:#44546A">It is not a large number of routes with these large jump distances, just a few.</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-family:"Calibri",sans-serif;color:#44546A"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-family:"Calibri",sans-serif;color:#44546A">When you say “</span>the first thing that happens is that the nearest point on the road network is found<span style="font-family:"Calibri",sans-serif;color:#44546A">”
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?</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-family:"Calibri",sans-serif;color:#44546A"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-family:"Calibri",sans-serif;color:#44546A"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Elephant",serif;color:#44546A">Bryan Sayer</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#44546A">Statistician</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#44546A">Social & Scientific Systems, Inc.</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#44546A">Monday-Friday 9:30 to 5:30</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#44546A"><a href="tel:(301)%20628-1576" target="_blank">(301) 628-1576</a></span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#44546A"><a href="https://www.s-3.com/" target="_blank">https://www.s-3.com/</a></span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-family:"Calibri",sans-serif;color:#44546A"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-family:"Calibri",sans-serif;color:#44546A"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> Daniel Patterson [mailto:<a href="mailto:daniel@mapbox.com" target="_blank">daniel@mapbox.com</a>]
<br>
<b>Sent:</b> Tuesday, January 16, 2018 5:24 PM<br>
<b>To:</b> Mailing list to discuss Project OSRM <<a href="mailto:osrm-talk@openstreetmap.org" target="_blank">osrm-talk@openstreetmap.org</a>><br>
<b>Subject:</b> Re: [OSRM-talk] calculation of jump distances</span><o:p></o:p></p>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">Hi Bryan,<o:p></o:p></p>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> 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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> 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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> 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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> Try making a single request with `overview=full&geometries=geojson`, then plot the full route geometry on
<a href="http://geojson.io/" target="_blank">http://geojson.io/</a> or something to see if it even looks reasonable.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">daniel<o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">On Tue, Jan 16, 2018 at 1:43 PM, Sayer, Bryan <<a href="mailto:BSayer@s-3.com" target="_blank">BSayer@s-3.com</a>> wrote:<o:p></o:p></p>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0in;margin-bottom:5.0pt">
<div>
<div id="m_1225376044667569585m_2888795376369566274divtagdefaultwrapper">
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-family:"Calibri",sans-serif;color:black">Hi,</span><o:p></o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-family:"Calibri",sans-serif;color:black"> </span><o:p></o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-family:"Calibri",sans-serif;color:black">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. </span><o:p></o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-family:"Calibri",sans-serif;color:black"> </span><o:p></o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-family:"Calibri",sans-serif;color:black">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.</span><o:p></o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-family:"Calibri",sans-serif;color:black"> </span><o:p></o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-family:"Calibri",sans-serif;color:black">Bryan Sayer</span><o:p></o:p></p>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><br>
****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.
<o:p></o:p></p>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:12.0pt"><br>
_______________________________________________<br>
OSRM-talk mailing list<br>
<a href="mailto:OSRM-talk@openstreetmap.org" target="_blank">OSRM-talk@openstreetmap.org</a><br>
<a href="https://lists.openstreetmap.org/listinfo/osrm-talk" target="_blank">https://lists.openstreetmap.org/listinfo/osrm-talk</a><o:p></o:p></p>
</blockquote>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
</div>
</div>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><br>
****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.
<o:p></o:p></p>
</div>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
<br>
****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.
</body>
</html>