How can I set a minimum distance constraint for generating points with numpy.random.rand?

Based on @Samir 's answer, and make it a callable function for your convenience :)

import numpy as npimport matplotlib.pyplot as pltdef generate_points_with_min_distance(n, shape, min_dist):    # compute grid shape based on number of points    width_ratio = shape[1] / shape[0]    num_y = np.int32(np.sqrt(n / width_ratio)) + 1    num_x = np.int32(n / num_y) + 1    # create regularly spaced neurons    x = np.linspace(0., shape[1]-1, num_x, dtype=np.float32)    y = np.linspace(0., shape[0]-1, num_y, dtype=np.float32)    coords = np.stack(np.meshgrid(x, y), -1).reshape(-1,2)    # compute spacing    init_dist = np.min((x[1]-x[0], y[1]-y[0]))    # perturb points    max_movement = (init_dist - min_dist)/2    noise = np.random.uniform(low=-max_movement,                                high=max_movement,                                size=(len(coords), 2))    coords += noise    return coordscoords = generate_points_with_min_distance(n=8, shape=(2448,2448), min_dist=256)# plotplt.figure(figsize=(10,10))plt.scatter(coords[:,0], coords[:,1], s=3)plt.show()

Here is a scalable O(n) solution using numpy. It works by initially specifying an equidistant grid of points and then perturbing the points by some amount keeping the distance between the points at most min_dist.

You'll want to tweak the number of points, box shape and perturbation sensitivity to get the min_dist you want.

Note: If you fix the size of a box and specify a minimum distance between every point, it makes sense that there will be a limit to the number of points you can draw satisfying the minimum distance.

import numpy as npimport matplotlib.pyplot as plt# specify paramsn = 500shape = np.array([64, 64])sensitivity = 0.8 # 0 means no movement, 1 means max distance is init_dist# compute grid shape based on number of pointswidth_ratio = shape[1] / shape[0]num_y = np.int32(np.sqrt(n / width_ratio)) + 1num_x = np.int32(n / num_y) + 1# create regularly spaced neuronsx = np.linspace(0., shape[1]-1, num_x, dtype=np.float32)y = np.linspace(0., shape[0]-1, num_y, dtype=np.float32)coords = np.stack(np.meshgrid(x, y), -1).reshape(-1,2)# compute spacinginit_dist = np.min((x[1]-x[0], y[1]-y[0]))min_dist = init_dist * (1 - sensitivity)assert init_dist >= min_distprint(min_dist)# perturb pointsmax_movement = (init_dist - min_dist)/2noise = np.random.uniform(    low=-max_movement,    high=max_movement,    size=(len(coords), 2))coords += noise# plotplt.figure(figsize=(10*width_ratio,10))plt.scatter(coords[:,0], coords[:,1], s=3)plt.show()

As I understood, you're looking for an algorithm to create many random points in a box such that no two points are closer than some minimum distance. If this is your problem, then you can take advantage of statistical physics, and solve it using molecular dynamics software. Moreover, you do need molecular dynamics or Monte Carlo to obtain exact solution of this problem.

You place N atoms in a rectangular box, create a repulsive interaction of a fixed radius between them (such as shifted Lennard-Jones interaction), and run simulation for some time (untill you see that the points spread out uniformly throughout the box). By laws of statistical physics you can show that positions of the points would be maximally random given the constraint that points cannot be close than some distance. This would not be true if you use iterative algorithm, such as placing points one-by-one and rejecting them if they overlap

I would estimate a runtime of several seconds for 10000 points, and several minutes for 100k. I use OpenMM for all my moelcular dynamics simulations.