算法来计算随机圈的位置，以便它们不重叠(Algorithm to calculate the pos

我有以下问题。

我有填充不同大小的圆圈的随机数大的区域。如果随机半径的新圈子插入一个随机位置，我想为它找一个附近的位置，所以它不与任何其他的重叠。这是最佳的，如果圆圈贴近。

圈的数量和它们的大小是有限的，但随机的。该区域将是相当大的，（2500x2500，也许），从而提出像素阵列这里是出了问题。谁回答同样的问题提出了格的人，其中细胞是圆的大小。这将解决我的问题，使用细胞可能的最大圆的大小，但我想圆圈保持尽可能接近，所以它不能完全满足我的需求。

一个非常基本的方法由对新圆的设置检测碰撞，并从它与碰撞的圆移动它扔掉。在此之后，再次检查冲突，并重复上述过程。这显然不是很优雅，它（往往比你想象的）是容易出现无限循环。

我们的目标是要找到新插入圈最接近的可能位置，因此它不会与其他人重叠。

PD
一个非常好的事情，但不同的事，而不是我的主要目的，是要重新安排尽可能多的圈，因为它是必要的，而不是重新定位只有一个，好像他们是“推”对方。我偏向于移动圈数距离。也就是说，我宁愿多圈动了一下不是一个圆周运动非常远离原来的位置。

Answer 1:

我会做到以下几点：确定X，Y的网格，网格，计算到各界减去最小距离半径的圆圈。在出现的地图，你可以选择是光明的，那么X，这意味着你可以将半径X有一个圆圈重叠没有任何像素。下面是代码和表示生成的地图图像。如果你想更快，你可以使用地图的较低分辨率版本。

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()

该方式在地图看起来像Voronoi图，但目前还不清楚是否可以被利用。

更新：经过一番思考是有可能更快的解决方案，将为众多圈子的工作。首先创建区域的网格（说2500x2500）。填写这是圈内1的所有像素，其他的一切为零。然后，你需要这个卷积地图与您要放置圆的半径要求的圆形内核。将得到的映射必须在其可以用于像素的放置的像素具有0。这种方法的优点是，它可以非常大电网和圈数工作，卷积可以通过FFT可以轻松完成。

这里是表示第一掩码的示意图，并用具有128个像素的半径圆形内核的卷积后的掩模。在右掩模所有零个像素与128的半径新圈子的可能位置。