我正在寻找一种有人可以访问的算法，该算法可以计算包围一组其他边界球的最小边界球。我对此已经思考了一段时间，并提出了一些初步的解决方案，但我不认为这些解决方案一定是最准确的或计算成本最低（最快）的。
我的第一个解决方案是最简单的天真的解决方案，即将球体中心平均以获得中心点，然后计算从计算的中心到每个球体中心的最大距离加上其半径，作为半径。所以伪代码如下：
function containing_sphere_1(spheres)
center = sum(spheres.center) / count(spheres)
radius = max(distance(center, spheres.center) + radius)
return Sphere(center, radius)
end
但是我感觉它的计算量并不便宜，也不是很准确，因为生成的球体可能比需要的大很多。
我的第二个想法是使用迭代算法来计算最小边界球。它是通过连续测试另一个球体来计算的，如果测试的球体在边界内，则不执行任何操作，否则根据两个可用球体计算新的边界球体。如果新的边界球体延伸到球体表面，则新边界球体的中心位于两个中心之间的向量的一半，半径是该线长度的一半（从新中心到任一球体表面）。
function containing_sphere_2(spheres)
bounds = first(spheres)
for each sphere in spheres
if bounds does not contain sphere
line = vector(bounds.center, sphere.center)
extend(line, bounds.radius)
extend(line, sphere.radius)
center = midpoint(line)
radius = length(line) / 2
bounds = Sphere(center, radius)
end
end
return bounds
end
最初我认为这将是要走的路，因为它是迭代的并且看起来逻辑上相当一致，但是在阅读了一些内容之后，最值得注意的是 Emo Welzl 的文章“最小的封闭圆盘（球和椭球体）”，我不是不太确定。
据我了解，该算法的基础是 3 维中一组点的最小边界球体可以由最多 4 个点（位于封闭球体的表面上）确定。因此，该算法采用迭代方法，选择 4 个点，然后测试其他点以查看它们是否在内部，如果不是，则构建以新点为特征的新边界球。
现在该算法严格处理点，但我认为它可以应用于处理球体，主要的复杂性是在构造封闭球体时考虑半径。
那么，为一组给定球体创建最小边界球体的“最佳”算法（计算成本最低）是什么？
我在这里描述的其中之一就是答案吗？一些伪代码或算法会很棒。
从包围点到包围球的步骤并不简单，正如 K. Fischer 论文中的对 Welzl 算法（用于包围点）的讨论所解释的那样，“球中的最小包围球”。 参见第 2 节。 5.1.
第 4 章介绍“包围点”材料，然后第 5 章介绍“包围球体”。
： 对于每个球体，找到其最小/最大 x/y/z 点。把这6点扔进一个桶里。当您完成所有 N 个球体后，您将获得一桶 6N 点。使用任何已知算法找到这些的边界球。
无论采用何种算法，您得到的边界球很可能会有点太小。然后，您可以执行 Ritter 方法的第二遍，但使用球体的背面作为测试点。 “背面”表示球体上距离当前 bnd 球体中心最远的点。如果球体的背面 pt 位于当前 bnd 球体之外，则增长 bnd 球体以将其包含在内。
除了 6 个极值点之外，您最初还可以包括内切立方体的 8 个角：
( [+/-]kR, [+/-]kR, [+/-]kR )，其中 k=sqrt(3)/3。这给出了 14 个点，这些点在测地线上分布得相当均匀。
从第一种方法开始：找到点的平均值（可能按半径加权），并将其用作最小化算法（如
scipy.optimize.minimize）的起点，最小化半径加距离的总和当前位置（边界球体的中心）和另一个球体之间。在Python中：
import numpy as np
from scipy.optimize import minimize
# spheres given by centers = np.array([[x0,y0,z0],...])
# and radii = np.array([r0,...])
def dist(pos):
return np.min(radii + np.linalg.norm(centers-pos[np.newaxis,:]))
result = minimize(dist,x0=np.average(centers,axis=0,weights=radii))
bounding_center = result.x
bounding_radius = result.fun
* 对于 N 个球体和最小化例程对函数的 F 次调用，时间复杂度为 O((1+F)*N)。