Quadtree for 2D collision detection

Question

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):

1. Check the object for collisions with any objects in the current node.
2. For any subtree whose space overlaps the object, recurse.

To find all collisions within a quadtree tree:

1. Check each object in the current node against each other object in the current node.
2. Check each object in the current node against each subtree.

To insert into a quadtree:

1. If the object fits into multiple subtrees, then add it to the current node, and return.
2. Otherwise, recurse into whichever subtree contains it.

To update a quadtree:

1. Recurse into each subtree.
2. If any element in the current node no longer fits completely in the current tree, move it to the parent.
3. If any element in the current node fits into a subtree, insert it into the subtree.

Is this alright? Can it be improved?

Answer 1

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:

1. 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.
2. 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.
3. 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.
4. Test for all collisions between all objects inside the quadtree:
   For every object in the quadtree execute the single object collision test.
5. 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.

Answer 2

Quad trees are not always the best data structure for collision detection. The overhead of a quadtree can potentially be unbounded (if you don't limit the depth of the tree), and in the worst case don't give any speed up at all. Instead, you might want to consider using a sparse grid, which gives better performance than a quadtree only without the extra overhead of traversing multiple tree levels.

There are also other completely different approaches which might be even better. For example, you could try implementing Zomorodian and Edelsbrunner's algorithm, as I did in the following module:

• https://github.com/mikolalysenko/box-intersect

Here are also some articles which I wrote that discuss these issues in more detail:

• http://0fps.net/2015/01/07/collision-detection-part-1/
• http://0fps.net/2015/01/18/collision-detection-part-2/
• http://0fps.net/2015/01/23/collision-detection-part-3-benchmarks/

In particular, if you look at the benchmarks in the last section you will see that of all the libraries surveyed, quadtrees tended to perform quite poorly compared to other collision detection methods like R-Trees, grids or segment trees.