How do map providers like Google calculate the distance between two coordinates and find turn by turn directions?

Question

I have searched on how Google or any map provider calculates distance between two coordinates. The closest I could find is Haversine formula.

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 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?

Answer 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 2

Obviously the way Google store their information is not published, but from the Directions API 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 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.