生成区域中的点,其间具有至少X个间隙长度
Vec*_*vox 8 algorithm computational-geometry
我试图想出一种方法,用于在给定区域(在我的情况下是一个正方形)中生成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之间的距离最小？
谢谢!
编辑:更好,我的意思是通常更好地实现性能与完美的平衡.我知道,有点模糊.我并不确定我有多少开销可以产生这些点,所以我基本上比我自己的方法更优雅.
〜罗伯特
要理解您的问题：您是否正在寻找最佳答案（即：作业），或者寻找比创建随机点更好的非常好的算法？
在第一种情况下，如果你没有关于 A 区域的先验信息，恐怕这是一个非常复杂的问题。而且我相信很难找到比探索每一个案例更快的算法。
但是，如果您事先了解了 A 的一些信息，那么事情可能会更简单。例如，如果它是凸的，您可以利用这样一个事实：如果您的空间是无限的，则最佳路面是六边形。这意味着您必须将点（X 中）放在三角形的末端
所以 ：
- 计算凸包 (O(n*log(n)))
- 计算直径（集合中最远的两个点）
- 首先将（直径）点之一添加到 X
- 然后添加与六边形路面相对应的点，有利于凸包上的点
这个算法不是最优的（除非你定义了一个非常好的“偏向于凸包上的算法”......）
编辑：E 先生的评论提醒我，最佳的人行道源自圆形包装。为他的精确度点赞！
然而，我确实有另一种算法，看起来非常好，甚至可能是最优的！不需要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)），只有C，并且我相信在任何时候，C的大小都是O( n) ，仍然比 O(n^2) 好得多。计算直径仍然是 O(size(C)) = O(n)