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.
Simply mentioning PR and P Quadtrees tipped me off since that class is the only time I've ever heard of those data structures mentioned. Then I checked out your website and saw you went to UMD. Case closed, haha.
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.
It seems like you could balance as you went along in a similar fashion to balanced binary trees such as b-trees or AVL trees.
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.