algorithm - 如何创建随机的非重叠坐标？

Question

我正在尝试创建一个函数，该函数将生成长度为 n 的 vec，随机 x 和 y 一些边界 (-b, b) 之间 f64 类型的坐标。具有此类坐标的每个点之间必须有一个最小距离 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
}

Answer 1

大量点的算法草图(但分布与网格相关):

在您所在的区域构建正方形网格。选择单元格 Size = 3*MinDist。所以你有 (Width * Height)/(9 * MinDist^2) 点站点。

当你添加新点时，选择随机的自由站点并将点放置在网格结中，然后在 -Mindist..MinDist 范围内在两个方向上随机更改其位置。像元大小 3 保证没有点靠得太近。

生成示例:左图一半站点被占用，右图所有站点被占用

为了获得更好的“随机外观”，您可以缩小单元格大小 - 例如，2*MinDist，但在这种情况下，您必须检查相邻站点 - 但只有四个而不是全部。