python - 如何检查 2D 图表中所有点的距离并确保没有点太近？

Question

我想创建并返回一组随机的 2 元素元组，这些元组代表 2D 图上的点。我的问题是我希望每个点彼此之间至少有一定的距离。这应该根据下面函数中 minDistance 参数的值。

我想不出一种方法来遍历一组并检查每个点的距离，同时替换距离不够远的点。我怎样才能做到这一点？

注意:该图的长度为 90 点，宽度为 160 点。

这是迄今为止我的功能:

def makeTiles(num, xBounds, yBounds, minDistance):
"""
Creates and returns a set of points.

:param num: int
    The number of points to be returned.
:param xBounds: tuple of 2 ints
    The first element is the minimum an x-value should be.
    The second element is the maximum an x-value should be.
:param yBounds: tuple of 2 ints
    The first element is the minimum an y-value should be.
    The second element is the maximum an y-value should be.
:param minDistance: int
    The minimum distance that should occur between points.
:return: set of tuples
    The set of points that will be created.
"""
tileSet = set()

for n in range(num):
    x = r.randint(xBounds[0], xBounds[1])
    y = r.randint(yBounds[0], yBounds[1])
    tileSet.add((x, y))

tempSet = tileSet.copy()
distances = set()
for t1 in tempSet:
    for t2 in tileSet:
        distances.add(m.sqrt((t1[0] - t2[0]) ** 2 + (t1[1] - t2[1]) ** 2))
        for d in distances:
            if d < minDistance:

Answer 1

您应该查看Quadtrees ，它们可以在这种检查中获得更好的性能。 除此之外，除了检查图表中每个点到其他点的距离之外，没有其他办法。

还要确保在比较点时，不要对照点本身进行检查。