我正在寻找3D球体随机紧密包装的算法。诀窍是我想在周围填充球体一定数量的现存球体。例如，给定100到1000个3D球体(它们具有固定的位置和大小;它们可能重叠，可能大小不同)，我想在它们周围填充球体(大小相同，位置可以自由选择)(没有重叠)。
衡量包装质量好坏的标准是包装密度或空隙率。从本质上讲，我希望固定球体和填充球体占据一个紧凑的空间体积(例如，大致为球形，或者围绕固定球体分层排列)，其中的空隙尽可能少。
是否有现成的算法可以做到这一点?你们如何在计算速度和包装质量之间取得平衡?
关于包装密度的细节:这取决于计算时选择的体积。为此，我们希望在固定的球体周围包装一定数量的球体层。形成一个点的曲面，这些点与最近的固定球的表面的距离为d;填料密度应在该表面封闭的体积内计算。如果d =填充球体大小的某个倍数，这很方便。(假设我们至少可以放置尽可能多的自由球体来填充该体积;可能会有多余的，不管放在哪里)
固定球和所有可变球的大小都非常相似(假设从最小到最大的范围在2倍以内)。在实践中，固定球的重叠程度也是有限的:没有一个固定球比任何其他固定球的一定距离(约0.2-0.3直径)更近(因此可以保证它们是分散的，和/或只重叠几个邻居而不是全部重叠)
赏金发布!
使用一个点阵，其中每个点与填充球体的直径等距。满足上述定义的任何晶格形状都可以。
定位晶格的平移和旋转，使固定球体的中心偏移量最小化，从而产生世界变换。
固定通道1:
创建一个列表中的任何晶格点固定球体半径+填充球体的直径。对于后者，保留位置(原点)差向量在列表中。
标记在列表中的点阵(移除)。
Lattice Pass 1:
结合,即。重新定位原点到重叠点(一个真正的重叠或扩展到填充半径)，任何重叠的固定球体的距离向量。存储值,萎靡不振的另一侧,允许多个重叠。
这就是需要做决定的地方:
- 随时间优化空间，计算速度慢:从调整的原点半径+填充半径添加点。然后迭代晶格点，每次从其他点移动一个点，直到满足所有间距条件。如果格子点实现春天逻辑,产生一个最优解时,给予足够的迭代(N ^ 2 + N)。? ?停在这里……做。
- 拉格子中剩余的点来填充空白:在每个重叠点或原点附近(大小根据需要而定)扭曲晶格，如果不存在重叠，则拉动点，以填补空白。
Lattice Pass 2:
添加缺失点，即在填充半径+ 1内没有其他点，并且不在固定球体附近(其他半径+填充半径)标记点作为移除。这应该是少量的点。
Lattice Pass 3:
调整所有网格位置，使其更接近适当的网格间距。这将单调地减少点之间的距离，限制为>= radius1 + radius2。
重复3-4次(或更多)。在创建的点的第一次传递中应用少量的随机性(每个维度最大1到-1像素)偏差偏移，以避免在翘曲之后出现任何相等的间距冲突。如果没有创建合适的间隙，解决方案可能会得到一个优化不佳的解决方案。
每个填充球以一个格点为中心。
我可以看到许多改进和优化的领域，但重点是提供一个清晰的，有点快的算法，这是好的，但不能保证最优。
注意1和2的区别:
第1条创建了一个与其他球体碰撞的球体，并要求所有填充物移动多次以解决碰撞。
2只在空白空间中创造新的球体，并将其余的球体向内移动以适应，导致更快的收敛，因为没有碰撞需要解决。