wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Algorithms/Data structures used in Google maps?
        
(Message started by: bmudiam on Jan 25^th, 2010, 9:49pm)

Title: Algorithms/Data structures used in Google maps?
Post by bmudiam on Jan 25^th, 2010, 9:49pm

Hi Everyone,

I am amazed at how google maps work and how they return routes between two places so fast. Any idea which algorithm/data structure are used?

Regards
Bala

Title: Re: Algorithms/Data structures used in Google maps
Post by towr on Jan 26^th, 2010, 3:10am

You can represent the road network as a weighted graph, and finding a route is then just an application of a shortest path algorithm. See http://en.wikipedia.org/wiki/Shortest_path_problem

Title: Re: Algorithms/Data structures used in Google maps
Post by Grimbal on Jan 26^th, 2010, 9:59am

Considering the large number of small roads worldwide, and the fact that the graph is embedded in a 2D plane, I am sure there are very specific algorithms for the task. A generic shortest path algorithm would perform poorly. It would make sense to represent the roads in a multi-level graph where only the highways are considered for long distances, then larger roads near the ends and the smallest roads only to actually reach the start and end point, not further than it takes to reach a larger road.

Title: Re: Algorithms/Data structures used in Google maps
Post by bmudiam on Jan 26^th, 2010, 12:01pm

I think algorithms in computational geometry field are useful here.

When you click on a particular coordinate in the map and using that information, can get the latitude and longitude of that location. Based on the latitude and longitude and the level of zoom, the place can be identified.

Once you have identified the two places, the only problem for you is to identify the nearest route. Now this problem is finding the shortest path between two points, having polygon blocks between them(which correspond to the places which contains no roads) and the only possible connections are roads. This is a known problem and efficient algorithms exist to solve this.

Is this how it works?

Title: Re: Algorithms/Data structures used in Google maps
Post by rmsgrey on Jan 27^th, 2010, 8:03am

on 01/26/10 at 12:01:35, bmudiam wrote:

Once you have identified the two places, the only problem for you is to identify the nearest route. Now this problem is finding the shortest path between two points, having polygon blocks between them(which correspond to the places which contains no roads) and the only possible connections are roads. This is a known problem and efficient algorithms exist to solve this.

Is this how it works?

Not all roads are equal. Given a choice between a 3-lane carriageway that bypasses a city, the 2-lane carriageway that circles the town centre, and the victorian-era streets (now one-way where they're not pedestrianised) that thread through the town centre, the longest route (the bypass) is often the one that takes the shortest time, with the one-way system generally only useful if you want to get to/from somewhere in the centre...

The obvious way to handle the difference between different roads is by taking account of the average speed of travel on each (stretch of) road - so, rather than distances, you deal in expected times.

Depending on how much computational power you want to throw at the task, you can create a simplified graph for long-distance travel that follows major roads, and then apply a path-finding algorithm to the problem of getting between the nearby nodes of the simplified graph and your actual destination, or you can take the brute-force approach and do a single pass that considers every dirt-track and rat-run on the way.

An additional consideration is that, unless you're transferring the directions directly into someone's satnav (which generally have their own route-finding built in), the directions have to be interpreted and followed by a human being - even if the route with 50 extra turns would take less time if you could follow it, it's much easier to follow a main road past 3-4 cities than it is to leave the main road at each city, navigate the town centre, and then rejoin the road you left half an hour ago...