在其间至少有 X 间隙长度的区域中生成点

我试图想出一种在给定区域（在我的例子中是一个正方形）中生成 X 个随机点的方法。造成这个问题的一件事是每个点必须距离所有其他点至少 Y 个单位。

首先想到的是（在 c# 中）检查新点与所有现有点之间的距离：

while(points.Count < pointsToGenerate)
{
     Point newPoint = NewPoint();
     bool addPoint = true;
     foreach(Point p in points)
     {
          if((p - newPoint).Length() < minDistance)
          {
              addPoint = false;
              break;
          }
     }

     if(addPoint)
     {
          points.Add(newPoint);
     }
}

现在这肯定会起作用，但是如果没有找到有效点，这将成为一个永无止境的循环。那么，在那里输入一个神奇的数字 Z 作为尝试的限制？

if(loopCount > 100)
{
     break;
}

现在这有一些明显的问题。如果点是随机生成的，则即使还有剩余位置可以放置点，loopCount 也可以高于 Z。它不仅可以，而且将会发生！

我可以做的是为每个通道创建一个可用点列表，然后随机选择其中一个。除了一件事之外，这将完美地工作：性能。我的应用程序不需要超级性能，但面积是 1000^2。即使我将自己限制为整数，每次传递仍有很多点需要检查！

因此，我能想到的可能还不够，因此我希望得到一些帮助。有没有更好的方法在区域 A 中生成 X 点，并且点 Y 之间的距离最小？

Thanks!

EDIT:我所说的“更好”是指通常更好，在性能与完美之间取得平衡。我知道有点模糊。我还不确定生成这些点需要多少开销，所以我基本上追求比我自己的方法更优雅的方法。

~Robert

要理解您的问题：您是否正在寻找最佳答案（即：作业），或者寻找比创建随机点更好的非常好的算法？

在第一种情况下，如果你没有关于 A 区域的先验信息，恐怕这是一个非常复杂的问题。而且我相信很难找到比探索每一个案例更快的算法。

但是，如果您事先了解了 A 的一些信息，那么事情可能会更简单。例如，如果它是凸的，你可以利用这样一个事实如果你的空间是无限的，最佳的路面是六边形。这意味着您必须将点（X 中）放在三角形的末端

So :

• 计算凸包 (O(n*log(n)))
• 计算直径（集合中最远的两个点）
• 首先将（直径）点之一添加到 X
• 然后添加与六边形路面相对应的点，有利于凸包上的点

这个算法不是最优的（除非你定义了一个非常好的“偏向于凸包上的算法”......）

编辑：E先生的评论提醒我，最佳的人行道源自圆形包装 http://en.wikipedia.org/wiki/Circle_packing。为他的精确度点赞！

然而，我确实有另一种算法，看起来非常好，甚至可能是最佳的！不需要A上的任何条件，价格有点贵，但也不算太多。是的，我知道，这与我所说的相矛盾，但谁在乎呢！拥有一个好的算法就足够了。

我们将迄今为止可用点的集合命名为 B。 C 是构成 B 的末端的点。一开始，B=A，如果 A 是正方形，则 C 由 4 个点（角）组成。你只需递归地：

• 计算 B 的两个最远点。为此，您只需要 C 中的点
• 随机将（直径）点之一添加到 X
• 从 B 中删除现在不可用的点。为此，您只需更新 C 即可。

我知道如果你在 1000x1000 的网格中工作，C 开始时有 4 个点，但是在 X 上添加一个点后，这意味着 C 增长到 1570 点（大约为 (pi/2)1000）。 你必须注意，你从来没有放入内存 B，它很大（如果 A 可以放入 n 中，则 O(n^2)n 个网格）只有 C，我相信在任何时候， C 的大小都是 O(n) ，这仍然比 O(n^2) 好得多。计算直径仍然是 O(size(C)) = O(n)