title: Fast Collision Detection for Circle Insertion into 2D Plane
body: <p>I know there are lots of posts about collision detection generally for sprites moving about a 2D plane, but my question is slightly different.</p>
  
  <p>I'm inserting circles into a 2D plane.  The circles have variable radii.  I'm trying to optimize my method of finding a random position within the plane where I can insert a new circle without it colliding with any other circles already on the plane.  Right now I'm using a very "un-optimized" approach that simply generates a random point within the plane and then checks it against all the other circles on the plane.</p>
  
  <p>Are there ways to optimize this?  For this particular app, the bounds of the plane can only hold 20-25 circles at a time and typically there are between 5-10 present.  As you would expect, when the number of circles approaches the max that can fit, you have to test many points before finding one that works.  It gets very slow.</p>
  
  <p>Note: safeDistance is the radius of the circle I want to add to the plane.</p>
  
  <p>Here's the code:</p>
  
  <pre><code>- (CGPoint)getSafePosition:(float)safeDistance {
  // Point must be far enough from edges
  // Point must be far enough from other sprites
  
  CGPoint thePoint;
  BOOL pointIsSafe = NO;
  
  int sd = ceil(safeDistance);
  
  while(!pointIsSafe) {
  
      self.pointsTested++; // DEBUG
  
      // generate a random point inside the plane boundaries to test
      thePoint = CGPointMake((arc4random() % ((int)self.manager.gameView.frame.size.width - sd*2)) + sd, 
                             (arc4random() % ((int)self.manager.gameView.frame.size.height - sd*2)) + sd);
  
      if(self.manager.gameView.sprites.count &gt; 0) {
          for(BasicSprite *theSprite in self.manager.gameView.sprites) {
  
              // get distance between test point and the sprite position
              float distance = [BasicSprite distanceBetweenPoints:thePoint b:theSprite.position];
  
              // check if distance is less than the sum of the min safe distances of the two entities
              if(distance &lt; (safeDistance + [theSprite minSafeDistance])) {
                  // point not safe
                  pointIsSafe = NO;
                  break;
              }
  
              // if we get here, the point did not collide with the last tested point
              pointIsSafe = YES;
          }
      }
      else {
          pointIsSafe = YES;
      }
  }
  
  return thePoint;
  }
  </code></pre>