6 ms·

An interactive explanation of quadtrees (2014)

102 points by nbaksalyar 4y ago

eutectic 4y ago
I feel like quadtrees are almost never the best data structure for a given problem. The rare exception being HashLife.
- convolvatron 4y ago
  what else would you use for spacial subdivision? bsp trees?
  - hobs 4y ago
    Why cant you use an N tree, what's special about 4?
    - ShredKazoo 4y ago
      Maybe having the struct size be constant allows for better space locality in memory? You never have to reallocate nodes, you can pack everything into an array.
      - taeric 4y ago
        I'm now very curious on this. My gut was more that it is 2^(number of dimensions) that is important here. As such, for a single dimensional storage of data, standard binary tree. Add in another dimension, but still want to halve the search space with every comparison, add another branch factor to the tree. That said, this implies that for 3d space, you would want 8 way trees? But, I don't think I've ever heard of that being done/used.
        EliasLittle 4y ago
        8 way trees are used for 3D, they’re called Octrees. https://en.wikipedia.org/wiki/Octree?wprov=sfti1 https://en.wikipedia.org/wiki/Octree?wprov=sfti1
        taeric 4y ago
        I'm now super amused with myself for not looking for "oct." Which, yeah, would have been the obvious prefix to look for.
        ShredKazoo 4y ago
        A B-tree does in fact have >2 children for only a single dimension.
        taeric 4y ago
        Right. But that is more to optimize cache/block reads, right? Been way too long since I've looked at many of those details. :)
        ShredKazoo 4y ago
        Yeah pretty much, a node in a B-Tree is designed to fill a single page of memory
        corysama 4y ago
        In ray-tracing, people debate back and forth between kd-trees, octrees, quad-AABB trees, oct-AABB trees, and I’m sure there are a few more. I think quad-AABB has been the most popular option for a while now.
        sudosysgen 4y ago
        Generally the most popular is a BVH system between objects and a kd-Tree within objects, in my experience.
        boppo1 4y ago
        I'm a noob to DS&A, but I'm writing a little add-on for Blender and have come up against BVH and kd-trees. What makes one more popular for 'within objects' and the other for 'between'?
        sudosysgen 4y ago
        BVHes handle sparsity and very large scenes with variable density very well, so they are good to be able to see which objects you might intersect. kd-Trees are much better for objects because they handle the high density of geometry very well and are thus very effective if you want to test against a million triangles in close proximity, for example.
        boppo1 4y ago
        Thanks!
        taeric 4y ago
        So many things to read up on, now! :D Thanks for the pointers!
        misja111 4y ago
        > My gut was more that it is 2^(number of dimensions) that is important here. Yes, it's just binary search but applied to every dimension.
        taeric 4y ago
        This was my thinking, exactly. I have not tried implementing one before.
    - deleted 4y ago
      [deleted]
  - eutectic 4y ago
    Something adaptive. Maybe AABB trees depending on the context.
  - MrLeap 4y ago
    I'm a fan of spatial hash grids for most of the things I would consider quadtrees for. It's simpler to reason about and there's no monkeying around with trees when you add an element or move one around.
- jandrewrogers 4y ago
  Quadtrees have the distinction of being the simplest space decomposition data structures that also manifest every pathology and difficulty of said data structures. It is a great data structure to study for this reason. While they work well in some applications, many people opt for one of two algorithm selection strategies as an alternative. First, select a more narrowly tailored algorithm that fits their application domain and requirements but avoiding many of the pathologies, giving up some generality but retaining the simplicity. R-trees are arguably an example of this (albeit a bit more complex). Second is to use more exotic and complex space decomposition algorithms that are significantly more difficult to implement in practical systems but retain at least as much generality while mitigating or eliminating most pathological cases. A quadtree isn't a local maxima in the algorithm phase space in the same way a b+tree is.
  - heisjustsosmart 4y ago
    What pathology and difficulty? "Second is to use more exotic and complex space decomposition algorithms" these being what What is this: "algorithm phase space"
    - jandrewrogers 4y ago
      Quadtrees have exceptional scalability but also notorious issues with space complexity and selectivity for some common data models. Space complexity is unbounded space for non-scalar types, hence why r-trees are used in practice for things like polygons. They have poor search selectivity as a function of index size for many data models, quasi-monotonic data like time-series being an extreme case. In alternative algorithms that try to preserve scalability, these issues are handled via a combination compressing out non-selective branches of the index, for which there are many techniques in literature with various tradeoffs when applied to space decomposition, and by embedding the data model into a higher dimensionality index of a similar type, allowing the algorithm to be selective on additional properties of the data not for the purpose of search but to cause the data to organize in such a way that it is more resistant to manifesting selectivity and space complexity issues. There are hundreds of described spatial indexing algorithms in literature that tackle the selectivity and space complexity issues in various ways, often by sacrificing the natural scalability of quadtrees in various ways. The space of possible algorithm designs with interesting tradeoffs is very large but bounded. Hanan Samet's canonical text on the algorithm design space weighs in at over a thousand pages and still doesn't cover the full scope of notable algorithm design clusters in public literature.
- deleted 4y ago
  [deleted]
bfrog 4y ago
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.
stolen_biscuit 4y ago
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
dang 4y ago
Discussed at the time: An interactive explanation of quadtrees - https://news.ycombinator.com/item?id=7668628 https://news.ycombinator.com/item?id=7668628 - April 2014 (19 comments)
turtledragonfly 4y ago
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-well-explained-implementation-of-a-quadtree-for-2d-collision-det/48330314#48330314 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 (:
- exDM69 4y ago
  I'm also working on a linear octree (like quadtree but 3d) right now. An array sorted by Morton code is a quadtree/octree and an equally spaced kd-tree. Radix sorting can be used for sorting in linear time (and GPUs). When looking at the Morton code, if the most significant bit is 0 then it is on the left side of the x=0 plane, and right side if the bit is 1. You can find the split position where the bit flips with binary search. Then recurse to both halves using the next most significant bit which corresponds to the y=0 plane. Each level of recursion splits the space in two. You could also get the splits "for free" from the histograms produced during radix sorting to reduce the number of binary searches. This idea can be extended to AABBs instead of points by XORing the end point Morton codes and counting the leading zeros. A lot of literature was written on this topic in the past 10-20 years for the purpose of building acceleration structures for Ray tracing on the GPU.
- gniv 4y ago
  > It was quite hard for me to find open-source implementations of linear quadtrees. You probably know this, but the S2 library has one: https://github.com/google/s2geometry https://github.com/google/s2geometry
chidiw 4y ago
Inspired by this post two years ago, I wrote a more comprehensive version: https://chidiwilliams.com/post/quadtrees/ https://chidiwilliams.com/post/quadtrees/. Also showed how quadtrees could be used for compression.

102 points by nbaksalyar 4y ago

eutectic 4y ago

I feel like quadtrees are almost never the best data structure for a given problem. The rare exception being HashLife.

convolvatron 4y ago
what else would you use for spacial subdivision? bsp trees?
- hobs 4y ago
  Why cant you use an N tree, what's special about 4?
  - ShredKazoo 4y ago
    Maybe having the struct size be constant allows for better space locality in memory? You never have to reallocate nodes, you can pack everything into an array.
    - taeric 4y ago
      I'm now very curious on this. My gut was more that it is 2^(number of dimensions) that is important here. As such, for a single dimensional storage of data, standard binary tree. Add in another dimension, but still want to halve the search space with every comparison, add another branch factor to the tree. That said, this implies that for 3d space, you would want 8 way trees? But, I don't think I've ever heard of that being done/used.
      - EliasLittle 4y ago
        8 way trees are used for 3D, they’re called Octrees. https://en.wikipedia.org/wiki/Octree?wprov=sfti1 https://en.wikipedia.org/wiki/Octree?wprov=sfti1
        taeric 4y ago
        I'm now super amused with myself for not looking for "oct." Which, yeah, would have been the obvious prefix to look for.
      - ShredKazoo 4y ago
        A B-tree does in fact have >2 children for only a single dimension.
        taeric 4y ago
        Right. But that is more to optimize cache/block reads, right? Been way too long since I've looked at many of those details. :)
        ShredKazoo 4y ago
        Yeah pretty much, a node in a B-Tree is designed to fill a single page of memory
      - corysama 4y ago
        In ray-tracing, people debate back and forth between kd-trees, octrees, quad-AABB trees, oct-AABB trees, and I’m sure there are a few more. I think quad-AABB has been the most popular option for a while now.
        sudosysgen 4y ago
        Generally the most popular is a BVH system between objects and a kd-Tree within objects, in my experience.
        boppo1 4y ago
        I'm a noob to DS&A, but I'm writing a little add-on for Blender and have come up against BVH and kd-trees. What makes one more popular for 'within objects' and the other for 'between'?
        sudosysgen 4y ago
        BVHes handle sparsity and very large scenes with variable density very well, so they are good to be able to see which objects you might intersect. kd-Trees are much better for objects because they handle the high density of geometry very well and are thus very effective if you want to test against a million triangles in close proximity, for example.
        boppo1 4y ago
        Thanks!
        taeric 4y ago
        So many things to read up on, now! :D Thanks for the pointers!
      - misja111 4y ago
        > My gut was more that it is 2^(number of dimensions) that is important here. Yes, it's just binary search but applied to every dimension.
        taeric 4y ago
        This was my thinking, exactly. I have not tried implementing one before.
  - deleted 4y ago
    [deleted]
- eutectic 4y ago
  Something adaptive. Maybe AABB trees depending on the context.
- MrLeap 4y ago
  I'm a fan of spatial hash grids for most of the things I would consider quadtrees for. It's simpler to reason about and there's no monkeying around with trees when you add an element or move one around.
jandrewrogers 4y ago
Quadtrees have the distinction of being the simplest space decomposition data structures that also manifest every pathology and difficulty of said data structures. It is a great data structure to study for this reason. While they work well in some applications, many people opt for one of two algorithm selection strategies as an alternative. First, select a more narrowly tailored algorithm that fits their application domain and requirements but avoiding many of the pathologies, giving up some generality but retaining the simplicity. R-trees are arguably an example of this (albeit a bit more complex). Second is to use more exotic and complex space decomposition algorithms that are significantly more difficult to implement in practical systems but retain at least as much generality while mitigating or eliminating most pathological cases. A quadtree isn't a local maxima in the algorithm phase space in the same way a b+tree is.
- heisjustsosmart 4y ago
  What pathology and difficulty? "Second is to use more exotic and complex space decomposition algorithms" these being what What is this: "algorithm phase space"
  - jandrewrogers 4y ago
    Quadtrees have exceptional scalability but also notorious issues with space complexity and selectivity for some common data models. Space complexity is unbounded space for non-scalar types, hence why r-trees are used in practice for things like polygons. They have poor search selectivity as a function of index size for many data models, quasi-monotonic data like time-series being an extreme case. In alternative algorithms that try to preserve scalability, these issues are handled via a combination compressing out non-selective branches of the index, for which there are many techniques in literature with various tradeoffs when applied to space decomposition, and by embedding the data model into a higher dimensionality index of a similar type, allowing the algorithm to be selective on additional properties of the data not for the purpose of search but to cause the data to organize in such a way that it is more resistant to manifesting selectivity and space complexity issues. There are hundreds of described spatial indexing algorithms in literature that tackle the selectivity and space complexity issues in various ways, often by sacrificing the natural scalability of quadtrees in various ways. The space of possible algorithm designs with interesting tradeoffs is very large but bounded. Hanan Samet's canonical text on the algorithm design space weighs in at over a thousand pages and still doesn't cover the full scope of notable algorithm design clusters in public literature.
deleted 4y ago
[deleted]

bfrog 4y ago

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.

stolen_biscuit 4y ago

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

dang 4y ago

Discussed at the time: An interactive explanation of quadtrees - https://news.ycombinator.com/item?id=7668628 https://news.ycombinator.com/item?id=7668628 - April 2014 (19 comments)

turtledragonfly 4y ago

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-well-explained-implementation-of-a-quadtree-for-2d-collision-det/48330314#48330314 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 (:

exDM69 4y ago
I'm also working on a linear octree (like quadtree but 3d) right now. An array sorted by Morton code is a quadtree/octree and an equally spaced kd-tree. Radix sorting can be used for sorting in linear time (and GPUs). When looking at the Morton code, if the most significant bit is 0 then it is on the left side of the x=0 plane, and right side if the bit is 1. You can find the split position where the bit flips with binary search. Then recurse to both halves using the next most significant bit which corresponds to the y=0 plane. Each level of recursion splits the space in two. You could also get the splits "for free" from the histograms produced during radix sorting to reduce the number of binary searches. This idea can be extended to AABBs instead of points by XORing the end point Morton codes and counting the leading zeros. A lot of literature was written on this topic in the past 10-20 years for the purpose of building acceleration structures for Ray tracing on the GPU.
gniv 4y ago
> It was quite hard for me to find open-source implementations of linear quadtrees. You probably know this, but the S2 library has one: https://github.com/google/s2geometry https://github.com/google/s2geometry

chidiw 4y ago

Inspired by this post two years ago, I wrote a more comprehensive version: https://chidiwilliams.com/post/quadtrees/ https://chidiwilliams.com/post/quadtrees/. Also showed how quadtrees could be used for compression.