如何检查二维图形中所有点的距离并确保 None 距离太近？

Question

我想创建并 return 一组随机的 2 元素元组，代表二维图形上的点。我的问题是我希望每个点彼此之间至少有一定的距离。这应该根据下面函数中 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))

如何检查二维图形中所有点的距离并确保 None 距离太近？

How can I Check all the Points in a 2D Graph for Distance and Make Sure None are Too Close?

python

procedural-generation

python-3.x