Map Clustering with QuadTrees using GoogleMaps

In this article I’ll explain how to use map clustering with quad trees using GoogleMaps for iOS.

This was done back in December 2015 as back then Google did not have map clustering available for iOS. Since then Google have implemented map clustering using the algorithm described. This was a great academic exercise, a fun project and I believe it’s worth sharing.

What is a QuadTree?

A QuadTree is a data structure used to divide an area into manageable parts. As more objects are added into the tree it will split into four smaller quadrants, or nodes. Each node has a certain capacity and when that capacity is reached it splits into more nodes.

On the diagram below, the root node is split into four quadrants which are typically known as North-West, North-East, South-West and South-East.

The idea is to search in smaller areas to speed up processing time.

What is a Bounding Box?

The idea behind this is basically it’s a searchable area. You want to see just the markers that are in this area so all of the markers positioned outside of this are not checked or drawn. You primarily use the North-East and South-West coordinates to get the minimum and maximum latitudes and longitudes. Based on these two coordinates you can extrapolate the whole Bounding Box. An explanation is shown below.

 

The image below represents an initial state where Google Maps will display the entire world on the screen of your device, otherwise known as the Bounding Box. As you zoom in or pan the map you change the Bounding Box. When you stop moving it the QuadTree will be reconstructed for the markers within the Bounding Box, including the markers that are partially visible.

 

Querying

The idea here is you look at a region within the bounding box. This will determine how many markers are clustered together. So, for example, if 20 markers are found within this smaller region they will be grouped together and displayed as one marker.

The formula used to calculate the smaller region is:

Google Maps states that “increasing the zoom level by one doubles the width of the world on the screen”. They say that at zoom level n the width of the world is approximately (256 * 2^n). I want to keep the coordinateAreaSize relative to the zoom level (hence the 2^15) and it should decrease as we increase the zoom because we are using the Earth’s coordinate system of latitude and longitude. We are only observing a small bounding box which is the screen of the device. If we didn’t modify the coordinateAreaSize in this way when we zoom in we end up with a bounding box that is smaller than the coordinateAreaSize which means that all of the markers for that bounding box will not be clustered correctly.

Code

To create a quad tree you first create a bounding box of the visible area on screen which gives you an initial set of values for minimum and maximum latitude and longitude for the quad tree.

You then insert all of the markers into the quad tree. First the true minimum and maximum latitude and longitude values are found and updated with values from the markers sitting at the most North-East and South-West coordinates. This is done on the first draw only, but no new markers are ever going to be added to the marker array in this example.

Next a check is done to see if the marker is contained within the visible area of the bounding box. If it’s not it is rejected by the quad tree. If it is the node is checked to see if it still has capacity to accept the marker. If it doesn’t it simply subdivides itself and then adds the marker to whichever child node will accept it.

Coordinates for North-East and South-West are taken and along with the quad tree, bounding box and zoom level are passed to the main algorithm of the program to figure out which markers to cluster together. This is done by querying the main bounding box with a smaller region (also a bounding box) inside of it. The coordinateAreaSize dictates the size of the smaller region to search. This returns an array of markers that are grouped together to form a new single, clustered marker. The location of this marker is based on an average of all the other markers within it.

The clustered markers are then translated into GMSMarkers and are given a different image size based on how many markers they contain.

Finally the map is updated with the GMSMarkers. A hash value on the marker is used to determine if the GMSMarker is still on screen after the bounding box changes. If it is still visible it doesn’t redraw itself again.

That’s it 🙂 Here’s what it will look like:

You can find the project on my GitHub repository.

 Thanks for reading 🙂
~ S

0

Leave a Reply