Generating multiple random (x, y) coordinates, excluding duplicates?

Question

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.

So how would I go about doing this?

Answer 1

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 

Answer 2

I would overgenerate the points, target_N < input_N, and filter them using a KDTree. For example:

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) 

Would give me points that are "close" to each other. From here it should be simple to apply any filter:

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