Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Functional Quadtrees

lbjgruppen.com

Post reply on HN
Print view View original

41–50 of 52 posts

Re: Functional Quadtrees

#41

Post by _jackdk_ »

quibono wrote: post #13
pixelpoet wrote: post #11

Earlier quoted context omitted.

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?

Here's a 3D version used in the creation of sparse voxel octrees:

https://forceflow.be/2013/10/07/morton-encodingdecoding-thro...

Here's an example from AWS, where lat/long pairs are put into a Z-index, which is used as a DynamoDB sort key, letting you efficiently query for items near a point.

https://aws.amazon.com/blogs/database/z-order-indexing-for-m...

Re: Functional Quadtrees

#42

Post by nanomonkey »

zelphirkalt wrote: post #33
torusle wrote: post #8

"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.

The problem is rather, that most data structure tutorials and books don't even get the idea, to introduce a purely functional version, but merely state the imperative versions. Coming up with the functional versions of data structures can be difficult. Papers about it can be hard to understand and often require one to already know some niche language, that a researcher used for the paper. Even if you can find a funct…

I've been looking for the same for scheme and clojure. Here are a few I've found:

Functional Data Structures and Algorithms, A Proof Assistant Approach by Tobias Nipkow (Ed.) [https://fdsa-book.net/functional_data_structures_algorithms....]

Purely Functional Data Structures thesis by Chris Okasaki [https://www.cs.cmu.edu/~rwh/students/okasaki.pdf]

https://en.wikipedia.org/wiki/Purely_functional_data_structu...

Re: Functional Quadtrees

#43

Post by KPGv2 »

andoando wrote: post #28
lemonwaterlime wrote: post #20

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 fou…

Dammit why these books have to be $60

because they have low demand, meaning they would lose money if the price were lower

Re: Functional Quadtrees

#44

Post by KPGv2 »

nanomonkey wrote: post #42
zelphirkalt wrote: post #33

Earlier quoted context omitted.

The problem is rather, that most data structure tutorials and books don't even get the idea, to introduce a purely functional version, but merely state the imperative versions. Coming up with the functional versions of data structures can be difficult. Papers about it can be hard to understand and often require one to already know some niche language, that a researcher used for the paper. Even if you can find a funct…

I've been looking for the same for scheme and clojure. Here are a few I've found: Functional Data Structures and Algorithms, A Proof Assistant Approach by Tobias Nipkow (Ed.) [ https://fdsa-book.net/functional_data_structures_algorithms.... ] Purely Functional Data Structures thesis by Chris Okasaki [ https://www.cs.cmu.edu/~rwh/students/okasaki.pdf ] https://en.wikipedia.org/wiki/Purely_functional_data_structu...

Okasaki's is basically the Bible for this stuff. Anyone writing data structure libraries in a functional language will have read this or have it on their to-read list.

Re: Functional Quadtrees

#45

Post by cpgxiii »

catapart wrote: post #39

I appreciate that this writeup takes care to call out use cases when they help with understanding! I do have a semi-unrelated question though: does using the recursive approach prevent it from being calculated efficiently on the GPU/compute shaders? Not that it matters; plenty of value in a CPU-bound version of a solution and especially one that is easy to understand when recursive. I was just wondering why the promi…

> I do have a semi-unrelated question though: does using the recursive approach prevent it from being calculated efficiently on the GPU/compute shaders?

Historically speaking, the use of recursion in shaders and GPGPU kernels (e.g. OpenCL "C" prior to 1.2) was effectively prohibited. The shader/kernel compiler would attempt to inline function calls, since traditional GPU models had little in the way of supporting call stacks like normal CPU programs have, and thus recursion would be simply banned in the shader/kernel language.

Re: Functional Quadtrees

#47

Post by senderista »

mkehrt wrote: post #36
almostgotcaught wrote: post #23

Earlier quoted context omitted.

> 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.

I don't think that's what they meant. It's the case you can use literal strings of bits to encode a (2^n)-tree node, so you use actual bitstring comparisons and operations to manipulate them. Rightshift gives you the parent and things like that. I don't think this is something the article cares about, though.

Thank you, that is exactly what I meant.

Re: Functional Quadtrees

#48

Post by senderista »

almostgotcaught wrote: post #23
senderista wrote: post #18

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.

Uh, base 4 is exactly what I meant. I guess I wasn't very clear that I mean positions are encoded as bitstrings, with one pair of bits for each level (and triples of bits for octrees). Is that clear enough for you?

Re: Functional Quadtrees

#49

Post by kristianp »

pavlov wrote: post #12
pixelpoet wrote: post #11

Earlier quoted context omitted.

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 true, however you can see if you downvoted by the "undown" link displayed instead of "unvote".

Re: Functional Quadtrees

#50

Post by zelphirkalt »

KPGv2 wrote: post #44
nanomonkey wrote: post #42

Earlier quoted context omitted.

I've been looking for the same for scheme and clojure. Here are a few I've found: Functional Data Structures and Algorithms, A Proof Assistant Approach by Tobias Nipkow (Ed.) [ https://fdsa-book.net/functional_data_structures_algorithms.... ] Purely Functional Data Structures thesis by Chris Okasaki [ https://www.cs.cmu.edu/~rwh/students/okasaki.pdf ] https://en.wikipedia.org/wiki/Purely_functional_data_structu...

Okasaki's is basically the Bible for this stuff. Anyone writing data structure libraries in a functional language will have read this or have it on their to-read list.

I have the book, but it also doesn't contain that many data structures. Some of the maybe most used (AVL tree?) are not in there.

Not all exercises have solutions. I get stuck on some exercise and have a hard time finding solutions to them, that I can compare with my implementations in Scheme. Not being a Haskell user (yet), I also have some issues translating Haskell to Scheme. In languages like Haskell one often controls flow by pattern matching on type. In Scheme one needs to make structures or records explicitly and use their predicates to explicitly check the type. It's all possible, but not exactly great for learning. Sort of the road has many sticks and stones to stumble.

Post reply on HN