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.<p>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.<p>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.<p>This is a great SO post on dynamic-style quadtrees: <a href="https://stackoverflow.com/questions/41946007/efficient-and-well-explained-implementation-of-a-quadtree-for-2d-collision-det/48330314#48330314" rel="nofollow">https://stackoverflow.com/questions/41946007/efficient-and-w...</a><p>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.<p>One day I'll open-source my code. I was going back to papers from the '80s for some of that stuff (: