如何生成n个点并限制它们之间的距离大于给定值？

Question

我想以均匀分布随机生成 n 个点，使得任意点之间的距离大于某个固定值。

这是我在 MATLAB 中的场景：

• 我有M个随机生成的红点，均匀分布如下：M个红点的横坐标为xr = rand(1, M)，M个红点的纵坐标为yr = rand(1, M).
• 此外，我有 M 个黑点，我生成的黑点与红点类似，即 xb = rand(1, M) 和 yb = rand(1, M)。

• 然后，我计算所有点之间的距离如下：

  x = [xr, xb];
  y = [yr, yb];
  D = sqrt(bsxfun(@minus, x, x').^2 + bsxfun(@minus, y, y').^2);
  d = D(1:M, M + 1:end);
  

• 现在，我必须限制距离 d 始终大于某个给定值，比如 d0=0.5。

如何操作？

Answer 1

虽然在 math.stackexchange 上讨论了这种采样（相当于非重叠圆圈生成），请参阅 https://mathematica.stackexchange.com/questions/2594/efficient-way-to-generate-random-points-with-a-predefined-lower-bound-on-their-p and https://mathematica.stackexchange.com/questions/69649/generate-nonoverlapping-random-circles, I would like to point out to another potential solution which involves quasi-random numbers. For quasi-random Sobol sequences there is a statement which says that there is minimum positive distance between points which amounts to 0.5*sqrt(d)/N, where d is dimension of the problem, and N is number of points sampled in hypercube. Paper from the man himself http://www.sciencedirect.com/science/article/pii/S0378475406002382