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

Question

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

我有一个给定宽度、高度和深度的边界框。
我还有一个领域列表。即，每个球体的中心坐标 (xi _, y _i ,zi ₎和半径 r _{i 。}

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

所以我的情况是这样的：

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

我还有一个目标点 T = (x,y,z)，我的目标是使这个新球体（给定上述条件）尽可能接近该目标点。

我正在尝试构建一种有效的算法来找到新球体的最佳位置。最优为：尽可能接近目标点。或者，如果边界框内任何位置的现有球体之间或周围没有空间适合这个新球体，则结果为“假”。

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

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

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

Answer 1

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

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

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

不幸的是，这个图的构建不会让人笑出声来。查看文章“3D 球的欧几里得 Voronoi 图及其通过追踪边缘的计算”及其参考书目。

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

对于单个给定的球体和给定的立方体，可以通过分析找到最小值和最大值。然后考虑所有球体，您可以找到最小的最大值和最小的最小值，它们是真实距离的上限和下限（最大的最小值不行）。然后你保留所有的范围，使最小值保持在上限以下，你就得到了一个（希望是简短的）候选者列表。

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

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

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