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

Question

我需要在html5画布上放置1到100个节点(实际上是25px点).我需要让它们看起来随机分布,所以使用某种网格就可以了.我还需要确保这些点不接触或重叠.我也希望没有大的空白区域.谁能告诉我这种算法叫什么？对这样做的开源项目的引用也将受到赞赏.

谢谢大家

圭多

Answer 1

您正在寻找的是一种泊松盘分布.它在自然界中发生在视网膜上的感光细胞分布.Mike Bostock(StackOverflow profile)有一篇名为Visualizing Algorithms的文章.它有JavaScript演示和许多代码可供查看.

为了做更多的事情,然后将链接放到答案中,我将尝试简要介绍一下这篇文章:

米切尔的最佳候选算法

一种简单的近似,称为米切尔的最佳候选算法.很容易实现两个人群的空间,并在其他空间留下空白.该算法一次添加一个新点.对于每个新样本,最佳候选算法生成固定数量的候选者,例如10.将距离任何其他点最远的点添加到集合中,并且重复该过程直到达到期望的密度.

布里森的算法

Bridson的Poisson-disc采样算法(原始论文 pdf)线性扩展,易于实现.这个算法从最初的点开始增长,并且(恕我直言)非常有趣(再次参见Mike Bostock的文章).集合中的所有点都是活动的或非活动的.所有积分都被添加为有效积分.从活动集中选择一个点,并且在环形(也称为环)中生成一些候选点,其从样本延伸,其中内圆具有半径r,外圆具有半径2r.候选样本少于距离FinalSet中任何一点的r距离被拒绝.一旦找到未被拒绝的样本,就会添加FinalSet.如果所有候选样本都被拒绝,则原始点被标记为非活动,假设具有如此多的邻近点,则不能在其周围添加更多邻居点.当所有样本都处于非活动状态时,算法终止.

r/?2可以使用大小网格来大大提高检查候选点的速度.只有一个点可能在网格中,并且只需要检查有限数量的相邻方块.

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 那就没问题了。