Fast Collision Detection for Circle Insertion into 2D Plane

Question

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

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 2

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?