我正在寻找一种算法,它可以计算包围一组其他边界球的最小边界球。我已经思考了一段时间,并提出了一些初步解决方案,但我不认为这些方案一定是最准确或最节省计算开销的(速度最快)。
第一个想法
我的第一个解决方案是最简单和朴素的一种,即将球心平均化以获得中心点,然后计算从计算出的中心到每个球心加其半径的距离的最大值作为半径。 因此,伪代码如下:
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的文章“Smallest enclosing disks (balls and ellipsoids)”,我不太确定了。
Welzl算法
据我所知,该算法的基础是可以通过最多4个点(位于包围球体表面上的点)来确定3维空间中一组点的最小包围球。因此,该算法采用迭代方法,首先选择4个点,然后测试其他点是否在其内部,如果不在,则构造包含新点的新的边界球体。
现在该算法严格处理点,但我认为它可以应用于处理球体,主要的问题在于在构造包围球体时要考虑半径。
回到问题
那么,对于给定的一组球体,创建最小包围球的“最佳”(即计算成本最小)算法是什么?
我描述的其中一个是答案吗?提供伪代码或算法将会很好。