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 (:
At one point I wrote a quad tree as part of the Map in SLAM to store probabilities of a point containing an obstacle on a 2d map, the thinking was I could use the quadtree to then navigate the robot.<p>The reality was for the detail I needed at the scale I needed quad trees sort of sucked at this (university is a great place to try and fail at things, I learned a bunch!)<p>I'd be really curious what is used now, if there's some shape estimations to collate points into blobs that are cheaper to store and navigate around. Been awhile since I read any books on robotics and navigation and SLAM though.
Understanding how quadtrees work was how I finally managed to develop an intuitive grasp of how octrees work. Great to know for any budding voxel enthusiast
Inspired by this post two years ago, I wrote a more comprehensive version: <a href="https://chidiwilliams.com/post/quadtrees/" rel="nofollow">https://chidiwilliams.com/post/quadtrees/</a>. Also showed how quadtrees could be used for compression.
Discussed at the time:<p><i>An interactive explanation of quadtrees</i> - <a href="https://news.ycombinator.com/item?id=7668628" rel="nofollow">https://news.ycombinator.com/item?id=7668628</a> - April 2014 (19 comments)