Check for colliding circles

Question

I have some circles and I know their X, Y, and r. I want to check if ANY of them collide with ANY other...
The way to check is easy:

r₁+r₂ < sqrt((x₁-x₂) ² +(y₁-y₂)²)

but do I have to check all with all? It gives me O(n²) complexity, and I want to avoid that.

Answer 1

Try looking at KD-tree acc-struct. first you have to consider circles as squares way less complexity for computing intersection , than you put these squares in the modified KD-tree ,it will need some thinking but hopefully nothing too extreme ... Way kd-tree works is that it cancels out half of the possible matches based on some criteria for each tree level. Look it up on wiki. Good luck with your problem :)

Answer 2

You can divide your space into regions, like:

1. Compute 2D AABB - axis aligned bounding box for all the circles
2. Divide it into four sub boxes
3. To each of sub boxes assign circle, if circle even slightly crosses such box then it must be put into such box. This means that circle can be assigned to multiple boxes.
4. Iterate each circle, then check to which box it was assigned, and compute collision only with circles from that box.

In 2. you can do many subdivisions, depending on your space size, also if to many circles are assigned to one box then subdivide it further.