5 ms·

Cool visualization. I hadn't heard of quad trees and this presented them in a very clear way. Within a couple of minutes I understood how they work and what t

Cool visualization. I hadn't heard of quad trees and this presented them in a very clear way. Within a couple of minutes I understood how they work and what they are used for (the hit detection use-case particularly resonated with me). Couple of minor gripes, though. It encourages you to play with the first pair of tree/map, which involves a lot of scrolling (which is stolen and zooms if I accidentally hover the tree). This would've been a lot easier if I'd been encouraged to move on and see the side-by-side (or maybe omit the bigger versions completely). Also, you asked my biggest question ("Why four children?") and then completely failed to answer it. This looks like it could be implemented trivially as a binary tree (twice as deep, of course). Why 4? Why not 2, or 8? Arguing "by definition" tells me nothing.

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 ago
  Okay, 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.

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 ago
Okay, 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.