by turtledragonfly on 2/15/2023, 6:26:51 AM
by bfrog on 2/15/2023, 12:07:04 AM
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.
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!)
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.
by stolen_biscuit on 2/15/2023, 3:19:40 AM
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
by chidiw on 2/15/2023, 2:42:43 PM
Inspired by this post two years ago, I wrote a more comprehensive version: https://chidiwilliams.com/post/quadtrees/. Also showed how quadtrees could be used for compression.
by eutectic on 2/14/2023, 11:14:48 PM
I feel like quadtrees are almost never the best data structure for a given problem. The rare exception being HashLife.
by dang on 2/15/2023, 5:53:35 AM
Discussed at the time:
An interactive explanation of quadtrees - https://news.ycombinator.com/item?id=7668628 - April 2014 (19 comments)
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 (: