7 ms·
I feel like quadtrees are almost never the best data structure for a given problem. The rare exception being HashLife.
by 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 agowhat else would you use for spacial subdivision? bsp trees?
- hobs 4y agoWhy cant you use an N tree, what's special about 4?
- ShredKazoo 4y agoMaybe 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 agoI'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 ago8 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 agoI'm now super amused with myself for not looking for "oct." Which, yeah, would have been the obvious prefix to look for.
- ShredKazoo 4y agoA B-tree does in fact have >2 children for only a single dimension.
- taeric 4y agoRight. 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 agoYeah pretty much, a node in a B-Tree is designed to fill a single page of memory
- corysama 4y agoIn 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 agoGenerally the most popular is a BVH system between objects and a kd-Tree within objects, in my experience.
- boppo1 4y agoI'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 agoBVHes 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 agoThanks!
- taeric 4y agoSo 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 agoThis was my thinking, exactly. I have not tried implementing one before.
- deleted 4y ago[deleted]
- eutectic 4y agoSomething adaptive. Maybe AABB trees depending on the context.
- MrLeap 4y agoI'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 agoQuadtrees 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 agoWhat 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 agoQuadtrees 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]