Map clustering algorithms

When you zoom out and 10,000 points overlap into a blob, you need clustering. Rendering 10,000 individual markers at zoom 5 provides no useful information — the entire city is covered by overlapping dots. Clustering groups nearby points into summary markers that convey density without visual chaos. Toggle the visualization to see the difference.

Grid clustering

Snap each point to a grid cell of size $s$ pixels at the current zoom level. All points in the same cell merge.

$$\text{cellX} = \lfloor p_x / s \rfloor$$ $$\text{cellY} = \lfloor p_y / s \rfloor$$ $$\text{key} = \text{cellX}\_\text{cellY}$$

Fast, simple, but produces ugly square boundaries that shift as you pan. The cell boundaries are fixed to the pixel grid, not to the data, so panning even a few pixels causes points to jump between clusters.

Distance-based (DBSCAN-lite)

For each point, find all unclustered neighbors within radius r (in pixels). Form a cluster. Repeat. $O(n^2)$ naively, but with a spatial index it becomes $O(n \log n)$.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is the full algorithm, which also identifies noise points that don't belong to any cluster. For map rendering, you typically skip the noise classification and cluster everything, which simplifies the implementation.

Supercluster algorithm (Mapbox)

The state of the art for web maps:

1. Start with all points at max zoom.
2. For each lower zoom level, cluster points within radius pixels using a KD-tree.
3. Each cluster has a representative position (weighted average) and a count.
4. At render time, query the precomputed tree for the visible bbox at the current zoom.

This is what supercluster.js does. Pre-computation makes pan/zoom essentially free.