Finally: how satnav and GPS find routes

This may only scratch an itch of mine but it’s a big itch and I’ve had it a long time. It’s very easy to understand how GPS works – it’s triangulation – even when you know exactly where you are on the globe, how in the hell do you work out the best route to Tesco?

I think about this a lot and I’ve asked people about it who ended up explaining GPS like I hadn’t just said I got that bit. Usually I don’t get anywhere. But noodling around this evening, look what I found: the explanation.

There’s this guy, right, and he was preparing to demonstrate some fancy computer.

For a demonstration for noncomputing people you have to have a problem statement that non-mathematicians can understand,” [Edsger W. ] Dijkstra recalled in an interview not long before his 2002 death. “They even have to understand the answer. So I designed a program that would find the shortest route between two cities in the Netherlands, using a somewhat reduced road-map of the Netherlands, on which I had selected 64 cities.”

“What’s the shortest way to travel from Rotterdam to Groningen?,” Dijkstra said. “It is the algorithm for the shortest path, which I designed in about 20 minutes.”

The Simple, Elegant Algorithm That Makes Google Maps Possible – Michael Byrne, Motherboard (22 March 2015)

Read the full piece for some basic maths on an admittedly simplified version of how it’s all done. But it’s how it’s all done. I am so pleased right now.

Leave a Reply

Your email address will not be published. Required fields are marked *

Blue Captcha Image