I like to do data-oriented programming, and was just thinking about how I want to organize (and search through) the primary data structures/concepts for a project I'm working on. Part of that involved thinking about things like what information I might cache and what representations data might take. That lead me to looking into the nuances of things like B-Trees, AVL Trees, Quadtrees, k-d trees and so forth.
I've found the book "Foundations of Multidimensional and Metric Data Structures" by Hanan Samet to be an excellent resource when looking for a slightly deeper dive than a more introductory algorithms course. It goes in depth on the nuances of these approaches, many of which are highly similar at a cursory glance.
Quadtrees are also quite useful for generating fractals.
A very related project of mine, Lambda Screen [0], explores this by encoding these functional quadtrees directly in lambda calculus and rendering the structure based on Church booleans being true (white) or false (black).
With fixed point recursion, this allows for very tiny definitions of IFS fractals. For example, fractals like the Sierpinski triangle/carpet only require ~50 bit of binary lambda calculus [1] [2]!
You can even build them with basically one line of code by sorting points using Morton / Z-curve order. It's linear time if you use a counting/radix sort.
Edit: lol, downvoted for this post. Never change, HN.
It’s super easy to click the downvote button by accident on mobile when you meant to upvote. And this UI will never be fixed because this is HN after all.
This is precisely the reason that I do not log in to HN on my phone. My phone is read-only and if I want to upvote or comment then I have to switch to my laptop. Pretty easy with firefox because I can send tabs to other devices.
Neat! Weirdly sending this article from my phone (Pixel 8) to my browser (Arc) via Pushbullet resulted in an incredibly strange bug that it loads this site instead:
I remember Arc randomly rewriting my bookmarks using some kind of summarization model or something like that, it also sometimes changed the name of downloaded files reinterpreting their names. Maybe it is related somehow.
Well, I guess it was the first AI-first browser, hence all this bs. I uninstalled it months ago...
Yeah that feature was nice at the start then got very annoying. Still like the browser though. Weirdly enough chrome on my phone has been reporting the wrong URLs, usually one I've just been on.
Apologies! I think I might have a found an eager redirect on the server. I haven't been able to reproduce, but you're not the first to report it. I hope it's fixed now.
I love the visualization, which gave me an idea: what if we numbered every "Looking at" step in the visualization? Then it's obvious just how many search steps it takes.
And then maybe even juxtapose that with a linear search example, which also numbers every step. I bet this would make it really click for some people. And for free the user can also play with how a linear search can sometimes be faster when they just want the first element!
As a bonus: allow the user to change the cell count so they can really feel just how each method scales!
I wish the article had made it clearer that quadtree positions are encoded as strings over the alphabet on 2 bits (similarly, octrees use the alphabet over 3 bits). This makes storing keys and lexicographically comparing them very simple.
> positions are encoded as strings over the alphabet on 2 bits
This is the most pedantic way of saying "binary 2-tuples" I've ever seen. Also for quadtrees this is inferior to base 4 because you can assume clockwise (or counter) ordering.
A general quadtree implementation question that puzzled me when I was implementing it myself for hobby games was: do you store a rectangle in the smallest node that completely contains it?
Most code that I saw that used quadtrees were treating things as points and storing them only at the lowest level.
I also made mine auto-divide by counting items that are entirely in a quadrant as they are added to the node, with allocate and split triggered if a count went above a certain threshold.
I like to do data-oriented programming, and was just thinking about how I want to organize (and search through) the primary data structures/concepts for a project I'm working on. Part of that involved thinking about things like what information I might cache and what representations data might take. That lead me to looking into the nuances of things like B-Trees, AVL Trees, Quadtrees, k-d trees and so forth.
I've found the book "Foundations of Multidimensional and Metric Data Structures" by Hanan Samet to be an excellent resource when looking for a slightly deeper dive than a more introductory algorithms course. It goes in depth on the nuances of these approaches, many of which are highly similar at a cursory glance.
Quadtrees are also quite useful for generating fractals. A very related project of mine, Lambda Screen [0], explores this by encoding these functional quadtrees directly in lambda calculus and rendering the structure based on Church booleans being true (white) or false (black).
With fixed point recursion, this allows for very tiny definitions of IFS fractals. For example, fractals like the Sierpinski triangle/carpet only require ~50 bit of binary lambda calculus [1] [2]!
[0]: https://text.marvinborner.de/2024-03-25-02.html
[1]: https://lambda-screen.marvinborner.de/?term=ERoc0CrYLYA%3D
[2]: https://lambda-screen.marvinborner.de/?term=QcCqqttsFtsI0OaA
"I could only find a couple tutorials/guides and both were imperative"
Aren't Quadtrees covered by almost all basic data-structure books? It is the most simple form of taking the binary tree into the next (2D) dimension.
You can even build them with basically one line of code by sorting points using Morton / Z-curve order. It's linear time if you use a counting/radix sort.
Edit: lol, downvoted for this post. Never change, HN.
I'd love to see that. Could you link me to an implementation or explain this in more detail please?
It’s super easy to click the downvote button by accident on mobile when you meant to upvote. And this UI will never be fixed because this is HN after all.
This is precisely the reason that I do not log in to HN on my phone. My phone is read-only and if I want to upvote or comment then I have to switch to my laptop. Pretty easy with firefox because I can send tabs to other devices.
That is why I like harmonic app, there is an invite button separating the upvote and downvote. Never going to have this kind of issue
Zoom in or unvote/revote
Neat! Weirdly sending this article from my phone (Pixel 8) to my browser (Arc) via Pushbullet resulted in an incredibly strange bug that it loads this site instead:
https://www.lindelystables.dk/en/posts/functional-quadtree-c...
Got very confused! I challenge the HN hivemind to figure out what's going on.
I remember Arc randomly rewriting my bookmarks using some kind of summarization model or something like that, it also sometimes changed the name of downloaded files reinterpreting their names. Maybe it is related somehow.
Well, I guess it was the first AI-first browser, hence all this bs. I uninstalled it months ago...
Yeah that feature was nice at the start then got very annoying. Still like the browser though. Weirdly enough chrome on my phone has been reporting the wrong URLs, usually one I've just been on.
Apologies! I think I might have a found an eager redirect on the server. I haven't been able to reproduce, but you're not the first to report it. I hope it's fixed now.
I love the visualization, which gave me an idea: what if we numbered every "Looking at" step in the visualization? Then it's obvious just how many search steps it takes.
And then maybe even juxtapose that with a linear search example, which also numbers every step. I bet this would make it really click for some people. And for free the user can also play with how a linear search can sometimes be faster when they just want the first element!
As a bonus: allow the user to change the cell count so they can really feel just how each method scales!
I wish the article had made it clearer that quadtree positions are encoded as strings over the alphabet on 2 bits (similarly, octrees use the alphabet over 3 bits). This makes storing keys and lexicographically comparing them very simple.
> positions are encoded as strings over the alphabet on 2 bits
This is the most pedantic way of saying "binary 2-tuples" I've ever seen. Also for quadtrees this is inferior to base 4 because you can assume clockwise (or counter) ordering.
A general quadtree implementation question that puzzled me when I was implementing it myself for hobby games was: do you store a rectangle in the smallest node that completely contains it?
Most code that I saw that used quadtrees were treating things as points and storing them only at the lowest level.
I also made mine auto-divide by counting items that are entirely in a quadrant as they are added to the node, with allocate and split triggered if a count went above a certain threshold.
Anything novel or oopsie?
We just did a whole visual identity around the quadtree concept. Take a scroll on this one! https://trace.systems/
That all sounds incredibly dystopian, ugh.
I think it is weird to have two cells divided downto their smallest size when my cursor clearly occupies only one of them, not two.
[dead]