title: Collision detection of huge number of circles
body: <p>What is the best way to check collision of huge number of circles?<br>
  It's very easy to detect collision between two circles, but if we check every combination then it is <strong>O(n<sup>2</sup>)</strong> which definitely not an optimal solution.  </p>
  
  <p>We can assume that circle object has following properties:</p>
  
  <ul>
  <li>Coordinates  </li>
  <li>Radius  </li>
  <li>Velocity  </li>
  <li>Direction</li>
  </ul>
  
  <p>Velocity is constant, but direction can change.</p>
  
  <p>I've come up with two solutions, but maybe there are some better solutions.  </p>
  
  <p><strong>Solution 1</strong><br>
  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.</p>
  
  <p><strong>Solution 2</strong><br>
  At the beginning distances between every pair of circles need to be calculated.<br>
  If the distance is small then these pair is stored in some list, and we need to check for collision in every update.<br>
  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.</p>
  
  <p><strong>Answers to Mark Byers questions</strong>  </p>
  
  <ol>
  <li><em>Is it for a game?</em><br>
  It's for simulation, but it can be treated also as a game  </li>
  <li><em>Do you want to recalculate the new position every n milliseconds, and also check for collisions at this time?</em><br>
  Yes, time between update is constant.  </li>
  <li><em>Do you want to find the time at which the first/every collision occurs?</em><br>
  No, I want to find every collision and do 'something' when it occures.  </li>
  <li><em>How important is accuracy?</em><br>
  It depends on what do you mean by accuracy. I need to detect all collisions.  </li>
  <li><em>Is it a big problem if very small fast moving circles can pass through each other occasionally?</em><br>
  It can be assumed that speed is so small that it won't happen.</li>
  </ol>