Fast Collision Detection for Circle Insertion into 2D Plane

Question

Hello all.

I know there are lots of posts about collision detection generally for sprites moving about a 2D plane, but my question is slightly different.

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.

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.

Note: safeDistance is the radius of the circle I want to add to the plane.

Here's the 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 > 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 < (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;
}

Answer 1

Honestly, with only 20-25 circles, you're not going to get much of a speed boost by using a fancier algorithm or data structure (e.g. a quadtree or a kd-tree). Everything is fast for small n.

Are you absolutely sure this is the bottleneck in your application? Have you profiled? If yes, then the way you're going to speed this up is through microoptimization, not through advanced algorithms. Are you making lots of iterations through the while loop because most of the plane is unsafe?

Answer 2

You could split your plane in lots of little rectangles (slightly quadtree-related) and save which rectangles are hit by at least one of the circles. When you look for a insertion-point, you'll just have to look for some "empty" ones (which doesn't need any random jumps and is possible in constant time).

The number and constellation of rectangles can be computed by the radius.

Answer 3

Subdivide your window into w by h blocks. You'll be maintaining a w by h array, dist. dist[x][y] contains the size of the largest circle that can be centred at (x, y). (You can use pixels as blocks, although we'll be updating the entire array with each circle placed, so you may want to choose larger blocks for improved speed, at the cost of slightly reduced packing densities.)

Initialisation

Initially, set all dist[x][y] to min(x, y, w - x, h - y). This encodes the limits given by the bounding box that is the window.

Update procedure

Every time you add a circle to the window, say one positioned at (a, b) with radius r, you need to update all elements of dist.

The update required for each position (x, y) is:

dist[x][y] = min(dist[x][y], sqrt((x - a)^2 + (y - b)^2) - r);

(Obviously, ^2 here means squaring, not XOR.) Basically, we are saying: "Set dist[x][y] to the minimum distance to the circle just placed, unless the situation is already worse than that." dist values for points inside the circle just placed will be negative, but that doesn't matter.

Finding the next location

Then, when you want to insert the next circle of radius q, just scan through dist looking for a location with dist value >= q. (If you want to randomly choose such a location, find the complete list of valid locations and then randomly choose one.)

Answer 4

Just an outline, since this solution is fairly involved.

If you want to guarantee you always find a place to put a circle if it's possible, you can do the following. Consider each existing circle C. We will try to find a location where we can place the new circle so that it is touching C. For each circle D (other than C) that is sufficiently close to C, there will be a range of angles where placing a new circle at one of those angles around C will make it intersect with D. Some geometry will give you that range. Similarly, for each of the four boundaries that are close enough to C, there will be a range of angles where placing a new circle at one of those angles will make it intersect with the boundary. If all these intervals cover all 360 degrees around C, then you cannot place a circle adjacent to C, and you will have to try the next circle, until there are no more candidates for C. If you find a place to put the new circle, you can move it some random distance away from C so that all your new circles do not have to be adjacent to an existing circle if that is not necessary.