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
}

Hum, it looks more like an [tag:algorithm] problem than a [tag:rust] one. — Boiethios, Sep 21 '18 at 09:50
You have a bunch of unused stuff in your code sample, and all your type anotations are useless. In idiomatic Rust, you should add them only if they are required. In fact, your whole function can be written with one line: `thread_rng().sample_iter(&Standard).take(n).collect()`. — Boiethios, Sep 21 '18 at 10:10
Are you sure you don't want some sort of domain for `x, y`? 'A random `f64`' is a HUGE domain. — orlp, Sep 21 '18 at 10:49
@orlp I guess I could bound `x` and `y` between two values, lets say `-10.0, 10.0` . — Craftrac, Sep 21 '18 at 11:43
n points. It could be from some hundreds to up to some millions — Craftrac, Sep 21 '18 at 12:18
Try-and-check-all method is quadratic and becomes unreliable for million points. Perhaps you'll have to consider kd-tree in the future — MBo, Sep 21 '18 at 12:31
I'd be tempted to find myself a physics engine that can simulate charged particles, create `n` particles with random (within a range) charges all of the same sign, and get the engine to find their steady state in a suitably sized box. — AakashM, Sep 21 '18 at 14:36
Also https://mathematica.stackexchange.com/questions/2594. Also https://stackoverflow.com/questions/8930796, but that asker wants to additionally have a maximum distance, and does *not* want any randomness. Also https://stackoverflow.com/questions/47041784. And that's me done. — AakashM, Sep 21 '18 at 14:43

MBo · Answer 1 · 2018-09-21T14:15:52.547

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.

That is a really interesting approach! I will try to implement it soon — Craftrac, Sep 21 '18 at 16:09

Boiethios · Answer 2 · 2018-09-21T12:31:53.050

3

You can use a naive algorithm: while the generated point is not ok, try with another one:

extern crate rand;
use rand::prelude::*;

pub fn apply_random_pos(n: usize, min_distance: f64, boundary: f64) -> Vec<(f64, f64)> {
    fn distance(p1: (f64, f64), p2: (f64, f64)) -> f64 {
        ((p1.0 - p2.0).powf(2.) + (p1.1 - p2.1).powf(2.)).sqrt()
    }

    let mut rng = thread_rng();
    let mut positions = Vec::with_capacity(n);

    while positions.len() < n {
        let p1 = (
            rng.gen_range(boundary, -boundary),
            rng.gen_range(boundary, -boundary),
        );
        if positions.iter().all(|&p2| distance(p1, p2) > min_distance) {
            positions.push(p1);
        }
    }
    positions
}

Note that this algorithm is not suitable at all for a great number of points. It is even the worst possible algorithm.

edited Sep 21 '18 at 12:31

answered Sep 21 '18 at 10:09

Boiethios

38,438
19
134
183

It is a good approximation but I have to modify it because it ends in infinite loop – Craftrac Sep 21 '18 at 12:11
2

@Moreorem `gen` will generate a number between 0 and 1. Your distance should be in this range. You must likely add a check in your function to see if the request is possible (*e.g.* 10 points with a minimum distance of 0.9 is impossible for example). – Boiethios Sep 21 '18 at 12:14
True. A check will indeed be necessary – Craftrac Sep 21 '18 at 12:34

score 0 · Answer 3 · edited Sep 21 '18 at 13:37

I used @Boiethios' answer with some additions and it seems to work as I want. The only minor problem is that I haven't thought of a way to output a more specific range that contains negatives as well

pub fn apply_random_pos(n: usize, min_distance: f64) -> Vec<(f64, f64)> {
    fn distance(p1: (f64, f64), p2: (f64, f64)) -> f64 {
        ((p1.0 - p2.0).powf(2.) + (p1.1 - p2.1).powf(2.)).sqrt()
    }
    let mut rng = thread_rng();
    let mut positions = Vec::with_capacity(n);

    while positions.len() < n {
        let mut p1 = rng.gen::<(f64, f64)>();
        let mut p2 = rng.gen::<(f64, f64)>();
        // Multiply with 10 because we need numbers bigger than 1
        p1 = (p1.0 * 10.0, p1.1 * 10.0);
        p2 = (p2.0 * 10.0, p2.1 * 10.0);

        if positions.iter().all(|&p2| distance(p1, p2) > min_distance) {
            positions.push(p1);
            positions.push(p2);
        }
    }
    positions
}

I decided to bound the values after @orlp's suggestion. Having negative values is not so necessary because I transfer them on a canvas afterwards, but it would help. I could not however find an `rng` function where I can specify both the type ( `(f64, f64)`) and the range (`-b, b`) of the output — Craftrac, Sep 21 '18 at 12:32

How do I create random non-overlapping coordinates?

3 Answers3