Answers.Body: <p>Roads maps are well defined and you can access them online. For example you can visit OpenStreetMap to download road network of a given region. </p>
  
  <p>Such a road network definition contains nodes (junctions) with lat/lon coordinates and edges between nodes (roads). An edge is defined by a connection of two nodes. Edges can represent one-way roads: you need to define double ways as two edges going in both ways. Haversine formula gives you the straight distance between two nodes: the length of the edge. </p>
  
  <p>This definition of a road network gives you a graph (in the mathematical point of view) and is largely covered by the literature. You can search the graph and compute many of its parameters.</p>
  
  <p>From a road network definition you can run shortest path algorithm to find the closest way between two nodes. From a given coordinate you can either pick the closest node or get the closest edge (and compute distance to the edge and the coordinates of the perpendicular projection point). </p>
  
  <p>Algorithms like A* and Dijkstra are not so time consuming and you can find shortest path efficiently.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-13T08:39:18.563Z
Answers.LastActivityDate: 2019-05-15T18:29:03.030Z
Answers.LastEditDate: 2019-05-15T18:29:03.030Z
Answers.UserDisplayName: Madthrax
Answers.Body: <p>Obviously the way Google store their information is not published, but from the <a href="https://developers.google.com/maps/documentation/directions/intro" rel="nofollow noreferrer">Directions API</a> I would make the following educated guesses:</p>
  
  <ol>
  <li>The roads/paths are stored as a graph database</li>
  <li>Each path has additional information: type of road, transport link, etc.</li>
  <li>Geocoordinates or placenames are mapped onto graph nodes</li>
  </ol>
  
  <p>Finding a route then is a problem of finding the best path through the graph. This will be easier if you provide waypoints (which effectively split a long route into several shorter ones). As you have the physical coordinates, you can use something like the <a href="https://en.wikipedia.org/wiki/A*_search_algorithm" rel="nofollow noreferrer">A* algorithm</a> to traverse the graph.</p>
  
  <p>From your question I assume that you'd want to work with map images, rather than a pre-processed graph. I would think that this is not feasible, and that you have to do this conversion into a graph first. You can probably semi-automate this by using image processing to identify roads, but ultimately this is probably something that has to be done at least partially with human intervention. You don't want to drive for ages only to find out there was a one-way street which you did not spot from the image.</p>
  
  <p>Also, usually satnavs are aware of speed limits along the path. This again has to be added either manually or automated (by recognising traffic signs along the route, eg from a street view photography car). So image data alone is not sufficient.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-12T10:39:52.560Z
Answers.Text: Can you elaborate on how roads/paths are stored in the graph database? If I give a latitude and longitude points how will it be searched in the graph database of roads and paths?
Answers.UserDisplayName: AshTyson
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-12T10:46:25.607Z
Answers.Text: As I said, educated guess only: you simply store long/lat with each node in the graph and then pick the closest match. You do that for both origin and destination, then you have two nodes in the graph -- now find the best path using a graph search algorithm.
Answers.UserDisplayName: Oliver Mason
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-12T10:12:55.377Z
Answers.LastActivityDate: 2019-04-12T10:12:55.377Z
Answers.UserDisplayName: Oliver Mason
Body: <p>I have searched on how Google or any map provider calculates distance between two coordinates. The closest I could find is <a href="http://www.movable-type.co.uk/scripts/latlong.html" rel="nofollow noreferrer">Haversine formula</a>.</p>
  
  <p>If I draw a straight line between two points, then Haversine formula can be helpful. But since no one will travel straight and typically move through the streets, I want to know if there are any methods to calculate turn by turn points and see how to find multiple ways to travel to the destination from the source.</p>
  
  <p>Right now my idea is</p>
  
  <ol>
  <li>Have the two coordinates within a map window.</li>
  <li>Make an algorithm detect the white lines (path) in the window.</li>
  <li>Make it understand how they are connected.</li>
  <li>Feed it to an algorithm to solve the <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem" rel="nofollow noreferrer">Travelling Salesman Problem</a> to find the best path between them.</li>
  </ol>
  
  <p>But these things see very memory and process intensive. Even with the knowledge that Google has the powerhouse to process, to serve so many directions and distance matrix in fractions of seconds in amazing. I want to know if there are different approaches to this?</p>
  
Tags: <reinforcement-learning><object-recognition>
Title: How do map providers like Google calculate the distance between two coordinates and find turn by turn directions?
UserDisplayName: AshTyson
ThreadText: # How do map providers like Google calculate the distance between two coordinates and find turn by turn directions?
  
  (Asked by: username_0 on 2019-04-12)
  
  I have searched on how Google or any map provider calculates distance between two coordinates. The closest I could find is [Haversine formula](http://www.movable-type.co.uk/scripts/latlong.html).
  
  If I draw a straight line between two points, then Haversine formula can be helpful. But since no one will travel straight and typically move through the streets, I want to know if there are any methods to calculate turn by turn points and see how to find multiple ways to travel to the destination from the source.
  
  Right now my idea is
  
  1. Have the two coordinates within a map window.
  2. Make an algorithm detect the white lines (path) in the window.
  3. Make it understand how they are connected.
  4. Feed it to an algorithm to solve the [Travelling Salesman Problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem) to find the best path between them.
  
  But these things see very memory and process intensive. Even with the knowledge that Google has the powerhouse to process, to serve so many directions and distance matrix in fractions of seconds in amazing. I want to know if there are different approaches to this?
  
  **Tags:** reinforcement-learning, object-recognition
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2019-05-13. Score: 1
  
  Roads maps are well defined and you can access them online. For example you can visit OpenStreetMap to download road network of a given region.
  
  Such a road network definition contains nodes (junctions) with lat/lon coordinates and edges between nodes (roads). An edge is defined by a connection of two nodes. Edges can represent one-way roads: you need to define double ways as two edges going in both ways. Haversine formula gives you the straight distance between two nodes: the length of the edge.
  
  This definition of a road network gives you a graph (in the mathematical point of view) and is largely covered by the literature. You can search the graph and compute many of its parameters.
  
  From a road network definition you can run shortest path algorithm to find the closest way between two nodes. From a given coordinate you can either pick the closest node or get the closest edge (and compute distance to the edge and the coordinates of the perpendicular projection point).
  
  Algorithms like A\* and Dijkstra are not so time consuming and you can find shortest path efficiently.
  
  
  ---
  
  ### Answer by username_2 on 2019-04-12. Score: 0
  
  Obviously the way Google store their information is not published, but from the [Directions API](https://developers.google.com/maps/documentation/directions/intro) I would make the following educated guesses:
  
  1. The roads/paths are stored as a graph database
  2. Each path has additional information: type of road, transport link, etc.
  3. Geocoordinates or placenames are mapped onto graph nodes
  
  Finding a route then is a problem of finding the best path through the graph. This will be easier if you provide waypoints (which effectively split a long route into several shorter ones). As you have the physical coordinates, you can use something like the [A\* algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm) to traverse the graph.
  
  From your question I assume that you'd want to work with map images, rather than a pre-processed graph. I would think that this is not feasible, and that you have to do this conversion into a graph first. You can probably semi-automate this by using image processing to identify roads, but ultimately this is probably something that has to be done at least partially with human intervention. You don't want to drive for ages only to find out there was a one-way street which you did not spot from the image.
  
  Also, usually satnavs are aware of speed limits along the path. This again has to be added either manually or automated (by recognising traffic signs along the route, eg from a street view photography car). So image data alone is not sufficient.
  
  > **Comments:**
  > **username_0**: Can you elaborate on how roads/paths are stored in the graph database? If I give a latitude and longitude points how will it be searched in the graph database of roads and paths?  
  > **username_2**: As I said, educated guess only: you simply store long/lat with each node in the graph and then pick the closest match. You do that for both origin and destination, then you have two nodes in the graph -- now find the best path using a graph search algorithm.  
  
  ---
  
  