用较小的球体最佳地填充 3D 球体

Optimally filling a 3D sphere with smaller spheres

我正在尝试用 "particles"（由 3D XYZ 向量表示）以最佳方式填充 3D 球形体积，它们需要彼此保持特定距离，同时尝试尽量减少自由 space 介于两者之间。

不过有一个问题 - 粒子本身可能会落在球形体积的边界上 - 它们无法存在于球形体积之外。理想情况下，我想最大限度地增加落在该边界上的粒子数量（我想这是一种球形堆积问题），然后向内填充其余体积。

有没有什么算法可以解决这类问题？它不需要非常精确，但这里的关键是最终解决方案的密度需要相当准确（"perfect" 解决方案的 +/- ~5%）。

没有一个公式可以用 n 个球体最佳地填充一个球体。在 this wikipedia page you can see the optimal configurations for n <= 12. For the optimal configurations for n <= 500 you can view this 网站上。正如您在这些网站上看到的那样，不同数量的球体具有不同的最佳对称群。

你的约束有点模糊，所以很难确定，但我会为此尝试现场方法。初见：

  • Computational complexity and shape nesting
  • Path generation for non-intersecting disc movement on a plane
  • How to implement a constraint solver for 2-D geometry?

以及您可以在其中找到此方法的一些示例的子链接。

现在算法：

  1. 在球体内随机放置 N 个粒子

    N 应该安全地低，所以它比你的溶液粒子数小。

  2. 开始场模拟

    因此，请使用您的解决方案规则来创建吸引力和排斥力，并通过牛顿达朗贝尔物理学驱动您的粒子。不要忘记添加摩擦力（这样运动会在时间后停止）和球体体积边界。

  3. 当你的粒子停止移动时停止

    所以如果max(|particles_velocity|)<threshold停止。

  4. 现在检查所有粒子是否正确放置

    没有违反您的任何规则。如果是，那么请记住此位置作为解决方案，然后使用 N+1 粒子从 #1 重试。如果不停止并使用最后一个正确的解决方案。

    要加快速度，您可以添加更多粒子，而不是使用类似于二进制搜索的 (N+1)（添加 32 个粒子，直到可以……然后才 16……）。此外，您不需要在 #1 中为其他 运行 使用随机位置。您可以让其他粒子从它们在上一个 运行 解决方案中放置的位置开始。

如何确定解决方案的准确性是完全不同的事情。由于您没有提供确切的规则，因此我们只能猜测。我会尝试估计理想的粒子密度并根据球体体积计算理想的粒子数。您也可以将其用于 N 的初始猜测，然后与最终 N.

进行比较