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

最简单的方法是为每个坐标生成随机(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);
}

这是 ,但如果 只有100才行。

你要找的东西叫做 泊松盘分布 . 它发生在自然界视网膜上感光细胞的分布中。有一篇很好的文章 Mike Bostock StackOverflow profile )已调用 Visualizing Algorithms . 它有JavaScript演示和大量代码可供查看。

米切尔最佳候选算法

一个简单的近似称为MITCHELLS最佳候选算法。这是很容易实现的两个拥挤的一些空间和留下差距的其他。算法一次添加一个新点。对于每个新样本,最佳候选算法生成固定数量的候选,例如10个。将距离任何其他点最远的点添加到集合中,并重复该过程,直到达到所需的密度。

泊松盘抽样的bridson算法( original paper pdf)线性缩放,易于实现。这个算法从一个初始点发展而来(IMHO)非常有趣(再次参见Mike Bostock的文章)。集合中的所有点都处于活动或非活动状态。所有点都作为活动点添加。从激活集中选择一个点,并在环(即环)中生成一些候选点,该环从具有半径的内圆的样本延伸而来 r 外圆有一个半径 2r

大小网格 r/√2 可用于大大提高候选点的检查速度。一个方格中可能只有一个点,并且只需要检查有限数量的adjsent方格。

我不知道这是不是一个命名算法,但听起来你可以给每个节点分配一个网格上的位置,然后选择一个随机偏移。这将使一些混乱的外观,同时仍然保证没有大的空白空间。

例如:

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

或者你可以随机放置点,然后让空白区域吸引点,给点一个有限范围的排斥力,但这可能太复杂了,需要太多的CPU时间来完成这个简单的任务。