Как создать случайные непересекающиеся координаты? - PullRequest
Новая
       23

Как создать случайные непересекающиеся координаты?

0 голосов
/ 21 сентября 2018

Я пытаюсь создать функцию, которая будет генерировать vec длины n со случайными x и y координатами типа f64 между некоторой границей (-b, b).Каждая точка с такой координатой должна иметь минимальное расстояние d друг от друга.Я пытаюсь использовать функцию thread_rng(), но я застрял.Должен ли я использовать определенный дистрибутив или добавить какой-либо фильтр или условие для достижения этого? 

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
}

Ответы [ 3 ]

0 голосов
/ 21 сентября 2018

Я использовал @ Boiethios 'ответ с некоторыми дополнениями, и, кажется, работает так, как я хочу.Единственная небольшая проблема заключается в том, что я не думал о способе вывода более конкретного диапазона, который также содержит негативы 

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
}
0 голосов
/ 21 сентября 2018

Схема алгоритма для большего количества точек (но распределение привязано к сетке):

Построить квадратную сетку в вашем регионе.Выберите ячейку Size = 3*MinDist.Таким образом, у вас есть (Width * Height) / (9 * MinDist^2) точечных сайтов.

Когда вы добавляете новую точку, выбираете случайный свободный сайт и размещаете точку в узле сетки, затем случайным образом меняете ее положение в диапазоне -Mindist..MinDist в обоих направлениях.Размер ячейки 3 гарантирует, что ни одна точка не находится слишком близко.

Пример генерации: половина сайтов занята на левой картинке, все сайты заняты на правой

enter image description hereenter image description here

Чтобы добиться лучшего «случайного вида», вы можете уменьшить размер ячейки - например, 2*MinDist, но в этом случае вам нужно проверить соседасайтов - но только четыре из них, а не все.

0 голосов
/ 21 сентября 2018

Вы можете использовать наивный алгоритм: пока сгенерированная точка не в порядке, попробуйте другую: 

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
}

Обратите внимание, что этот алгоритм вообще не подходит для большого количества точек,Это даже худший из возможных алгоритмов.

...