生成N个随机点，并确保它们之间有预定义的距离。

Question

我需要在MATLAB中创建一种高速公路场景。我需要在高速公路上生成随机点（即车辆）。使用randn()命令，随机点会重叠在彼此之上。我希望生成的随机点之间保持最小距离。

有谁能帮助我生成这种场景吗？

- reena

---

对于 R²，如果您想保持纯均匀分布，我不知道有比拒绝抽样更好的方法。需要均匀分布吗？您的场景有多大？对于大型场景，拒绝抽样可能会太慢。 - Daniel

场景：一条长度为L的高速公路（L值可以从3000米到10000米不等）。高速公路可以有多条车道。我必须随机在高速公路上生成车辆，以保持两辆车之间的最小距离。车辆数量可以从10到500不等。我认为车辆将均匀分布。如果我们可以使用其他分布来生成车辆，请告诉我。 - reena

Answer 1

您可以考虑使用泊松盘（也称为圆盘）抽样。基本上，泊松盘抽样会生成紧密排列的点，但彼此之间的距离不会比指定的最小距离更近，从而产生更自然的模式。

我的matlab有点生疏，很抱歉没有代码，但是有链接。

http://www.cs.sandia.gov/~samitch/papers/cccg-present.pdf

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

- Severin Pappadeux

---

这可能是解决非常大的问题的方法。 - Daniel

@severin：Danial是正确的。泊松盘用于大问题。我尝试了链接http://cusacklabcomputing.blogspot.ca/2013/07/poisson-disc-2d-in-matlab.html中提供的泊松盘。它生成了我不需要的大量数字。我需要在保持模拟区域恒定的情况下改变车辆数量。 - reena

Answer 2

这不是一个优雅的解决方案，但它满足您的最小距离限制。

% Highway dimensions
lx = 1000;
ly = 1000;

% Minimum distance
d = 100;

% Number of points to generate
n = 50;

points = [rand(1, 2) .* [lx ly]];
d2 = d ^ 2;

% Keep adding points until we have n points.
while (size(points, 1) < n)

    % Randomly generate a new point
    point = rand(1, 2) .* [lx ly];

    % Calculate squared distances to all other points
    dist2 = sum((points - repmat(point, size(points, 1), 1)) .^ 2, 2);

    % Only add this point if it is far enough away from all others.
    if (all(dist2 > d2))
        points = [points; point];
    end
end

plot(points(:,1), points(:,2), 'o')

- Jeff Irwin

---

这不是拒绝法，也不会生成所有可能的事件，其概率相同，但它可能非常接近。拒绝法会拒绝和重新生成所有点，直到一个集合符合要求。 - Daniel

@Danial 感谢澄清。如果我说错了，请纠正我，但真正的拒绝抽样比我的方法要慢得多。 - Jeff Irwin

特别是在拒绝概率较高时，它会变得更慢。 - Daniel

“d”和“n”的值是多少？根据输入的不同，将某个数量的车辆装入给定区域可能是不可能的。我已经使用“lx = 1000; ly = 700; d = 100; n = 50;”测试了我的代码，并且它按预期工作。 - Jeff Irwin

@Jeff Irwin：你是对的。我之前只是通过观察图形来判断距离。你给出的代码是有效的。 - reena