Как я могу проверить все точки на двухмерном графике для расстояния и убедиться, что ни один не слишком близко? - PullRequest
Новая
       30

Как я могу проверить все точки на двухмерном графике для расстояния и убедиться, что ни один не слишком близко?

0 голосов
/ 03 мая 2018

Я хочу создать и вернуть рандомизированный набор двухэлементных кортежей, которые представляют точки на двухмерном графике. Моя проблема в том, что я хочу, чтобы каждая точка была как минимум на некотором расстоянии друг от друга. Это должно соответствовать значению параметра 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:

Ответы [ 2 ]

0 голосов
/ 04 мая 2018

Я сам придумал алгоритм.

Для каждой точки, которую я хочу получить, я добавляю все точки, необходимые для создания квадрата вокруг этой точки. Я добавляю эти точки и исходную точку к временному набору и добавляю новую точку, следя за тем, чтобы ее не было во временном наборе. Тогда я просто повторяю цикл столько раз, сколько мне нужно.

Это не самый быстрый способ сделать это, но он работает. 

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))
0 голосов
/ 03 мая 2018

Вам следует заглянуть в Quadtrees , они позволяют повысить производительность при такого рода проверках. Кроме этого, нет другого способа, кроме как проверить расстояние от каждой точки до каждой другой точки на графике.

Также убедитесь, что при сравнении точек вы не проверяете точку относительно себя.

...