Algorithm to calculate the positions of random circles so they don't overlap

Question

I have the following problem.

I have a large region populated with a random number of circles of different sizes. If a new circle of random radius is inserted in a random location, I'd like to find a nearby position for it so it doesn't overlap with any of the others. It's optimal if the circles stay close.

The number of circles and their size are limited, but random. The region will be quite large, (2500x2500, maybe) so an array of pixels as proposed here is out of the question. A person who answered that same question proposed a grid, in which the cells are the size of the circles. That would solve my problem, using cells the size of the largest possible circle, but I would like the circles to remain as close as possible, so it wouldn't entirely satisfy my needs.

A very basic approach consists of detecting collisions on placement of the new circle, and moving it away from the circle it collides with. After that, check for collisions again and repeat the process. This is obviously not very elegant and it's prone to infinite loops (more often than you might think).

The goal is to find the closest possible position for the newly inserted circle so it does not overlap with anyone else.

P.D.
A very nice thing, but a different matter, and not my main objective, would be to rearrange as many circles as it's necessary, instead of relocating just the one, as though they were 'pushing' each other. I'd favor distance over number of circles moved. That is, I'd prefer many circles to move a little than one circle to move very far away from its original position.

Answer 1

I would do the following: define the grid of x,y and for the grid, compute the minimum distance to all the circles minus radius to the circle. On the resulting map, you can select any pixel which is brighter then X which means that you could place a circle with radius X there without overlap. Here is the code and an image showing the resulting map. If you want to make it faster, you can use a lower resolution version of the map.

import numpy as np,numpy.random
import matplotlib.pyplot as plt,matplotlib,scipy.optimize

maxx=2500
maxy=2500
maxrad=60 #max radius of the circle
ncirc=100 # number of circles
np.random.seed(1)

#define centers of circles
xc,yc=np.random.uniform(0,maxx,ncirc),np.random.uniform(0,maxy,ncirc)
rads=np.random.uniform(0,maxrad,ncirc)
#define circle radii

xgrid,ygrid=np.mgrid[0:maxx,0:maxy]
im=xgrid*0+np.inf

for i in range(ncirc):
    im = np.minimum(im, ((xgrid - xc[i])**2 + (ygrid - yc[i])**2)**.5 - rads[i])
# im now stores the minimum radii of the circles which can 
# be placed at a given position without overlap

#plotting 
fig=plt.figure(1)
plt.clf()
plt.imshow(im.T,extent=(0, maxx, 0, maxy))
plt.colorbar()
ax = plt.gca()
for i in range(ncirc):
     ax.add_patch(matplotlib.patches.Circle((xc[i], yc[i]), rads[i],
          facecolor='none', edgecolor='red'))
plt.xlim(0, maxx)
plt.ylim(0, maxy)
plt.draw()

The way the map looks like the voronoi diagram but it is unclear whether that can be exploited.

Update: After some thought there is a potentially faster solution which would work for large number of circles. First create grid of the area (say 2500x2500). Fill all the pixels which are inside the circles by 1, Everything else with zero. Then you need to convolve this map with the circular kernel with the required radius of the circle which you want to place. The resulting map must have 0 at the pixels which can be used for placing of the pixels. The advantage of this method is that it can work for very large grids and number of circles, and the convolution can be easily done by fft.

Here is the illustration showing the first mask, and the mask after the convolution with the circular kernel with radius of 128 pixels. All zero pixels in the right mask are possible location of the new circle with the radius of 128.