Return to Revisions

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, 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
}

But you can replace that square-root with a much cheaper multiplication if you compare with 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 rectangles of two circles do not intersect, then there can not be a collision
• If the inner rectangle intersect, then there must be a collision
• When the outer rectangles intersect but the inners 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

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.