Algorithm for calculating the positions of random circles so that they do not overlap

Question

I have the following problem.

I have a large region filled with a random number of circles of different sizes. If a new circle of random radius is inserted in a random place, I would like to find the closest position for it so that it does not intersect with any of the others. Optimal if the circles remain closed.

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

The easiest approach is to detect collisions when placing a new circle and moving it away from the circle that it collides with. After that, check for conflicts and repeat the process. This is obviously not very elegant, and it is subject to endless cycles (more often than you might think).

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

PD
A very nice thing, but another question, and not my main goal, would be to rearrange as many circles as necessary, instead of moving only one, as if they were "pushing" each other. I would prefer a distance over the number of circles moved. That is, I would prefer that many circles move a little than one circle to move very far from its original position.

Answer 1

I would do the following: define a grid x, y and for the grid calculate the minimum distance to all circles minus the radius to the circle. On the resulting map, you can select any pixel that is brighter than X, which means that you can place a circle with a radius of X there without overlapping. Here is the code and image displaying the final map. If you want to do 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() 

How the map looks like a voronoi diagram, but it is unclear whether it can be used.

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

Here is an illustration showing the first mask and the mask after convolution with a circular core with a radius of 128 pixels. All zero pixels in the right mask are the possible locations of a new circle with a radius of 128.

Answer 2

Try a dynamic grid in which you start with the largest circle size, and then draw lines on each edge of the circle after you place it at its final location. Now your grid will be made up of many different sizes, all you have to do is find the window that will fit the frame of your new circle, place it, and then draw the lines that define your smaller fields now. Keep moving until you place all your circles.

You can always put circles in an angular position in a square area, so that when drawing lines, you should first draw only two lines, the second you always save maximum space after placement.

Answer 3

Your question proposes a solution based on a power layout algorithm with a reasonable balance of repulsive and attractive forces. This answer points to a library that you can use, Google will find for you others that I expect.