QuadTree: store only points, or regions?

I am developing a quadtree to keep track of moving objects for collision detection. Each object has a bounding shape, let's say they are all circles. (It's a 2D top-down game)

I am unsure whether to store only the position of each object, or the whole bounding shape.

If working with points, insertion and subdivision is easy, because objects will never span multiple nodes. On the other hand, a proximity query for an object may miss collisions, because it won't take the objects' dimensions into account. How to calculate the query region when you only have points?

If working with regions, how to handle an object that spans multiple nodes? Should it be inserted in the nearest parent node that completely contains it, even if this exceeds the node's capacity?

Thanks.

Answer

If storing extended objects (regions) in a quadtree, the object should be referenced from all the leaf nodes it touches. I wouldn't try to find the least common ancestor and store it there, because then e.g. a small object that happens to cross a high-level boundary will end up in a very high node, and must be tested against everything else in that large, high-level node when you do collision queries and suchlike.

However, you also have to be careful because large objects could end up being referenced from many nodes, making them expensive to update when they move around, and causing them to be re-checked many times for collisions etc. Depending on your use case it might be worth using some kind of heuristic to store large objects at a higher level in the tree, but this would complicate the algorithms, so I probably woudn't bother unless you establish that it's really a performance problem in your particular case.

Similarly, to query a region, the query should look at all the leaf nodes the queried region touches.

These basically use the same algorithm, which is to start with a region and push it down through the tree to find the leaf nodes it touches. It's a depth-first traversal, but at each node you can prune any children that don't touch the region. You'll need to maintain a stack to keep track of where you are in the traversal.