Clustering Algorithm with SwiftUI

In a previous article I outlined how to coalesce map annotations in SwiftUI and MapKit for iOS. However, we left out an important factor: the actual clustering algorithm. In this second article we’ll complete the iOS implementation in detail. Although, we won’t go over how to write the algorithm, we’ll see how and why this particular algorithm is helpful for our use case. Read on to finish the map annotation clustering tutorial or to simply explore the Swift implementation of the clustering algorithm.

Clustering Algorithms

A Quick Primer

Our minds organize things into groups at lightening speed — literally the speed of electricity moving through our neurons. It’s easy for the human eye to group similar objects together but not as straightforward for a computer to do the same. In computer science this intelligence is called clustering and coding this intelligence may not be a trivial task. Essentially, clustering is classification, an important aspect of AI. People have already found various approaches to clustering, each algorithm having their own strengths and requirements. The design challenge is often knowing which one to apply for a given purpose.

The first clustering algorithm people often learn about is K-Means clustering. K-means finds clusters reliably when it’s told ahead of time how many clusters we need. Full implementations of K-means can also suggest an ideal amount of clusters. Generating a color palette consisting of four dominant colors from an image would be a great use of K-means. As useful as it is however, K-Means won’t quite accomplish the mapping task in this article.

When clustering geographic coordinates in an interactive map, the number of clusters will change depending on the zoom level. At lower zoom levels, when the camera is further away from the map, locations will appear closer together and so more closely clustered. At higher zoom levels, when the camera is closer to the map, locations will appear to be further apart and so less clustered. A mapping app requires an algorithm that can find any number of clusters at any zoom level.

Clustering results of DBSCAN and K-means for different scenarios

An algorithm called DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is well suited for clustering locations on a map. However, like other algorithms DBSCAN has its own limitations to consider. Before DBSCAN can find clusters, it needs to be given a standard distance between items — referred to as the epsilon. In a map interface, the distance between items changes as the zoom changes. Furthermore, finding the epsilon on a map requires some fairly complex (but standard) geodetic equations. Read on to see how SwiftUI has provided some helpful geodetic functions.

SwiftUI Tutorial

Final Steps

We left off the previous tutorial with an empty function called cluster, which we will now use to call the DBScan algorithm. NSHipster has done an amazing job making numerous algorithms available to the Swift developer community and we should have no problem implementing his code. In Xcode, click on the Project and go to the Package Dependencies tab. Now tap the “+” and search by the project url: https://github.com/NSHipster/DBSCAN. Select the “DBSCAN” project and Hit the “Add Package” button. Xcode will do it’s thing and let you know when the package is ready to use.

Once the package has been added to the Xcode project, let’s return to the cluster function. At the top of the file be sure to add the import statments for DBSCAN and for SIMD, an Apple vector library.

import DBSCAN
import simd

Now use this code for the body of cluster.

    static func cluster( items: [MKMapItem], epsilon: Double ) async -> [PlaceCluster] {
        guard !items.isEmpty else {
            return []
        }

        let dbScanTask = Task { () -> [PlaceCluster] in
            
            // put the locations in a format that DBSCAN can use
            var input: [SIMD3<Double>] = []
            for place in items {
                let coord = place.placemark.coordinate
                let vector = SIMD3<Double>(x:coord.latitude, y:coord.longitude, z:0.0)
                input.append(vector)
            }
            
            // create and run DBSCAN on the locations data
            let dbscan = DBSCAN(input)
            let (clusters, outliers) = dbscan(epsilon: epsilon, minimumNumberOfPoints: 1, distanceFunction: simd.distance)
           
            // return an array of PlaceClusters matching the clusters returned by DBSCAN 
            var foundClusters = [PlaceCluster]()
            for (_, cluster) in clusters.enumerated() {
                var itemsCluster = [MKMapItem]()
                if cluster.count > 0 {
                    for p in cluster {
                        let item = items.first(where: {$0.placemark.coordinate.latitude == p.x && $0.placemark.coordinate.longitude == p.y})
                        itemsCluster.append(item!)
                    }
                    let pointCluster = PlaceCluster(items:itemsCluster)
                    foundClusters.append(pointCluster)
                }
            }
            return (foundClusters)
        }
        
        return await dbScanTask.value
    }

As the code comments describe, the cluster function now puts the locations in a format that DBSCAN can use. After running DBSCAN, the resulting clusters need to be converted back into a format our app can use.

Thanks for reading. I hope this tutorial was valuable and offered some new tools for developers. I’m always happy to hear suggestions or questions from readers.

Happy coding!