Создание нескольких случайных (x, y) координат, исключая дубликаты?

Ответ 1

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

import random

radius = 200
rangeX = (0, 2500)
rangeY = (0, 2500)
qty = 100  # or however many points you want

# Generate a set of all points within 200 of the origin, to be used as offsets later
# There probably a more efficient way to do this.
deltas = set()
for x in range(-radius, radius+1):
    for y in range(-radius, radius+1):
        if x*x + y*y <= radius*radius:
            deltas.add((x,y))

randPoints = []
excluded = set()
i = 0
while i<qty:
    x = random.randrange(*rangeX)
    y = random.randrange(*rangeY)
    if (x,y) in excluded: continue
    randPoints.append((x,y))
    i += 1
    excluded.update((x+dx, y+dy) for (dx,dy) in deltas)
print randPoints

Ответ 2

Я бы перерождал точки target_N < input_N и отфильтровывал их, используя KDTree. Например:

import numpy as np
from scipy.spatial import KDTree
N   = 20
pts = 2500*np.random.random((N,2))

tree = KDTree(pts)
print tree.sparse_distance_matrix(tree, 200)

Дала бы мне очки, которые "близки" друг к другу. Отсюда должно быть просто применить любой фильтр:

  (11, 0)   60.843426339
  (0, 11)   60.843426339
  (1, 3)    177.853472309
  (3, 1)    177.853472309

Ответ 3

Некоторые параметры:

• Используйте свой алгоритм, но реализуйте его с помощью kd-tree, который ускорит поиск ближайших соседей
• Создайте регулярную сетку над квадратом [0, 2500] ^ 2 и произвольно сотрясайте все точки с двумерным нормальным распределением, центрированным на каждом пересечении в сетке
• Нарисуйте большее количество случайных точек, затем примените алгоритм k-means и удерживайте только центроиды. Они будут далеко друг от друга, и алгоритм, хотя итеративный, может сходиться быстрее, чем ваш алгоритм.

Ответ 4

На это был дан ответ, но он очень касательно связан с моей работой, поэтому я принял удар. Я реализовал алгоритм, описанный в это примечание, которое я нашел связанным с this сообщение в блоге. К сожалению, это не быстрее, чем другие предлагаемые методы, но я уверен, что есть оптимизации.

import numpy as np
import matplotlib.pyplot as plt

def lonely(p,X,r):
    m = X.shape[1]
    x0,y0 = p
    x = y = np.arange(-r,r)
    x = x + x0
    y = y + y0

    u,v = np.meshgrid(x,y)

    u[u < 0] = 0
    u[u >= m] = m-1
    v[v < 0] = 0
    v[v >= m] = m-1

    return not np.any(X[u[:],v[:]] > 0)

def generate_samples(m=2500,r=200,k=30):
    # m = extent of sample domain
    # r = minimum distance between points
    # k = samples before rejection
    active_list = []

    # step 0 - initialize n-d background grid
    X = np.ones((m,m))*-1

    # step 1 - select initial sample
    x0,y0 = np.random.randint(0,m), np.random.randint(0,m)
    active_list.append((x0,y0))
    X[active_list[0]] = 1

    # step 2 - iterate over active list
    while active_list:
        i = np.random.randint(0,len(active_list))
        rad = np.random.rand(k)*r+r
        theta = np.random.rand(k)*2*np.pi

        # get a list of random candidates within [r,2r] from the active point
        candidates = np.round((rad*np.cos(theta)+active_list[i][0], rad*np.sin(theta)+active_list[i][1])).astype(np.int32).T

        # trim the list based on boundaries of the array
        candidates = [(x,y) for x,y in candidates if x >= 0 and y >= 0 and x < m and y < m]

        for p in candidates:
            if X[p] < 0 and lonely(p,X,r):
                X[p] = 1
                active_list.append(p)
                break
        else:
            del active_list[i]

    return X

X = generate_samples(2500, 200, 10)
s = np.where(X>0)
plt.plot(s[0],s[1],'.')

И результаты:

Ответ 5

По ссылке, метод от aganders3 известен как выборка диска Пуассона. Возможно, вам удастся найти более эффективные реализации, использующие локальный сеточный поиск, чтобы найти "перекрытия". Например, отбор проб Пуассона. Поскольку вы ограничиваете систему, она не может быть полностью случайной. Максимальная упаковка для кругов с одинаковыми радиусами в плоскости составляет ~ 90% и достигается, когда круги расположены в идеальном гексагональном массиве. По мере того, как количество запрашиваемых вами точек приближается к теоретическому пределу, сгенерированное расположение станет более шестиугольным. По моему опыту, при таком подходе сложно получить упаковку с однородными кругами выше ~ 60%.