3 ms·
A quad tree is just a 2 dimensional representation of binary tree. Instead of splitting at the midpoint of 1 dimension, you have a split at the midpoint of 2 di
by sophacles 13y ago
A quad tree is just a 2 dimensional representation of binary tree. Instead of splitting at the midpoint of 1 dimension, you have a split at the midpoint of 2 dimensions (resulting in 4 divisions).
A different way of putting it is, a binary tree partitions a line, a quad tree partitions a plane. An octree (http://en.wikipedia.org/wiki/Octree http://en.wikipedia.org/wiki/Octree) partitions a space, and so on.
For some cool variants also see k-d tree:
http://en.wikipedia.org/wiki/K-d_tree http://en.wikipedia.org/wiki/K-d_tree
And R-tree:
http://en.wikipedia.org/wiki/R-tree http://en.wikipedia.org/wiki/R-tree
- munificent 13y ago> A quad tree is just a 2 dimensional representation of binary tree. That would actually be a BSP tree, k-d tree or bounding volume hierarchy. A quad tree is a 2-d version of a trie.
- thedufer 13y agoOkay, that explanation sits a little better with me. The mathematical simplicity of splitting each dimension in half is very nice and clearly the simplest way to go when looked at in this way. Replacing the current non-answer with something along those lines would be a big improvement, I think.