计算随机圆形的位置以避免重叠的算法

Question

计算随机圆形的位置以避免重叠的算法

4

我有以下问题。

我有一个由不同大小的随机圆形组成的大区域。如果在随机位置插入一个新的半径随机的圆形，我想找到一个附近的位置，使它不会与其他任何圆形重叠。最好是圆形保持接近。

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

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

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

P.D. 一个非常好的事情，但是与我的主要目标不同的是，而且不是我的主要目标，将重新安排尽可能多的圆，而不是仅重新定位一个圆，就好像它们在“推”彼此一样。我更喜欢距离而不是移动圆的数量。也就是说，我宁愿许多圆形移动一点，而不是一个圆形远离其原始位置。

- cangrejo

3个回答

2

尝试使用动态网格，从最大的圆圈尺寸开始，然后在将其放置在最终位置后，在圆圈每个边缘上绘制线条。现在，您的网格将由许多不同大小的框组成，您只需找到一个适合新圆圈的边界框的框，放置它，然后绘制定义您现在较小的框的线条。一直进行直到放置所有圆圈。

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

- trumpetlicks

这是一个好主意。问题在于每次放置圆形时，都会应用比必要更多的限制，最终它们可能会变得过多。我将运行一些测试来查看其行为如何。谢谢。 - cangrejo

你是正确的，然而任何基于网格的算法都会变成一个近似值，因为在圆形物品周围放置一个边界框将始终留下未使用的空间。我认为基于网格的算法可能是速度最快的选择，但如果你想要精确度，甚至是最佳适配度，那么任何网格答案都可能不是最佳选择，或者至少不是第一顺位的网格答案。 - trumpetlicks

2

您的问题暗示了一种基于力导向布局算法的解决方案，需要谨慎平衡斥力和吸引力。这个答案指出了一个库，您可以使用它，我相信谷歌还会找到其他类似的库。

- High Performance Mark

这对我的目的来说是一个很好的解决方案，尽管它的复杂度（O(n^3)）有点令人望而生畏。我会查看那些库，寻找一个高效的实现。谢谢。 - cangrejo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sega_sai · Accepted Answer

我会做以下事情：定义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()

可以放置而不重叠的最小半径圆的地图

这个地图看起来像沃罗诺伊图，但是目前尚不清楚是否能利用它。

更新：经过一些思考，有一种潜在更快的解决方案适用于大量的圆。首先创建一个区域的网格（比如 2500x2500）。将所有位于圆内的像素都设置为1，其余的都设置为零。然后你需要使用所需圆的半径对该映射与圆形核进行卷积。结果地图必须在可以放置新圆的位置上有0. 这种方法的优点是它可以用于非常大的网格和圆的数量，而且可以通过fft轻松地进行卷积。

下面是一个示例，展示了第一个掩模和使用半径为128像素的圆形核卷积后的掩模。右侧掩模中所有值为0的像素都是可以放置半径为128的新圆的可能位置。