算法来计算随机圈的位置，以便它们不重叠 [英] Algorithm to calculate the positions of random circles so they don't overlap

问题描述

我有以下问题。

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

I have a large region populated with a random number of circles of different sizes. If a new circle of random radius is inserted in a random location, I'd like to find a nearby position for it so it doesn't overlap with any of the others. It's optimal if the circles stay close.

回路的数目和它们的大小是有限的，但随机的。该地区将是相当大的，（2500x2500，也许）这样的像素阵列作为建议<一href="http://stackoverflow.com/questions/6002407/placing-random-circles-without-overlap-and-without-using-brute-force">here是出了问题。谁回答同样的问题提出了一个网格的人，其中的细胞是圆的大小。这将解决我的问题，利用细胞可能的最大圆的大小，但我想的圆圈以保持尽可能接近，所以它不能完全满足我的需求。

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

有一个非常基本的方法包括检测对新圈放置碰撞，并从它与碰撞的圆圈移动它了。在此之后，检查碰撞再次重复这个过程。这显然​​不是很优雅，很容易产生无限循环（往往比你想象的）。

A very basic approach consists of detecting collisions on placement of the new circle, and moving it away from the circle it collides with. After that, check for collisions again and repeat the process. This is obviously not very elegant and it's prone to infinite loops (more often than you might think).

Pd积。
一个非常好的事情，但不同的事，而不是我的主要目的，是要重新安排尽可能多的圈，因为它是不是搬迁只是一个必要的，仿佛他们是'推'对方。我赞成距离在移动圈数。也就是说，我想preFER许多圈子移动不是一个圆圈一点移动很远的距离原来的位置。

P.D.
A very nice thing, but a different matter, and not my main objective, would be to rearrange as many circles as it's necessary, instead of relocating just the one, as though they were 'pushing' each other. I'd favor distance over number of circles moved. That is, I'd prefer many circles to move a little than one circle to move very far away from its original position.

推荐答案

我要做到以下几点：确定X，Y的网格 和为网格，计算到所有的圆圈的半径的最小距离减去到圆。 在出现的地图，你可以选择是光明的，那么X，这意味着你可以将装有半径X有一个圆不重叠的任何像素。 这里是code和图像显示生成的地图。 如果你想让它快，你可以​​使用地图的分辨率较低的版本。

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

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

The way the map looks like the voronoi diagram but it is unclear whether that can be exploited.

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

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

下面是图示示出了第一掩模，并与圆形的内核与128像素半径的卷积后的掩模。在右边的面具所有零像素新圆128的半径可能的位置。

Here is the illustration showing the first mask, and the mask after the convolution with the circular kernel with radius of 128 pixels. All zero pixels in the right mask are possible location of the new circle with the radius of 128.

这篇关于算法来计算随机圈的位置，以便它们不重叠的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！