Collision detection of huge number of circles

Posted by Tomek Tarczynski on Stack Overflow See other posts from Stack Overflow or by Tomek Tarczynski
Published on 2010-03-30T10:30:07Z Indexed on 2010/03/30 10:33 UTC
Read the original article Hit count: 480

Filed under:
|

What is the best way to check collision of huge number of circles?
It's very easy to detect collision between two circles, but if we check every combination then it is O(n^2) which definitely not an optimal solution.

We can assume that circle object has following properties:
-Coordinates
-Radius
-Velocity
-Direction
Velocity is constant, but direction can change.

I've come up with two solutions, but maybe there are some better solutions.

Solution 1
Divide whole space into overlapping squares and check for collision only with circles that are in the same square. Squares needs to overlap so there won't be a problem when circle moves from one square to another.

Solution 2
At the beginning distances between every pair of circles need to be calculated.
If the distance is small then these pair is stored in some list, and we need to check for collision in every update.
If the distance is big then we store after which update there can be a collision (it can be calculated because we know the distance and velocitites). It needs to be stored in some kind of priority queue. After previously calculated number of updates distance needs to be checked again and then we do the same procedure - put it on the list or again in the priority queue.

© Stack Overflow or respective owner

Related posts about circle

Related posts about collision-detection