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:

var coordinateAreaSize: Double = 32768 / (256 * pow(2, zoomLevel)) //32768 = 2^15

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.

func boundingBoxForCoordinates(_ northEastCoord: CLLocationCoordinate2D, southWestCoord: CLLocationCoordinate2D) -> BoundingBox
    {
        let minLat: CLLocationDegrees = southWestCoord.latitude
        let maxLat: CLLocationDegrees = northEastCoord.latitude
        
        let minLong: CLLocationDegrees = southWestCoord.longitude
        let maxLong: CLLocationDegrees = northEastCoord.longitude
        
        return boundingBoxMake(CGFloat(minLong), y0: CGFloat(minLat), xf: CGFloat(maxLong), yf: CGFloat(maxLat))
    }

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.

func clusteredAnnotationsWithinMapRect(_ quadTree: QuadTree, zoomLevel: Double, boundaryNE: CLLocationCoordinate2D, boundarySW: CLLocationCoordinate2D, boundingBox: BoundingBox) -> [MapMarker]
    {
        let minLat:Int = Int(floor(boundarySW.latitude))
        let maxLat:Int = Int(ceil(boundaryNE.latitude))
        
        let minLong:Int = Int(floor(boundarySW.longitude))
        let maxLong:Int = Int(ceil(boundaryNE.longitude))
        
        var clusteredMapMarkers = [MapMarker]()
        var coordinateAreaSize: Double = 32768 / (256 * pow(2, zoomLevel)) //32768 = 2^15
        
        if zoomLevel > 10 { //The area becomes too small at this point so increase it
            coordinateAreaSize = 1
        }
        
        var i = Double(minLong)
        while i < Double(maxLong) + coordinateAreaSize {
            
            var j = Double(minLat)
            while j < Double(maxLat) + coordinateAreaSize {
                
                let northEastCoord: CLLocationCoordinate2D = CLLocationCoordinate2DMake(j + coordinateAreaSize, i + coordinateAreaSize)
                let southWestCoord: CLLocationCoordinate2D = CLLocationCoordinate2DMake(j, i)
                
                let areaBox: BoundingBox = quadTree.boundingBoxForCoordinates(northEastCoord, southWestCoord: southWestCoord) //An area within the boundary to cluster
                
                var totalLatitude: Double = 0
                var totalLongitude: Double = 0
                var mapMarkers = [MapMarker]()
                
                let objectArray = quadTree.queryRegion(boundingBox, region: areaBox)
                
                for object in objectArray {
                    
                    totalLatitude += object.markerCoordinate.latitude
                    totalLongitude += object.markerCoordinate.longitude
                    mapMarkers.append(object)
                }
                
                let count = mapMarkers.count
                
                if count == 1 {
                    clusteredMapMarkers += mapMarkers
                }
                
                if count > 1 {
                    let coordinate = CLLocationCoordinate2D(
                        latitude: CLLocationDegrees(totalLatitude)/CLLocationDegrees(count),
                        longitude: CLLocationDegrees(totalLongitude)/CLLocationDegrees(count)
                    )
                    
                    let cluster = Annotation()
                    cluster.markerCoordinate = coordinate
                    cluster.markerClusterTitle = "Marker Count: \(count)"
                    cluster.markerClusterCount = count
                    
                    clusteredMapMarkers.append(cluster)
                }
                
                j = j + coordinateAreaSize
            }
            
            i = i + coordinateAreaSize
        }
        
        return clusteredMapMarkers
    }

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.

private func updateMapWithAnnotations(_ newMarkers: inout [GMSMarker], map: GMSMapView, quadTree: QuadTree, box: BoundingBox)
    {
        var toKeep: [GMSMarker] = []
        var toAdd: [GMSMarker] = []
        var toRemove: [GMSMarker] = []
        
        if mapMarkers.count == 0 { //First time
            mapMarkers += newMarkers //Add all newMarkers to mapMarkers
            
            for aMarker in mapMarkers {
                aMarker.map = map
            }
        }
        else {
            for mapMarker in mapMarkers //mapMarkers are the old selection
            {
                for newMarker in newMarkers //newMarkers are the new selection
                {
                    let aMarker = mapMarker.userData as! MapMarker
                    let bMarker = newMarker.userData as! MapMarker
                    
                    if aMarker.isEqualToMarker(bMarker) { //If the markers are the same the old marker is still visible so keep it
                        toKeep.append(mapMarker)
                        
                        if let index = newMarkers.index( where: { ($0.userData as! MapMarker).markerHashValue == bMarker.markerHashValue } ){
                            newMarkers.remove(at: index) //Remove keep marker - logically what's left should be new markers to be added
                        }
                        
                        if let indexMap = mapMarkers.index( where: { ($0.userData as! MapMarker).markerHashValue == bMarker.markerHashValue } ) {
                            mapMarkers.remove(at: indexMap) //Remove keep marker - logically what's left should be old markers to be removed
                        }
                        
                        break
                    }
                }
            }
            
            toAdd += newMarkers
            toRemove += mapMarkers
            
            mapMarkers.removeAll()
            
            for addMarker in toAdd {
                mapMarkers.append(addMarker)
                addMarker.map = map
            }
            
            for keepMarker in toKeep {
                mapMarkers.append(keepMarker)
            }
            
            for removeMarker in toRemove {
                removeMarker.map = nil
            }
        }
    }

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

You can find the project on my GitHub repository.

 Thanks for reading 🙂
~ S

One thought on “Map Clustering with QuadTrees using GoogleMaps

  1. Manish Prakharan

    Hi Shóna,
    Well nice tutorial, but I am facing a problem as here you have taken random positions CLLocationCoordinate2D so the markers renders the screen well.

    As I am trying to populate the map coordinates from the API the markers does not renders on mapView it’s weird error I am facing or try rendering the mapView markers after few seconds it doesn’t renders.

    Hope You have understood it if you haven’t Please revert me.

    Thanks

    Reply

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.