algorithm - 在 3D 边界框中以最佳方式拟合其他球体之间的球体的算法？

我正在努力解决一个 3D 问题，我正在努力寻找一种有效的算法。

我有一个给定宽度、高度和深度的边界框。
我也有一个球体列表。也就是说，每个球体的中心坐标 (x _i ,y _i ,z _i ) 和半径 r _i。

球体保证适合边界框，并且不会相互重叠。

所以我的情况是这样的：

边界框中的球体

现在我有一个半径为 r 的新球体，我必须将其放入边界框内，而不是与之前的任何球体重叠。

我还有一个目标点 T = (x,y,z)，我的目标是让这个新球体（在上述条件下）尽可能靠近这个目标点。

我正在尝试构建一种有效的算法来找到新球体的最佳位置。Optimal as in：尽可能靠近目标点。或者，如果在边界框内的任何地方，在现有球体之间或周围没有空间可以容纳这个新球体，则结果为“错误”。

我已经想到了各种复杂的方法，比如构建剩余体积的某种参数化描述，从边界框开始，然后一个一个地减去现有的球体。但这似乎并没有引导我找到可行的解决方案。

请注意，有很多已知的“球体填充”算法，但它们往往只是用随机球体填充体积。他们也经常使用试错法，只是做一定数量的随机尝试然后终止。

而我有一个给定的特定新球体大小，我需要适应它（或发现这是不可能的）。

标签： algorithmoptimization3dvolumepacking

一种可能的方法是计算球体的“距离图”，即为每个点 (x, y, z) 返回到最近球体的距离的函数，这也是到最近中心的距离减去半径对应的球体。该地图由（超）圆锥曲面的交集组成。

然后您可以探索目标点周围的距离图，找到值超过目标半径的最近点。

如果我是对的，距离图与球心的加性加权 Voronoi 图（https://en.wikipedia.org/wiki/Weighted_Voronoi_diagram）直接相关，并且该图的顶点对应于局部最大值。因此，具有超过目标半径的值的最接近的 Voronoi 顶点将给出解决方案。

不幸的是，这个图表的构建不会是一个笑话。查看文章“3D 球的欧几里得 Voronoi 图及其通过跟踪边的计算”及其参考书目。

估计距离图的一种可能可行的解决方案是在规则的立方体网格中离散空间，并为每个立方体获得距离函数的下限和上限。

对于单个给定的球体和给定的立方体，可以通过解析找到最小值和最大值。然后考虑所有球体，您可以找到最小的最大值和最小的最小值，它们是真实距离的上限和下限（最大的最小值不会做）。然后，您保留所有球体，以使最小值保持在该上限以下，并且您会获得（希望是简短的）候选人列表。

在这里您可以检查到列表中球体的距离，如果上限小于目标半径，则可以放下立方体。如果您找到目标半径以上的上限，则您已经找到了解决方案。否则，如果距离函数的不确定性范围太大，则将立方体细分为较小的立方体，以便更准确地估计上下限。

要获得接近目标点的解决方案，您将通过增加与目标的距离（使用嵌套数字球体）来访问立方体，直到找到匹配项。

这个过程的一个关键点是快速找到最接近给定立方体的球体，以进行初始估计。诸如 kD-tree 或类似的数据结构可能会有所帮助。