计算随机圆的位置的算法,使它们不重叠

Question

我有以下问题.

我有一个大的区域,填充了随机数量的不同大小的圆圈.如果在随机位置插入一个新的随机半径圆,我想为它找到一个附近的位置,这样它就不会与任何其他位置重叠.如果圆圈靠近,这是最佳的.

圆圈的数量及其大小是有限的,但是随机的.该区域将非常大(可能是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的新圆的可能位置.