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 (:
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.
You probably know this, but the S2 library has one: https://github.com/google/s2geometry
Though I must say, looking at it briefly, I see no direct mention of "linear quadtree" (or even just "quadtree"), nor morton codes, z-order curves, BIGMIN/LITMAX functions, etc.
I suppose that's another difficulty with quadtrees — they're so common and amenable to hand-rolling that there are lots of different variations on terminology.
Do you happen to know where the linear-quadtree-related code is, in that library?
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.
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.
"Second is to use more exotic and complex space decomposition algorithms"
these being what
What is this: "algorithm phase space"
An interactive explanation of quadtrees - https://news.ycombinator.com/item?id=7668628 - April 2014 (19 comments)
