Author |
Topic: Algorithms/Data structures used in Google maps? (Read 6499 times) |
|
bmudiam
Junior Member
Gender: 
Posts: 55
|
 |
Algorithms/Data structures used in Google maps?
« on: Jan 25th, 2010, 9:49pm » |
 Quote  Modify
|
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
|
|
 IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Algorithms/Data structures used in Google maps
« Reply #2 on: Jan 26th, 2010, 9:59am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
bmudiam
Junior Member
Gender:
Posts: 55
|
|
Re: Algorithms/Data structures used in Google maps
« Reply #3 on: Jan 26th, 2010, 12:01pm » |
Quote Modify
|
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?
|
|
IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Algorithms/Data structures used in Google maps
« Reply #4 on: Jan 27th, 2010, 8:03am » |
Quote Modify
|
on Jan 26th, 2010, 12:01pm, 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...
|
| « Last Edit: Jan 27th, 2010, 8:04am by rmsgrey » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print