5 ms·

An interactive explanation of quadtrees

93 points by mbrubeck 13y ago

thedufer 13y ago
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.
mden 13y ago
I love quad and octrees but it's good to note that there's quite a bit of literature on them and for a good reason. I'm by no means an expert on them but here are some things worth knowing if you plan on using them: 1) The implementation shown is called a point region quadtree (pr quadtree) and subdivides the space equally for all divisions. This may seem like a neat approach until you consider what happens when there are two points very close to each other. Because you need each point to be in it's own node, you need to keep subdividing the region, which can result in a theoretically unbounded depth. There's a variant called compressed pr quadtree which handles this problem by removing all nodes that only have 1 non-empty child. This reduces the depth appropriately. 2) There is another strategy for dividing the space called point quadtrees (p quadtrees) which divides the regions at the point you are inserting. This gives an upper bound of the tree depth as the number of nodes inserted, which is still undesirable. To fix this, you have to choose the correct order for point insertion to obtain a well balanced tree with log_4(n) height. 3) The non-academic implementations I've seen do clever things like setting a maximal subdivision number and allowing multiple points within a leaf. 4) There are often alternatives to quadtrees that are simpler and usually effective enough such as subdividing the region into an mxn grid of equal proportion and using the grid squares as buckets for the elements that fall within them. Spatial data-structures are kinda fun but can have gotchas.
- gfodor 13y ago
  Pbrt has a pretty solid treatment implementing both a grid and octree.
- dandroid17 13y ago
  Someone must've taken CMSC420 with Meesh :)
  - mden 13y ago
    Indeed :) Curious, did you use any other information or was this a wild guess? As a side note, if anyone wants to go into more depth, Samet's "Foundations of Multidimansional and Metric Data Structures" (http://www.amazon.com/Foundations-Multidimensional-Structures-Kaufmann-Computer/dp/0123694469 http://www.amazon.com/Foundations-Multidimensional-Structure...) is an extensive survey of a lot of spatial data structures.
Arkadir 13y ago
> Roll the mouse wheel inside of the tree view. If you are on a touchscreen device, pinch out. I have neither mouse wheel nor touchscreen device, only a touchpad.
- anaphor 13y ago
  Drag in a downard motion on your touchpad with two fingers, alternatively draw a circle with one finger.
rhengles 13y ago
Very interesting! I developed a similar system myself, for dates on a timeline instead of spatial data. I just knew that comparing dates of every item was inefficient!
orthecreedence 13y ago
If my points are always moving and updating in position, is this method efficient? If not, what's a good way of finding nearest-neighbor for a set of data points that are constantly morphing?
- muhuk 13y ago
  This you might find useful: http://gamedev.stackexchange.com/questions/72392/handle-movement-with-quadtree http://gamedev.stackexchange.com/questions/72392/handle-move...
NAFV_P 13y ago
Great article. I've been messing around with trees recently, this variant is very interesting [0]. Basically, you can treat a tree like an array. This is the first time I have come across quad and oct trees, but I think the order statistic concept can be applied here. [0] http://www.cs.cornell.edu/courses/cs211/2004su/slides/Topic20b.pdf http://www.cs.cornell.edu/courses/cs211/2004su/slides/Topic2...
pacaro 13y ago
Great article. A description of Quadkeys would be great here too. The quadkey can be thought of as a representation of the route to a point, i.e each time a rectangle is divided, each of its quadrants is assigned a letter A-D (or number 0-3) and the quad key for a point is the concatenation of those labels from the top of the tree down to (typically) an arbitrary depth. If a quadkey is then used as an indexed field in a database, the question "All the points in a specific quadrant" is simply a prefix search
BinaryBullet 13y ago
The https://www.dashingd3js.com/ https://www.dashingd3js.com/ mailing list had some pretty cool links relating to quadtrees this week (this article included). Here's another one: http://bl.ocks.org/patricksurry/6478178 http://bl.ocks.org/patricksurry/6478178 Which also links: http://bl.ocks.org/mbostock/4343214 http://bl.ocks.org/mbostock/4343214 I found the 'Voronoi Tessellation' to be really mind bending: http://bl.ocks.org/mbostock/4060366 http://bl.ocks.org/mbostock/4060366
gdubs 13y ago
I made a video of an octree implementation a little while ago -- kind of neat to see how it subdivides as the particles move around the space: http://vimeo.com/35334594 http://vimeo.com/35334594

93 points by mbrubeck 13y ago

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.

mden 13y ago

I love quad and octrees but it's good to note that there's quite a bit of literature on them and for a good reason. I'm by no means an expert on them but here are some things worth knowing if you plan on using them: 1) The implementation shown is called a point region quadtree (pr quadtree) and subdivides the space equally for all divisions. This may seem like a neat approach until you consider what happens when there are two points very close to each other. Because you need each point to be in it's own node, you need to keep subdividing the region, which can result in a theoretically unbounded depth. There's a variant called compressed pr quadtree which handles this problem by removing all nodes that only have 1 non-empty child. This reduces the depth appropriately. 2) There is another strategy for dividing the space called point quadtrees (p quadtrees) which divides the regions at the point you are inserting. This gives an upper bound of the tree depth as the number of nodes inserted, which is still undesirable. To fix this, you have to choose the correct order for point insertion to obtain a well balanced tree with log_4(n) height. 3) The non-academic implementations I've seen do clever things like setting a maximal subdivision number and allowing multiple points within a leaf. 4) There are often alternatives to quadtrees that are simpler and usually effective enough such as subdividing the region into an mxn grid of equal proportion and using the grid squares as buckets for the elements that fall within them. Spatial data-structures are kinda fun but can have gotchas.

gfodor 13y ago
Pbrt has a pretty solid treatment implementing both a grid and octree.
dandroid17 13y ago
Someone must've taken CMSC420 with Meesh :)
- mden 13y ago
  Indeed :) Curious, did you use any other information or was this a wild guess? As a side note, if anyone wants to go into more depth, Samet's "Foundations of Multidimansional and Metric Data Structures" (http://www.amazon.com/Foundations-Multidimensional-Structures-Kaufmann-Computer/dp/0123694469 http://www.amazon.com/Foundations-Multidimensional-Structure...) is an extensive survey of a lot of spatial data structures.

Arkadir 13y ago

> Roll the mouse wheel inside of the tree view. If you are on a touchscreen device, pinch out. I have neither mouse wheel nor touchscreen device, only a touchpad.

anaphor 13y ago
Drag in a downard motion on your touchpad with two fingers, alternatively draw a circle with one finger.

rhengles 13y ago

Very interesting! I developed a similar system myself, for dates on a timeline instead of spatial data. I just knew that comparing dates of every item was inefficient!

orthecreedence 13y ago

If my points are always moving and updating in position, is this method efficient? If not, what's a good way of finding nearest-neighbor for a set of data points that are constantly morphing?

muhuk 13y ago
This you might find useful: http://gamedev.stackexchange.com/questions/72392/handle-movement-with-quadtree http://gamedev.stackexchange.com/questions/72392/handle-move...

NAFV_P 13y ago

Great article. I've been messing around with trees recently, this variant is very interesting [0]. Basically, you can treat a tree like an array. This is the first time I have come across quad and oct trees, but I think the order statistic concept can be applied here. [0] http://www.cs.cornell.edu/courses/cs211/2004su/slides/Topic20b.pdf http://www.cs.cornell.edu/courses/cs211/2004su/slides/Topic2...

pacaro 13y ago

Great article. A description of Quadkeys would be great here too. The quadkey can be thought of as a representation of the route to a point, i.e each time a rectangle is divided, each of its quadrants is assigned a letter A-D (or number 0-3) and the quad key for a point is the concatenation of those labels from the top of the tree down to (typically) an arbitrary depth. If a quadkey is then used as an indexed field in a database, the question "All the points in a specific quadrant" is simply a prefix search

BinaryBullet 13y ago

The https://www.dashingd3js.com/ https://www.dashingd3js.com/ mailing list had some pretty cool links relating to quadtrees this week (this article included). Here's another one: http://bl.ocks.org/patricksurry/6478178 http://bl.ocks.org/patricksurry/6478178 Which also links: http://bl.ocks.org/mbostock/4343214 http://bl.ocks.org/mbostock/4343214 I found the 'Voronoi Tessellation' to be really mind bending: http://bl.ocks.org/mbostock/4060366 http://bl.ocks.org/mbostock/4060366

gdubs 13y ago

I made a video of an octree implementation a little while ago -- kind of neat to see how it subdivides as the particles move around the space: http://vimeo.com/35334594 http://vimeo.com/35334594