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

Question

我正在尝试创建一个函数，它将生成一个vec长度，在某个边界之间n具有随机x和y类型的坐标。具有这种坐标的每个点必须彼此之间具有最小距离。我正在尝试使用该功能，但我被卡住了。我应该使用特定的分布还是添加一些过滤器或条件来实现这一点？f64(-b, b)dthread_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
}

标签： algorithmrustgeometrycoordinates

Answer 1

更多点的算法草图（但分布与网格相关）：

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

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

生成示例：左图占据一半站点，右图占据所有站点

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