二维随机点的均匀分布

Question

我正在尝试做一个简单的 'crowd' 模型，需要在 2D 区域内分布随机点。这个半伪代码是我最好的尝试，但我什至在我运行它之前就可以看到大问题，因为对于密集的人群，新点太近的可能性会很快变得非常高，使它除非对值进行微调，否则效率非常低且容易失败。有符号值也可能存在问题，但为了简单起见，我将其省略。

int numPoints = 100;
int x[numPoints];
int y[numPoints];
int testX, testY;

tooCloseRadius = 20;
maxPointChecks = 100;
pointCheckCount = 0;

for (int newPoint = 0; newPoint < numPoints; newPoint++ ){

    //Keep checking random points until one is found with no other points in close proximity, or maxPointChecks reached.
    while (pointCheckCount < maxPointChecks){
        tooClose = false;
        // Make a new random point and check against all previous points
        testX = random(1000);
        testY = random(1000);
        for ( testPoint = 0; testPoint < newPoint; testPoint++ ){
            if  ( (isTooClose (x[testPoint] , y[testPoint], textX, testY, tooCloseRadius) ) {
            tooClose = true;
            break; // (exit for loop)
        }
        if (tooClose == false){
            // Yay found a point with some space!
            x[newPoint] = testX;
            y[newPoint] = testY;
            break; // (exit do loop)
        }
        //Too close to one of the points, start over.
        pointCheckCount++;
    }
    if (tooClose){
        // maxPointChecks reached without finding a point that has some space.
        // FAILURE DEPARTMENT
    } else {
        // SUCCESS
    }
}

// Simple Trig to check if a point lies within a circle.
(bool) isTooClose(centerX, centerY, testX, testY, testRadius){
    return (testX - centreX)^2 + (testY - centreY)^2)  < testRadius ^2
}

在谷歌搜索这个主题后，我相信我所做的被称为拒绝采样（？），自适应拒绝采样可能是更好的方法，但数学太复杂了。

是否有不需要统计学学位的优雅方法来实现这一点？

Answer 1

对于您提出的问题，生成随机样本的最佳方法是使用 Poisson Disk Sampling。

https://www.jasondavies.com/poisson-disc

现在，如果您想以简单的方式对矩形中的随机点进行采样。简单地从 0 到最大维度的长度，每个点采样两个值。

如果表示较小维度的值大于维度，则丢弃该对并重试。

伪代码：

while (need more points)
begin
   range = max (rect_width, rect_height);

   x = uniform_random(0,range);
   y = uniform_random(0,range);

   if (x > rect_width) or (y > rect_height)
    continue;
   else
     insert point(x,y) into point_list;
end

之所以选择两个长度中较大的一个作为样本，是为了在长度不同时使统一选择标准等效。

例如，假设一侧的长度为 K，另一侧的长度为 10K。并假设所使用的数字类型的分辨率为 K 的 1/1000，那么对于较短的一侧，只有 1000 个可能的值，而对于较长的一侧，则有 10000 个可能的值可供选择。 1/1000 的概率与 1/10000 不同。简单地说，短边的坐标值发生概率是长边坐标值的 10 倍——这意味着采样并不是真正均匀的。

您要确保生成的点与任何已生成的点的距离不小于某个距离的场景的伪代码：

while (need more points)
begin
   range = max (rect_width, rect_height)

   x = uniform_random(0,range);
   y = uniform_random(0,range);

   if (x > rect_width) or (y > rect_height)
    continue;

   new_point = point(x,y);

   too_close = false;

   for (p : all points)
   begin
     if (distance(p, new_point) < minimum_distance)
     begin
       too_close = true;
       break;
     end
   end

   if (too_close)
      continue;

   insert point(x,y) into point_list;
end

Answer 2

虽然泊松圆盘解决方案通常很不错，但我想指出一个使用准随机数的替代方案。对于准随机 Sobol 序列，有一个声明说点之间的最小正距离为 0.5*sqrt(d)/N，其中 d 是问题的维度（在您的情况下为 2）， N 是在超立方体中采样的点数。本人论文http://www.sciencedirect.com/science/article/pii/S0378475406002382.

为什么我认为应该是 Python？对不起这是我的错。类C语言最好调用GSL，函数名是gsl_qrng_sobol。在 d=2 处使用它的示例已链接 here

二维随机点的均匀分布

Even distribution of random points in 2D

random

plot

2d

distribution

pseudocode