用于将点均匀放置在球体内的算法

Question

如果我有一个带有中心(x，y，z(和半径r的球体，请在将x数(x，y，z(放置在球体中的x数量(x，y，z(中例如，最小距离彼此之间的距离是最大化的？

例如。一个点将仅放在中间，将两个点放在相反的边界上，将三个点放在边界上的"三角形"地层中，等等。

。

正如已经指出的那样，每个数量的点都找不到相等的距离。因此，要求是为了最大化点之间的最小距离。

更新：

以下代码在半径1.0的球体内生成点，但不会最大化距离。

function getPoint() {
    var d, x, y, z;
    do {
        x = Math.random() * 2.0 - 1.0;
        y = Math.random() * 2.0 - 1.0;
        z = Math.random() * 2.0 - 1.0;
        d = x*x + y*y + z*z;
    } while(d > 1.0);
    return {x: x, y: y, z: z};
}

我认为之后我需要某种迭代。我试图使用n体问题作为灵感应用力模型，尽管有趣的是，它并没有很好地奏效。

Answer 1

对于随机但均匀的放置，在球体的边界立方体中绘制均匀的随机点，并接受球体内部的均匀点。当您有足够的积分时停止。

如果您想定期安排，问题要困难得多。

Answer 2

对于随机点均匀分布在单位球内，用圆柱坐标(r,phi,z)我们有

           int[0,x] 2*r*pi*2*sqrt(1-r^2) dr
P(r < x) = -------------------------------- = 1 - (1-x^2)^(3/2) =: F(x), x in [0,1]
                        4*pi/3

逆函数F^-1(r) = sqrt(1-(1-r)^(2/3))将在[0,1]中均匀分布的随机变量U转换为以上r分布的随机变量。由于1-U具有与U相同的分布，我们可以使用更简单的函数sqrt(1-r^(2/3))。

圆柱坐标的其他组件phi和z均匀分布在相应的范围内。

因此，我们获得了python代码，用于直接生成像这样的球体中平等分布的点：

import math, random
def randomUnitSpherePoint():
    # cylindrical coordinates
    rxy = math.sqrt(1 - random.uniform(0, 1)**(2./3.))
    phi = random.uniform(0, 2*math.pi)
    zAbsMax = math.sqrt(1 - rxy*rxy)
    z = random.uniform(-zAbsMax, zAbsMax)
    # cartesian coordinates
    x,y = rxy*math.cos(phi), rxy*math.sin(phi)
    return x,y,z
def randomSpherePoint(center, radius):
    x,y,z = randomUnitSpherePoint()
    return center[0] + r*x, center[1] + r*y, center[2] + r*z

Note ："标准"解决方案(在边界框中生成随机点和球内的选择点(通常更有效，尤其是在使用伪随机数字生成器时。

。

Answer 3

该问题与将相同的球填充到单位球体(也许两个问题甚至是等效的(密切相关：在将半径r的n球填充的解决方案中，所有球体中心都位于半径1-r的球体内，并且至少为2r。因此，可以将相同球包装到单位球体中的解决方案很容易地转化为解决问题的解决方案。

证明了用于包装相同球的最佳解决方案，仅存在于n=12。因此，我想您还必须使用近乎最佳的解决方案，至少对于n>12。目前最著名的算法在最佳方面似乎是相等球填料问题的串行对称迁移算法。

Answer 4

只是一个更新，因为我忘记了这个问题：

由于统一方法足够好，可以超过100点，并且由于有人计算了1至99分在球体上的位置，因此解决方案是查找[1：100]的位置，否则会生成分布均匀的点。