生成不在彼此范围内的点？

Question

我正在尝试在一个固定的区域内生成一组点，这些点之间不能重叠。我的方法如下：

import collections
from random import uniform

X = 100.0
Y = 100.0
points = 10
radius = 10

def in_circle(c_x, c_y, radius, x, y):
    dist_squared = (c_x - x)**2 + (c_y - y)**2
    return dist_squared <= radius ** 2

current = collections.defaultdict(lambda: [])

threshold = 0    

for point in range(1, points+1):
    cX = uniform(1.0, X)
    cY = uniform(1.0, Y)

    for cur in current:
        while in_circle(current[cur][0], current[cur][1], 2*radius, cX, cY):
          cX = uniform(1.0, X)
          cY = uniform(1.0, X)

          threshold += 1
          if threshold >= 1e+05:
              print "Cannot satisfy constraints"
              sys.exit(1)

    threshold = 0

    current[point] = [cX, cY]
    print cX, cY

有没有好的方法可以结束这个算法，避免它进入无限循环？我确实有一个阈值检查，但有没有更好的方法呢？

Answer 1

这类问题被称为圆形排列。在mathworld的文章中提到，对于单位正方形，已知的最密集的排列方式是有研究的（而且这个问题可以通过缩放x和y来转化为那个问题）。文章中的图片展示了两种密集的球体排列方式（方形和六边形）。

至于你能否插入一个新的圆，一个沃罗诺伊图可能会有帮助，因为它可以用来衡量剩余未被占用的最大区域。其他一些评估空闲区域的近似方法，比如四叉树或空间哈希，在某些情况下也可能足够用。

Answer 2

你可以把这个区域分成一些边长大于等于点之间最小允许距离的正方形，然后随机选择其中的一些正方形吗？

比如说，这些就是你用来包围点的正方形，编号从0到j：

0 1 2 3 4
5 6 7 8 9
a b c d e
f g h i j

接着你可以创建一个正方形索引的数组（在这个例子中是从0到j），然后随机打乱这个数组，最后得到一个像bc4j25e1670dfgh89ai3这样的字符串，然后从这个字符串的开头取出你需要的点的数量，比如5个：bc4j2。然后你就可以把这些点放在选中正方形的中心（或者左上角）的位置：

0 1 * 3 *
5 6 7 8 9
a * * d e
f g h i *

Answer 3

这篇文章讲的是泊松圆盘采样，可能会对你有帮助。作者介绍了一种选择点的方法，这些点之间不会太近，并且还提供了几种编程语言的示例代码，包括Python。

你提到的策略有个问题，就是如果你想选择很多点，或者想让这些点之间的距离比较远，性能可能会变得非常糟糕。我认为，泊松圆盘方案在性能上表现得更好。