如何计算包围其他包围球的最小包围球 [英] How to compute the smallest bounding sphere enclosing other bounding spheres

问题描述

我正在寻找一个有人可以访问的算法，该算法将计算包围一组其他边界球的最小边界球.我已经考虑了一段时间，并提出了一些初始解决方案，但我认为这些解决方案不一定是最准确的，也不一定是计算成本最低的(最快的).

I'm looking for an algorithm which someone has access to that will compute the smallest bounding sphere that encloses a set of other bounding spheres. I have thought about this for a while and have come up with some initial solutions, but I don't believe these are necessarily the most accurate or the least computationally expensive (fastest).

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

My first solution is the simplest naive one, which is to average out the sphere centers to get the center point, and then compute the maximum distance from the calculated center to each sphere's center plus its radius, as the radius. So pseudo code goes like:

function containing_sphere_1(spheres)
  center = sum(spheres.center) / count(spheres)
  radius = max(distance(center, spheres.center) + radius)
  return Sphere(center, radius)
end

但是我觉得它在计算上不是那么便宜，也不是很准确，因为结果球体可能比需要的大得多.

However I get the feeling that it isn't that computationally cheap, nor is it quite accurate since the resulting sphere could be quite larger than it needs to be.

我的第二个想法是使用迭代算法来计算最小边界球.通过依次测试另一个球体来计算它，如果被测试的球体在边界之内，则什么也不做，否则从可用的两个球体中计算出一个新的边界球体.如果新的边界球体扩展到球体表面，则其中心将位于两个中心之间的矢量的一半处，并且半径是该线的长度的一半(从新中心到任一球体的表面). /p>

My second thought is to use an iterative algorithm to compute the minimal bounding sphere. It is computed by successively testing another sphere, if the tested sphere is inside the bounds, then nothing is done, otherwise a new bounding sphere is computed from the two spheres available. The new bounding sphere has a center that is half way between the vector between the two centers if it was extended to the spheres surfaces, and the radius is the half the length of that line (from the new center to either sphere's surface).

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撰写的文章最小的封闭磁盘(球和椭球)"，我不太确定.

Initially I thought that this would be the way to go, since it is iterative and seems fairly logically consistent, however after doing some reading, most notably the article "Smallest enclosing disks (balls and ellipsoids)" by Emo Welzl I'm not not so sure.

据我所知，该算法的基础是3个维度上的一组点上的最小边界球最多可以由4个点(在包围球的表面上)确定.因此，该算法采用了一种迭代方法，即选择4个点，然后测试其他点以查看它们是否在内部，如果不是，则以该新点为特征构造新的边界球.

As I understand it the basis of this algorithm is that the minimum bounding sphere over a set of points in 3 dimensions can be determined by at most 4 points (which are on the surface of the enclosing sphere). So the algorithm takes an iterative approach by selecting 4 points, and then testing other points to see if they're inside or not, if they aren't a new bounding sphere is constructed featuring the new point.

现在该算法严格地处理点，但是我认为它可以用于处理球体，主要复杂之处在于构造封闭球体时要增加半径.

Now the algorithm deals strictly with points, but I think it can be applied to deal with spheres, the main complication being accounding for the radius when constructing the enclosing sphere.

那么，为计算一组给定球体创建最小边界球体的最佳"算法(至少是计算量最少的算法)是什么?

So what is the 'best', as in least computationally expensive, algorithm that creates a minimal bounding sphere for a set of given spheres?

我在这里描述了答案之一吗?一些伪代码或算法会很棒.

Is one of these I have described here the answer? Some pseudo code or the algorithm would be great.

推荐答案

从封闭点到封闭球体的步骤并非易事，因为

The step from enclosing points to enclosing spheres is non-trivial, as the discussion of Welzl's algorithm (which works to enclose points) in K. Fischer's thesis explains, "Smallest enclosing ball of balls". See Sec. 5.1.

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

Chapter 4 presents the "enclosing points" material, then Chapter 5 presents "enclosing spheres".

费舍尔论文中描述的算法已在CGAL包中中实现从3.0版开始，如果您只是在寻找实现的话.

The algorithm described in Fisher's thesis has been implemented in the CGAL package since release 3.0, if you are just looking for an implementation.

这篇关于如何计算包围其他包围球的最小包围球的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！