algorithm - Collision detection of huge number of circles

Question

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²) 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 need to overlap so there won't be a problem when a 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.

Answers to Mark Byers questions

1. Is it for a game?
   It's for simulation, but it can be treated also as a game
2. Do you want to recalculate the new position every n milliseconds, and also check for collisions at this time?
   Yes, time between update is constant.
3. Do you want to find the time at which the first/every collision occurs?
   No, I want to find every collision and do 'something' when it occures.
4. How important is accuracy?
   It depends on what do you mean by accuracy. I need to detect all collisions.
5. Is it a big problem if very small fast moving circles can pass through each other occasionally?
   It can be assumed that speed is so small that it won't happen.

Answer 1

There are "spatial index" data-structures for storing your circles for quick comparison later; Quadtree, r-tree and kd-tree are examples.

Solution 1 seems to be a spatial index, and solution 2 would benefit from a spatial index every time you recalculate your pairs.

To complicate matters, your objects are moving - they have velocity.

It is normal to use spatial indexes for objects in games and simulations, but mostly for stationary objects, and typically objects that don't react to a collision by moving.

It is normal in games and such that you compute everything at set time intervals (discrete), so it might be that two objects pass through each other but you fail to notice because they moved so fast. Many games actually don't even evaluate collisions in strict chronological order. They have a spatial index for stationary objects e.g. walls, and lists for all the moving objects that they check exhaustively (although with relaxed discrete checks as I outlined).

Accurate continuous collision detection and where the objects react to collisions in simulations is usually much more demanding.

The pairs approach you outlined sounds promising. You might keep the pairs sorted by next collision, and reinsert them when they have collided in the appropriate new positions. You only have to sort the new generated collision list (O(n lg n)) for the two objects and then to merge two lists (the new collisions for each object, and the existing list of collisions; inserting the new collisions, removing those stale collisions that listed the two objects that collided) which is O(n).

Another solution to this is to adapt your spatial index to store the objects not strictly in one sector but in each that it has passed through since the last calculation, and do things discretely. This means storing fast moving objects in your spatial structure, and you'd need to optimise it for this case.

Remember that linked lists or lists of pointers are very bad for caching on modern processors. I'd advocate that you store copies of your circles - their important properties for collision detection at any rate - in an array (sequential memory) in each sector of any spatial index, or in the pairs you outlined above.

As Mark says in the comments, it could be quite simple to parallelise the calculations.