Why should i use AABB for Circle-Circle collision

Question

In my wip game i have to implement Circle-Circle collisions. To implement this i simply calculate the square distance between their Centers (x1-x2)² + (y1-y2)². If this is smaller then their sqared radiuses (r1+r2)² a collision happened. But today i saw this link: Circle-Circle collision

Here they first use AABB collision to notice if the circles are near. But why should i do this? The circle-circle collision is a simple and not realy expensive calculation. When i use the AABB first i do at least the same number of calculations and if circles are near even more.

Let me explain:

I do an AABB collision detection for every circle with every other. So i have to do n! / (n-2)! calculations. n = number of circles to test. For every AABB colliding circle-pair i then have to do another calculation if they realy collide.

Without the AABB collision detection i only do n! / (n-2)! calculations and i don't think this calculations are so costly. What do you think?

Answer 1

This comment is the right answer. It depends on your Hardware and compiler. If you are using AABB detection first you have 8 add + 4 compare operations. If you compare the square distance and the square radiuses you do 6 add/subtract + 3 multiply + 1 compare. Maybe your hardware and compiler is faster with compares then with multiplications. But it shouldn't be a big difference in performance. If you instead of comparing the squares use the square roots (for whatever reason) you should do the AABB compare first cause square root calculations take some time. There are ofc also better Solutions like in this answer. If you have to do many detections between many objects you can think about one of this solutions.

Answer 2

I think here is way you can do this in O(NlogN) in average case but O(N^2) in worst : -

1. Consider each circle as rectangle of 2R*2R with center at center of circle.

2. Use sweep line algorithm for rectangles which is O(NlogN + R) where is number of intersections.

3. The intersecting pairs of rectangles can be checked as circles for intersection using your algorithm in O(R^2).

Note: If R is small then it is O(NlogN) but else if R = O(N) then it is O(N^2)