I have had to do some non-trivial work with quadtrees, and one thing I realized, which is not so well-advertised, is that there are really two main categories of quadtrees. So-called "linear" quadtrees are a somewhat different beast that the more typical "pointer to children" ones.

They're really just different representations of the same thing (a quadtree), but those representations have such different use-cases and performance characteristics that I tend to think of them differently.

Linear quadtrees typically use Morton codes (or another space-filling curve), and are good at doing fast queries against static data. You build the tree once, then query it lots. Whereas "standard" quadtrees are more about dynamism — being able to add and remove items quickly.

This is a great SO post on dynamic-style quadtrees: https://stackoverflow.com/questions/41946007/efficient-and-w...

It was quite hard for me to find open-source implementations of linear quadtrees. Whereas there are all kinds of implementations of the more common kind.

One day I'll open-source my code. I was going back to papers from the '80s for some of that stuff (:

You probably know this, but the S2 library has one: https://github.com/google/s2geometry