Skip to main content
2 of 2
added 6 characters in body
Romen
  • 416
  • 2
  • 8

I can't recommend a structure that actually implements what you're asking for, but it definitely won't work like a quad tree. It may not be a tree at all and it might not even exist...

A quad tree has a tree structure because each node represents the node above it divided into four quadrants. At any level these four quadrants cover all of the space covered by their parent. Every single point in the 2D space can be inserted at exactly one leaf node somewhere on the tree.

If you try to divide space into circles, you're not going to be able to find a set of circles that cover their parent circle completely and evenly. This geometric problem rules out the possibility that you can store these circles in a tree that will be useful to traverse for collision detection. There will always be points that are either not covered by a circle or covered by more than one circle. (That's bad because it means a point in 2D space either has nowhere to go in the tree or it has more than one place to go!)

Testing whether two circles intersect is simple, but I am not aware of anything simpler than just checking if the distance between them is less than the sum of their radii. You can save some CPU power on so many circle-circle tests by comparing the squared radii and distances and skipping the sqrt calculation.

Romen
  • 416
  • 2
  • 8