如何检查 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，它们在这种检查中可以提供更好的性能。 除此之外，除了检查图表中每个点到每个其他点的距离外，别无他法。

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

Answer 2

我自己想出了一个算法。

对于我想要的每个点，我添加所有必要的点，以在所述点周围制作一个正方形。我将这些点和原始点添加到临时集合中，并添加一个新点，同时确保它不在临时集合中。然后我只是循环我需要多少次。

这不是最快的方法，但它有效。

def makeTiles():
"""
Creates and returns a set of points.
Preconditions:
There is enough space within the area defined by xBounds and yBounds.
Algorithm:
1    Create a random point.
2    Add the point to tileSet and distanceSet.
3    Add all points within minDistance to distanceSet.
4    Create another random point.
5    while this point is in distanceSet.
6        Change the location of the point.
7    Add the point to tileSet and distanceSet.
8    Add all points within minDistance to distanceSet.
9    Continue looping from line 4 for num amount of times.
:return: set of tuples
The set of points that will be created.
"""
tileSet = set()
distanceSet = set()
x = r.randint(KEEP_X[0], KEEP_X[1])
y = r.randint(KEEP_Y[0], KEEP_Y[1])
tileSet.add((x, y))
for t in tileSet:
distanceSet.add((t[0], t[1]))
for m1 in range(1, KEEP_DIST):
for m2 in range(1, KEEP_DIST):
distanceSet.add((x + m2, y + m1))
distanceSet.add((x - m2, y - m1))
distanceSet.add((x + m2, y - m1))
distanceSet.add((x - m2, y + m1))
distanceSet.add((x, y + m1))
distanceSet.add((x, y - m1))
distanceSet.add((x - m2, y))
distanceSet.add((x + m2, y))
for n in range(KEEP_NUM):
x = r.randint(KEEP_X[0], KEEP_X[1])
y = r.randint(KEEP_Y[0], KEEP_Y[1])
while (x, y) in distanceSet:
x = r.randint(KEEP_X[0], KEEP_X[1])
y = r.randint(KEEP_Y[0], KEEP_Y[1])
print("(x, y)", (x, y))
tileSet.add((x, y))
distanceSet.add((x, y))
for m1 in range(1, KEEP_DIST):
for m2 in range(1, KEEP_DIST):
distanceSet.add((x + m2, y + m1))
distanceSet.add((x - m2, y - m1))
distanceSet.add((x + m2, y - m1))
distanceSet.add((x - m2, y + m1))
distanceSet.add((x, y + m1))
distanceSet.add((x, y - m1))
distanceSet.add((x - m2, y))
distanceSet.add((x + m2, y))