生成多个随机(x，y)坐标，但不包括重复项? [英] Generating multiple random (x, y) coordinates, excluding duplicates?

问题描述

我想生成0到2500之间的一堆(x，y)坐标，该坐标不包含彼此之间200个点之内的点而无需递归.

I want to generate a bunch (x, y) coordinates from 0 to 2500 that excludes points that are within 200 of each other without recursion.

现在，我让它检查所有先前值的列表，以查看是否有足够远的值.这确实是低效的，如果我需要生成大量的点，那将永远耗费时间.

Right now I have it check through a list of all previous values to see if any are far enough from all the others. This is really inefficient and if I need to generate a large number of points it takes forever.

那我该怎么做呢?

推荐答案

这是汉克·迪顿(Hank Ditton)建议的一种变体，应该在时间和内存方面更有效，特别是如果您从所有可能的点中选择相对少的点点.想法是，每当生成一个新点时，会将200个单位之内的所有内容添加到一组要排除的点中，以检查所有新生成的点.

This is a variant on Hank Ditton's suggestion that should be more efficient time- and memory-wise, especially if you're selecting relatively few points out of all possible points. The idea is that, whenever a new point is generated, everything within 200 units of it is added to a set of points to exclude, against which all freshly-generated points are checked.

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

这篇关于生成多个随机(x，y)坐标，但不包括重复项?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！