As explained in the answer by Romen, there aren't many applicable data structures which are not based on rectangles. But there are a couple other optimizations you can do for circle-circle collisions which could reduce your demand for a more optimized data-structure.
Compare the square of the distance with the square of the radius.
If you want to check if a point is in a circle or if two circles intersect, you have to use the Pythagorean theorem, which in its naive implementation looks like this:
distX = a.x - b.x
distY = a.y - b.y
radiusSum = a.radius + b.radius;
dist = sqrt(distX * distX + distY * distY);
if (dist < radiusSum) {
// collision
}
Unfortunately, calculating the square-root of a number is a very expensive operation. Fortunately, you can replace that square-root with a much cheaper multiplication in this case. Just compare the squares of the sum of the radiii with the square of the distance:
distSquared = distX * distX + distY * distY;
if (distSquared < radiusSum * radiusSum) {
// collision
}
Also note that if you want to check if points are within a circle, then you only need to calculate the square of the radius once. If it's always the same circle, you can even cache it. You can also cache the square of the radius sum if you compare objects which all have the same radius.
Check bounding boxes and inner boxes first
While multiplications are cheaper than square-roots, they are still not as cheap as addition and subtraction. But what you can do using only subtraction and addition is comparison between two axis-aligned boxes. So by checking the inner and outer rectangles of the circles first, you can rule out or detect a lot of circle-circle collisions without having to actually check if the radii overlap.
- If the bounding squares of two circles do not intersect, then there can not be a collision
- If the inner squares intersect, then there must be a collision
- If the outer squares intersect but the inner ones do not, then there might be a collision, which means you have to calculate the square of the distance and compare it to the square of the sum of the radii
(note that when you have a game where objects move relatively slow and overlapping objects usually don't remain overlapped, then implementing the 2nd step might not be worth it. When two objects approach each other slowly, then you will in most cases detect a circle-circle collision before you detect an inner rectangle collision)
And if you want to check bounding boxes first...
...then a quad tree can be a useful optimization.
I personally prefer spatial hashes, though. They are easier to implement (IMO) and often work better if objects are relatively evenly distributed. But trees usually adapt better to scenarios where you have to deal with vastly different object densities.
