How do I create random non-overlapping coordinates?

Question

I am trying to create a function that will generate a vec of length n, with random x and y coordinates of type f64 between some boundary (-b, b). Every point with such coordinate must have a minimum distance d from each other. I am trying to use the thread_rng() function, but I am stuck. Should I use a specific distribution or add some filter or condition to achieve that?

extern crate rand; // 0.5.5

use rand::prelude::*;
use rand::distributions::Standard;

pub fn apply_random_pos(n: usize, min_distance: f64) -> Vec<(f64, f64)> {
    let mut rng = thread_rng();
    let mut x: f64;
    let mut y: f64;

    let mut positions: Vec<(f64, f64)> = Vec::with_capacity(n);

    positions = thread_rng()
        .sample_iter(&Standard)
        .take(n)
        .collect::<Vec<(f64, f64)>>();

    positions
}

Answer 1

Sketch of algorithm for larger number of points (but distribution is tied to grid):

Build square grid on your region. Choose cell Size = 3*MinDist. So you have (Width * Height) / (9 * MinDist^2) point sites.

When you add new point, choose random free site and place point in grid knot, then change its position randomly in range -Mindist..MinDist in both directions. Cell size 3 guarantees that no points lie too close.

Example of generation: half of sites are occupied at the left picture, all sites are occupied at the right one

To achieve better "random look", you can make cell size smaller - for instance, 2*MinDist, but in this case you have to check neighbor sites - but only four of them rather than all.