I'm trying to use a quadtree for 2D collision detection, but I'm a little stumped on how to implement it. First of all, I'd have a quadtree which contains four subtrees (one representing each quadrant), as well as a collection of objects which don't fit into a single subtree.
When checking an object for collisions in the tree, I would do something like this (thanks to QuadTree for 2D collision detection):
To find all collisions within a quadtree tree:
To insert into a quadtree:
To update a quadtree:
Is this alright? Can it be improved?
Your quadtree structure isn't optimal. You're right to store 4 subtrees per node, but actual objects should only be stored inside the leaves, not inner nodes. Therefore the collection holding the actual objects needs to be moved to the leaves.
Let's have a look at the implementation of the operations:
This has several advantages:
Only disatvantage: