4

我有以下问题。

我有一个很大的区域，里面有随机数量的不同大小的圆圈。如果在随机位置插入一个随机半径的新圆，我想为它找到一个附近的位置，这样它就不会与其他任何位置重叠。如果圆圈保持接近，这是最佳选择。

圆圈的数量和大小是有限的，但随机的。该区域将非常大（可能是 2500x2500），因此这里提出的像素数组是不可能的。回答相同问题的人提出了一个网格，其中的单元格是圆圈的大小。这将解决我的问题，使用最大可能圆圈大小的单元格，但我希望圆圈尽可能靠近，所以它不能完全满足我的需求。

一种非常基本的方法包括检测新圆放置时的碰撞，并将其从与之碰撞的圆移开。之后，再次检查碰撞并重复该过程。这显然不是很优雅，而且很容易出现无限循环（比你想象的更频繁）。

目标是为新插入的圆找到最近的可能位置，使其不与其他任何人重叠。

PD
一件非常好的事情，但不同的事情，而不是我的主要目标，是根据需要重新排列尽可能多的圆圈，而不是仅仅重新定位一个，就好像它们在相互“推动”一样。我更喜欢距离而不是移动的圈数。也就是说，我宁愿很多圈子移动一点，而不是一个圈子远离它的原始位置。

4

3 回答 3

5

我会做以下事情：定义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 填充。然后，您需要将此地图与圆形内核与您要放置的圆的所需半径进行卷积。生成的地图的像素必须为 0，可用于放置像素。这种方法的优点是可以适用于非常大的网格和圈数，并且卷积可以通过fft轻松完成。

这是显示第一个掩码的插图，以及与半径为 128 像素的圆形内核卷积后的掩码。右掩码中的所有零像素都是半径为 128 的新圆的可能位置。

面具

于 2012-06-13T01:29:21.063 回答
2

您的问题提出了一种基于力的布局算法的解决方案，该算法在排斥力和吸引力之间取得了明智的平衡。 这个答案指向您可能使用的图书馆，我希望谷歌会为您找到其他人。

于 2012-06-13T15:51:18.367 回答
2

尝试动态网格，从最大的圆圈开始，然后在将圆圈放置到最终位置后在圆圈的每个边缘上画线。现在您的网格将由许多不同大小的框组成，您所要做的就是找到一个适合您的新圆的边界框的框，放置它，然后绘制定义您现在更小的框的线条。继续，直到你放置了所有的圈子。

您始终可以在正方形区域内的角落位置放置圆圈，这样当您绘制线条时，首先您只需绘制 2 条线，其次您将始终在放置后保持最大空间打开。

于 2012-06-12T23:02:42.380 回答