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?

Edit
Report