4 ms·
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 bi
by senderista 11mo ago
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.
- almostgotcaught 11mo ago> 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.
- mkehrt 11mo agoI 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.
- senderista 11mo agoThank you, that is exactly what I meant.
- senderista 11mo agoUh, 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?