math - 如何在平面上随机但均匀地分布节点

Question

我需要在 html5 Canvas 上放置 1 到 100 个节点(实际上是 25px 点)。我需要让它们看起来是随机分布的，所以使用某种网格已经过时了。我还需要确保这些点不接触或重叠。我也希望没有大的空白区域。谁能告诉我这种算法叫什么？对执行此操作的开源项目的引用也将不胜感激。

谢谢大家

圭多

Answer 1

您正在寻找的是一个 泊松盘分布 .它在自然界中发生在视网膜上感光细胞的分布中。 Mike Bostock 有一篇关于此的很棒的文章( StackOverflow profile ) 称为 Visualizing Algorithms .它有 JavaScript 演示和大量代码可供查看。
为了做更多的事情而不是在答案中添加链接，我将尝试对文章进行简要总结:
米切尔的最佳候选算法
一种简单的近似方法，称为 Mitchell 的最佳候选算法。很容易实现既挤满一些空间又在其他空间留下空隙。该算法一次添加一个新点。对于每个新样本，最佳候选算法生成固定数量的候选者，比如 10。将离任何其他点最远的点添加到集合中，并重复该过程，直到达到所需的密度。
Bridson 算法
Bridson 的 Poisson-disc 采样算法 (original paper pdf) 线性缩放并且也很容易实现。该算法从初始点开始增长，并且(恕我直言)观看起来非常有趣(再次参见 Mike Bostock 的文章)。集合中的所有点要么是事件的，要么是非事件的。所有点都添加为事件点。从事件集中选择一个点，并在从样本延伸的环(也称为环)中生成一些候选点，其中内圆的半径为 r和半径为 2r 的外圆.拒绝与 FinalSet 中任何点相距小于 r 距离的候选样本。一旦找到未被拒绝的样本，它就会被添加到 FinalSet。如果所有候选样本都被拒绝，则原始点被标记为非事件的，前提是它有很多相邻的点，以至于不能在它周围添加更多的点。当所有样本都处于非事件状态时，算法终止。
大小的网格 r/√2可用于大大提高检查候选点的速度。一个网格方块中可能只有一个点，并且只需要检查有限数量的相邻方块。