Quadtrees

[aramadia]

So I understand quadtrees in that you recursively divide a square area into four smaller squares until there are no objects left.

Then when I got around to implementing it in order to speed up collision detection, what the heck do you do with an object that overlaps the "division" lines?

The objects i need to do collision detection on are various sized rectangles.

I can see three possible solutions
1) One big pool for objects that don't fit nicely in the box
2) Each square has five children, the four sub-squares, and one pool for objects that overlap multiple sub squares
3) Add the object to each sub-square it overlaps.

I'm probably missing the best one so I'm hoping you guys can fill me in.

Additionally, there will be several thousand rectangles so I'm looking for a fast solution.

[aramadia]

Help?? Every article I find on google shows you how to divide a square, but doesn't actually let you know what to do with overlaps.

[DemonWasp]

From: http://www.heroicvirtuecreations.com/QuadTree.html

"...we have added an AddObject function which should add the object to every quad tree leaf node that it overlaps with. Branch nodes never have objects in them, since they relegate all their calls to their children nodes."