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:
- Insert an object into the quadtree:
Check if the object intersects the current node. If so, recurse. If you’ve reached the leaf level, insert the object into the collection. - Delete an object from the quadtree:
Execute the exact same steps as if inserting the object, but when you’ve reached the leaf level delete it from the collection. - Test if an object intersects any object inside the quadtree:
Execute the exact same steps as if inserting the object, but when you’ve reached the leaf level check for collision with all the objects in the collection. - Test for all collisions between all objects inside the quadtree:
For every object in the quadtree execute the single object collision test. - Update the quadtree:
Delete all objects from the quadtree whose position has been modified and insert them again.
This has several advantages:
- By only storing objects in the leaves it is very easy to handle operations on the quadtree (fewer special cases)
- The quadtree can have leaves with different depth, thus allowing you to adapt the density of the quadtree depending on the spatial region it covers. This adaption can happen at runtime, thus keeping the object/node ratio optimal.
Only disatvantage:
- Objects can belong to several collections inside the quadtree. You’re going to need an extra linear collection outside the quadtree to enumerate every object without duplicates.