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(n2) which definitely not an optimal solution.
We can assume that circle object has following properties:
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
I assume you are doing simple hard-sphere molecular dynamic simulation, right? I came accros the same problem many times in Monte Carlo and molecular dynamic simulations. Both of your solutions are very often mentioned in literature about simulations. Personaly I prefer solution 1, but slightly modified.
Solution 1
Divide your space into rectangular cells that don't overlap. So when you check one circle for collision you look for all circles inside a cell that your first circle is, and look X cells in each direction around. I've tried many values of X and found that X=1 is the fastest solution. So you have to divide space into cells size in each direction equal to:
Divisor = SimulationBoxSize / MaximumCircleDiameter;
CellSize = SimulationBoxSize / Divisor;
Divisor should be bigger than 3, otherwise it will cause errors (if it is too small, you should enlarge your simulation box).
Then your algorithm will look like this:
If you will write it correctly then you would have something about O(N) complexity, because maximum number of circles inside 9 cells (in 2D) or 27 cells (in 3D) is constant for any total number of circles.
Solution 2
Ususaly this is done like this:
R < R_max
, calculate time after which we should update lists (something about T_update = R_max / V_max
; where V_max is maximum current velocity)T_update
, go to 1.This solution with lists is very often improved by adding another list with R_max_2 > R_max
and with its own T_2
expiration time. In this solution this second list is used to update the first list. Of course after T_2
you have to update all lists which is O(N^2). Also be carefull with this T
and T_2
times, because if collision can change velocity then those times would change. Also if you introduce some foreces to your system, then it will also cause velocity change.
Solution 1+2 You can use lists for collision detection and cells for updating lists. In one book it was written that this is the best solution, but I think that if you create small cells (like in my example) then solution 1 is better. But it is my opinion.
Other stuff
You can also do other things to improve speed of simulation:
r = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + ...)
you don't have to do square root operation. You can compare r^2
to some value - it's ok. Also you don't have to do all (x1-x2)*(x1-x2)
operations (I mean, for all dimentions), because if x*x
is bigger than some r_collision^2
then all other y*y
and so on, summed up, would be bigger.For hard-spheres there is also effective algorithm that doesn't do steps in time, but instead it looks for nearest collision in time and jumps to this time and updates all positions. It can be good for not dense systems where collisions are not very probable.