如何计算包围其他边界球的最小边界球

Question

我正在寻找一个有人可以访问的算法,它将计算包含一组其他边界球体的最小边界球体.我已经考虑了一段时间,并提出了一些初步的解决方案,但我不相信这些必然是最准确或最少计算的(最快).

第一个想法

我的第一个解决方案是最简单的天真解决方案,即平均球形中心以获得中心点,然后计算从计算中心到每个球体中心的最大距离加上其半径,作为半径.所以伪代码如下:

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我不是不是这么肯定.

Welzl的算法

据我所知,该算法的基础是3维中一组点上的最小边界球可以由最多4个点(在封闭球体的表面上)确定.因此,该算法通过选择4个点进行迭代,然后测试其他点以查看它们是否在内部,如果它们不是新的边界球,则构造特征为新点.

现在算法严格处理点,但我认为它可以应用于处理球体,主要的复杂因素是在构造封闭球体时对半径进行处理.

回到问题

那么,对于一组给定的球体,创建最小边界球的"最佳"算法是什么,至少是计算成本最高的算法？

我在这里描述了其中一个答案吗？一些伪代码或算法会很棒.

Answer 1

从封闭点到封闭球体的步骤是非常重要的,因为在K.Fischer的论文中对Welzl算法(用于封闭点)的讨论解释了"最小的球包围球".见第二节.5.1.

第4章介绍了"封闭点"材料,然后第5章介绍了"封闭球体".

Fisher论文中描述的算法已经在 3.0版本的CGAL包中实现,如果你只是在寻找一个实现.

Answer 2

这是一种基于 Ritter 算法的快速、近乎最优的方法 https://en.wikipedia.org/wiki/Bounding_sphere：

对于每个球体，找到其最小/最大 x/y/z 点。把这6点扔进一个桶里。当您完成所有 N 个球体后，您将获得一桶 6N 点。使用任何已知算法找到这些的边界球。

无论算法如何，您得到的边界球很可能会有点太小。然后，您可以执行 Ritter 方法的第二遍，但使用球体的背面作为测试点。“背面”表示球体上距离当前 bnd 球体中心最远的点。如果球体的背面 pt 位于当前 bnd 球体之外，则增长 bnd 球体以将其包含在内。

除了 6 个极值点之外，您最初还可以包括内切立方体的 8 个角：

（[+/-]kR、[+/-]kR、[+/-]kR ），其中 k=sqrt(3)/3。这给出了 14 个点，这些点在测地线上分布得相当均匀。