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

Question

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

我有一个给定宽度、高度和深度的边界框。
我也有一个球体列表。即，每个球体的中心坐标 (xi,yi,zi) 和半径 ri。

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

所以我的情况是这样的:



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

我还有一个目标点 T = (x,y,z) 并且我的目标是让这个新球体(给定上述条件)尽可能靠近这个目标点。

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

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

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

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

Answer 1

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

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

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

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

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

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

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

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

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