生成多个随机(x,y)坐标,不包括重复？

Question

我想生成一个从0到2500的束(x,y)坐标,它排除彼此在200之内的点而不递归.

现在我检查所有以前的值列表,看看是否有足够远的所有值.这是非常低效的,如果我需要生成大量的点,它需要永远.

那我该怎么做呢？

Answer 1

这是Hank Ditton建议的一个变体,它应该在时间和记忆方面更有效,特别是如果你从所有可能的点中选择相对较少的点.我们的想法是,每当生成一个新点时,其中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's 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

Answer 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