在一个立方体上平分距离的点

5

我需要初始化一些三维点,并希望它们在立方体中均匀分布。有没有什么创造性的方法可以做到这一点?

我正在使用迭代期望最大化算法,我希望我的初始向量能够均匀地“覆盖”空间。

例如,假设我有八个点,我希望它们在一个大小为1x1x1的立方体中均匀分布。我希望这些点位于一个边长为0.333的立方体的角落,且该立方体居中于较大的立方体中。

下面是一个二维示例。请注意,红色点彼此之间和边缘等距离。我希望在三维中也是这样。

Equidistant points

在点数没有整数立方根的情况下,我可以接受排列中留下一些“间隙”。

目前,我正在取点数的立方根,并使用它来计算点数和所需的距离。然后我遍历这些点并递增X、Y和Z坐标(错开,以便Y不会在X循环回0之前递增,Z也是如此)。

如果在MATLAB中有一种简单的方法可以实现这一点,我很乐意使用它。


你没有完全定义问题,例如在3D立方体中有许多可能的2点布局。 - quant_dev
我希望所有的点彼此之间以及与包含立方体的边缘等距离。 - sourcenouveau
彼此之间和所包含的立方体的边的距离相等?我不确定总是有一个满足这些条件的解决方案。 - RBarryYoung
只是解决一次问题...我有一个可行的算法,但我很好奇是否有更好的方法。 - sourcenouveau
具有8个点和1x1x1立方体的示例很容易想象。如果有10个点,该如何分配?这是否意味着您会像上面那样分配前8个点,然后随机分配剩余的2个点? - ralphtheninja
显示剩余3条评论
5个回答

5
您提出的采样策略被称为Sukharev网格,它是最优的低色散采样策略,详情请见http://planning.cs.uiuc.edu/node204.html。当采样点数不是n^3时,从网格中选择省略哪些点对于采样来说并不重要。
实际应用中,可以使用低差异(准随机)采样技术在三维空间中获得非常好的结果,详情请见http://planning.cs.uiuc.edu/node210.html。您可能需要考虑使用Halton和Hammersley序列。

这个回答很有趣,也许是我正在寻找的,但目前超出了我的理解范围。 - sourcenouveau

3

如果点的数量不是一个完美的立方体,那么您需要更详细地定义问题。然而,对于点的数量是一个立方体的情况,您可以使用以下方法:

l=linspace(0,1,n+2);
x=l(2:n+1); y=x; z=x;
[X, Y, Z] = meshgrid(x, y, z);

然后,对于矩阵中的每个位置,该点的坐标由X、Y和Z的相应元素给出。如果您希望将这些点列在单个矩阵中,使每行代表一个点,并具有x、y和z坐标的三列,则可以使用以下命令:

points(:,1) = reshape(X, [], 1);
points(:,2) = reshape(Y, [], 1);
points(:,3) = reshape(Z, [], 1);

现在你有一个网格上的立方体上 n^3 个点的列表,不包括边界。如其他人建议的那样,如果您想要更少的点,您可以随机删除一些点。这很容易做到,通过使用randi([0 n^3], a, 1)来生成要删除的a个点的索引。 (别忘了检查由randi()返回的矩阵中是否有重复项,否则您可能无法删除足够的点。)

1

0
在立方体内随机选择点,然后计算到最近邻居或墙壁的向量。接着,通过指数衰减步长延伸最小向量的端点。如果你迭代地执行这个过程,点应该会收敛到最优解。即使点的数量不是立方体形状,这种方法也同样适用。

我之前是这样做的,但现在我需要一个确定性的解决方案。 - sourcenouveau

-1
一个良好的随机生成器可以作为一个可用的第一近似。也许后续还可以使用一个过滤器,再随机重新定位那些最差的元素。

你如何定义好的随机数生成器?毕竟,如果它是随机的,它不应该为这个问题产生近似值。 - lacop
我需要一个确定性算法。 - sourcenouveau

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接