Pablo Garcia

Apps for iPhone, iPad, Apple TV and Apple Watch

Quadtree and Map Clustering - III

Mar 31, 2019

In the previous post we viewed how to cluster annotations. Now, let see it in a real map.

Remember this image?

Pretty overwhelming for the user, isn't it? We will try to get something like this.

The philosophy behind this image is the same as the previous posts. We have to create a QuadTree and ask this QuadTree for annotations in different regions of the visible map.

QuadTree class is pretty similar to the one that we used.

ClusterManager class will need to know the visible map region and the zoom level of the map for clustering annotations.

Depending on the zoom level, we will divide the map region in cells of different size and we will use this cells to ask the QuadTree for annotations inside these cells.

class func cellSizeForZoomScale(zoomScale: MKZoomScale) -> Int {

    let zoomLevel = zoomScaleToZoomLevel(scale: zoomScale)

    switch zoomLevel {
    case 0...4:
        return 32
    case 5...8:
        return 16
    case 9...16:
        return 8
    case 17...20:
        return 4
        return 10

The function clusterAnnotationWithinMapRectangle will do...

  • Calculate de size of the cell
  • Ask the QuadTree for annotations
  • Display annotations on the map.

public func clusterAnnotationWithinMapRectangle(visibleMapRect: MKMapRect, zoomScale: Double) {

        guard !zoomScale.isInfinite else {
        var clusterAnnotations = [MKAnnotation]()
        let cellSizePoints = Double(visibleMapRect.size.width/Double(PGClusteringManager.cellSizeForZoomScale(zoomScale: MKZoomScale(zoomScale))))
        let minX = visibleMapRect.minX
        let maxX = visibleMapRect.maxX
        let minY = visibleMapRect.minY
        let maxY = visibleMapRect.maxY

        operationQueue.addOperation {

            var yCoordinate = minY

            while yCoordinate<maxY {
                var xCoordinate = minX

                while xCoordinate<maxX {
                    let area = PGBoundingBox.mapRectToBoundingBox(mapRect: MKMapRect(x: xCoordinate, y: yCoordinate, width: cellSizePoints, height: cellSizePoints))
                    self.quadTree.queryRegion(searchInBoundingBox: area) { (annotations) in

                        if annotations.count>1 {
                            var totalX = 0.0
                            var totalY = 0.0

                            for annotation in annotations {
                                totalX += annotation.coordinate.latitude
                                totalY += annotation.coordinate.longitude
                            let totalAnnotations = annotations.count

                            clusterAnnotations.append(PGAnnotation(coordinate: CLLocationCoordinate2D(latitude: totalX/Double(totalAnnotations), longitude: totalY/Double(totalAnnotations)), title: "\(annotations.count)", subtitle: "Clustered"))
                        } else if annotations.count == 1 {
            self.delegate?.displayAnnotations(annotations: clusterAnnotations)

And that's it. You have an example here