如何在平面上随机均匀分布节点

Question

我需要在一个HTML5画布上放置1到100个节点（实际上是25像素的点）。我需要让它们看起来是随机分布的，所以使用某种网格方式排列就不可行了。我还需要确保这些点不相互接触或重叠。同时，我也不希望有太多空白区域。请问这种算法叫什么？如果能提供一个开源项目的参考，那就更好了。

谢谢大家

Guido

- gatapia

---

我想到了 Floyd-Steinberg 抖动和低差异准随机序列...这两者在这里都有点过头了。 - Peter G.

Answer 1

你需要的是称为泊松盘分布的东西。它在你的视网膜上的光感受器细胞的分布中也出现在自然界中。Mike Bostock（StackOverflow profile）有一篇关于这个的很棒的文章，名为Visualizing Algorithms。它有JavaScript演示和许多代码可供查看。

为了不仅仅在答案中放置一个链接，我将尝试简要概括这篇文章：

Mitchell's best-candidate algorithm

一个简单的近似算法被称为Mitchell的最佳候选算法。它易于实现，但在某些空间中会拥挤，而在其他空间中则会留下空隙。该算法逐个添加新点。对于每个新样本，最佳候选算法生成固定数量的候选项，例如10个。距离任何其他点最远的点被添加到集合中，并重复此过程，直到达到所需密度。

Bridson's Algorithm

Bridson的泊松盘采样算法（原始论文 pdf）具有线性可扩展性，并且易于实现。该算法从一个初始点开始生长，看起来非常有趣（可以参考Mike Bostock的文章）。集合中的所有点都是活动或非活动的。所有点都被添加为活动状态。从活动集合中选择一个点，并在环形区域（也称为圆环），该区域从内圆半径r到外圆半径2r扩展，生成一些候选点。距离FinalSet中任何点小于r的候选样本将被拒绝。一旦找到一个未被拒绝的样本，它就会被添加到FinalSet中。如果所有的候选样本都被拒绝，则假定原始点已经有了太多的邻居点，无法再添加更多点，因此将其标记为非活动状态。当所有样本都处于非活动状态时，算法终止。

一个大小为r/√2的网格可以用来极大地提高检查候选点的速度。每个网格方格中只能有一个点，只需检查有限数量的相邻方格即可。

- John F. Miller

---

+1 感谢您提醒我 Bostock 的精彩演示页面。真是令人惊叹。唯一可以改进这个答案的是提供一个最佳候选 findNearest 方法的 Quadtree 实现链接。 - Tom Auger

Answer 2

最简单的方法是为每个点生成随机的(x, y)坐标，如果它们相互接触或重叠就再次生成。

伪代码:

do N times
{
start:
  x = rand(0, width)
  y = rand(0, height)
  for each other point, p
    if distance(p.x, p.y, x, y) < radius * 2
      goto start
  add_point(x, y);
}

这是O(n^2)，但如果n只会到100，那就没问题了。

- Peter Alexander

---

这正是O(n^2)……对于每个点，你都必须检查其他每个点。当然有更快的方法，但我提出的算法肯定是O(n^2)。 - Peter Alexander

可能无法满足 n^2 的部分是因为重叠的部分会将您带回该点的起始位置。（例如，如果您的平面空间不足，则此过程永远不会终止。在临界尺寸附近，取决于您的“运气”，它可能会或可能不会终止。) 对于所有能够有解的大小，期望运行时间可能仍然是n^2，但也可能不是...所需的数学知识可能并不是微不足道的。 - Michael Anderson

Answer 3

我不知道这是否是一种已命名的算法，但你可以将每个节点分配到“网格”上的一个位置，然后选择一个随机偏移量。这会给人一种混乱的感觉，同时仍然保证没有大的空白区域。

例如：

node.x = node.number / width + (Math.random() - 0.5) * SOME_SCALE;
node.y = node.number % height + (Math.random() - 0.5) * SOME_SCALE;

- David Wolever

---

这是一种抖动的形式，通常不会产生视觉（或其他方面）上令人满意的结果，因为你要么会抖动过度（失去网格结构并引入聚类），要么抖动不够（使网格结构可见）。 - cemper93

Answer 4

也许你可以使用一个圆形网格，在每个圆里放置一个25像素的点？虽然不是真正的随机，但看起来很好。 或者你可以随机放置点，然后使空白区域吸引点，并给点一个有限范围的排斥力，但这可能对于这个简单的任务来说太复杂了，需要太多的CPU时间。

- thejh