Clustering comments without measuring a thing

Hi, it’s Megan, tldraw intern, here.

Comments in tldraw are on-the-canvas UI, like map pins: they stay anchored as you pan and zoom, but the pin itself never changes size. While this behavior makes sense, it also creates an issue: Zoom out far enough and spread-out conversations group together into a crowd of speech bubbles all talking over each other, making it impossible to differentiate one from the other.

To get around this, we cluster them. Pins nearby merge into a badge that says "5 comments here!", and individual comments pop out of the group as you zoom back in. But how do you actually make that happen?

The obvious way is to measure distances every frame: on each camera change, iterate over the pins, figure out which ones are too close together, and group the overlapping ones. We do none of that. While you move around the canvas, tldraw never measures the distance between comments.

This post is a deep dive into how I figured all of this out, and learned that the study of algorithms actually shows up in interesting places (and is not just something they teach at university to torture you).

Zoom is all you need

Initially, I knew that this algorithm had to be fast, and running some sort of distance algorithm every time you panned or zoomed would have been computationally expensive.

Instead, I explored the potential of computing clusters only when comments are placed or deleted, and keeping a record of exactly when things should merge after that. I needed an algorithm that figured out the set of shortest distances that covered all comments, which would become the order in which comments collapse as you zoom out.

If this seems like a familiar problem, it’s because it’s solved by computing the Euclidean minimum spanning tree (MST).

Once I had that figured out, all that I needed to do was translate those edge lengths into zoom thresholds. This was revolutionary because now the process hinged on a single variable, the current zoom level, and calculating whether things should cluster became a quick movement down an array.

To avoid flickering, I decided to cluster and uncluster at slightly different zoom levels, which became two thresholds per event in an array that you move along as the zoom level changes.

A small note. I did spend an afternoon on the wrong problem: Delaunay triangulation. It's such a wonderful O(n log n) algorithm and really speeds up the MST calculations, but it was massively overkill, so I dropped it. But to this day there is still an affordance in the codebase to swap in triangulation, just in case anyone ever finds themselves with a million comments on one tldraw page.

Testing out clustering at this point was really satisfying. The comments grouped themselves smoothly, and running experiments with thousands of comments on the canvas showed basically zero performance degradation. This algorithm seemed perfect. I was done… right?

I was not done

I started noticing more design flaws. The current algorithm meant that every edge in the MST was treated as a separate merge event, so things only ever merged in twos. 4 equally-spaced comments were forced to collapse into groups of 2, then 4, rather than just merging into 4 in the first place, which just felt wrong. A nice solution I found was to combine many merge events that happen soon after each other into one, and hand-tune an eagerness constant until the number of comments merging simultaneously felt right.

The evil twin of my 4 equally spaced comment example was a long line of comments. They're all equally spaced, so thresholds are all the same, but the two ends are really far apart: how do I choose what merges and what doesn't?

This is apparently a notoriously hard chaining problem, and I was re-discovering it. Intuitively: if we can postpone the eventual mass-merging of these pins, the result will look much less strange. I tried enforcing a max distance at which two nodes can merge in a single event. If two comments take up a small section of the screen, or if their distance isn't too far apart, it probably looks okay if they merge.

Now, sadly, I lied to you. That exact change also stopped making the cluster badges aesthetic and started making them functional (Noo! My perfect monotone sequence!). This reintroduces a small number of edge cases where things misbehave—later merges start triggering a cluster before earlier ones—so I enforce that any thresholds created can never return a "cluster now!" zoom level larger than the one previously returned.

The runtime is one (1) integer

To recap where we are: clustering is now a sequence of events, complexly and delicately arranged, and zooming far enough tells the UI "hey, cluster these comments now". When we order this sequence by descending merge zoom, a really lovely property drops out: the set of comments that are currently clustered forms an unbroken prefix of the list.

This seems obvious, but lets us throw away the huge chunk of information at runtime that says "comments x, y, z are in a cluster, a and b are apart," and instead record a single number, the index of the end of the current prefix.

Why is this cool? Well, a lesser algorithm might have had to, on every camera change, iterate over each cluster and check whether it was time for it to unmerge, or recompute distances between badges. All we do is perform a single comparison.

So it turns out that they really were teaching me useful things at university. Thanks tldraw for giving me the chance to over-engineer an algorithm.

Read about my past experiment, with second-finger-as-shift-key, here.

If you’re new to tldraw, it’s easy to get started with npm create tldraw@latest or through one of our starter kits.