How are Google Maps generated?
Hey friends, Happy Wednesday!
Let’s look at how Google Maps are generated and maintained this week. I aim to write my newsletter issues in a way one can follow them while traveling on a bus, having a coffee, waiting for your food, etc. Let's jump in!
How are Google Maps generated?
Collecting Satellite imagery
Figure 1: Satellite image of a geographic location
Geographical data and high-resolution images from satellite imagery, aerial photography, and public data sets from governmental agencies and commercial providers are collected. These images are taken at different angles and times to create a composite view of the Earth's surface.
Images from Street View Cars
Figure 2: A live google street view car taking images from the streets using the camera and sensors mounted on the top
Street View cars are equipped with cameras, LIDAR sensors, and GPS receivers to capture street-level imagery. They have a 360-degree camera on the top and literally go around the streets taking images. This is what you see on your phone after you click the street view of a place.
Stitching the Images from These Sources
To create a seamless map, multiple images and data from all these sources are stitched together. Advanced algorithms are used to blend the images and data, considering their geographic coordinates and orientation.
How are features like rivers and parks identified?
Google uses computer vision and machine learning algorithms to identify and extract various map features from the imagery and data. This includes roads, buildings, rivers, parks, and other geographic elements.
How does Google Maps generate a route?
Figure 3: Converting the map into nodes and edges in an area to solve the shortest path problem and find a route
Google collects data from GPS devices and smartphones to create real-time traffic information and routing algorithms. This helps users find the best routes to their destinations, taking into account current traffic conditions. The more the number of devices detected on the same road using the GPS information, the map marks the portion of the road in red to denote traffic. This data is used by the machine learning model to predict the time it’d take to reach the destination taking traffic into account.
This also helps google to suggest an alternate route as the algorithm penalizes routes that take more time for you to reach the destination. The algorithms used by Google Maps to generate a route from the start to the destination are a variation of Dijkstra and A* search. These are graph search algorithms that find the shortest path between two points. I programmed these algorithms for a robotics course in my grad school and here is a video that discusses one of the algorithms in detail, if you’re interested.
Rendering all the information on your phone
When a user accesses Google Maps, the system determines the portion of the map to display based on the user’s view and zoom level. The corresponding map tiles are retrieved from the database and rendered on the user’s screen.
Feedback and manual correction
Google continually updates its maps using new data and imagery from various sources. They also incorporate user feedback and corrections to improve the accuracy and completeness of the maps.
Question of the week
How do you think buildings and terrains are represented in 3D on your Google Maps? Reply to this email with your thoughts, and let’s have a discussion.
Thank you for reading!
Have a nice rest of the week, and take care!
Until next Wednesday,
Chendur
