Aug 11, 2020 • 2 min read

Clustering map annotations using Quadtrees

Back in 2015, I was working on an mobile app that displayed expensive condos for sale in Manhattan. We had to show listings on a map and we were using Mapbox SDK. Mapbox was and is still a great mapping solution. It allows for great customization with colors and overlays, highly recommend it. It lacked one feature though -- clustering map annotations. I remembered reading an article from the amazing folks at Thoughtbot on How To Efficiently Display Large Amounts of Data on iOS Maps (Btw, the article is 7 years old now). But much of the explanation went over my head and I didn't have much time to investigate it given the project deadline. The app shipped without that feature and I was secretly hoping there would not be many listings. 😂

Fast forward to present, I've been itching to solve a nice mathematical or algorithmic problem and write a post on it.

A Primer on Quadtrees

To start with, we have a map with a lot of points that we'd like to cluster. The idea is to use a scanning box and run through the map checking how many points there are in each box. But the problem is, how to I know how many points exists in a certain region? To solve this we need a suitable data structure.

Now let's break down the problem in 1-dimension space. Given an array of sorted points, what would be the best way to find how many numbers are within a specific range? A Binary Search Tree is an excellent option to store these numbers in for this purpose.

BSTs can be used to easily find the rank of an item. Or even, find the number of nodes within a given range. So what if we could extend this logic to a 2-dimension space - Enter Quadtree.

• A quadtree is usually set with a certain capacity. The idea of a quadtree is that it breaks the space into 4 parts when it crosses the threshold capacity, hence the name quad-Trees. Each of the broken part is in-turn a quadtree.

• So if you notice, quadTree is a similar to a binary tree in two dimension. In 3D, it'll be an Octree and so on. So it doesn't scale that well for higher dimensions.