9

我对Bouncing Bubble Algorithm感兴趣，可以找到一组点的近似最小封闭球体。

我理解基本概念：“每次找到球外的一点，球就会向它移动并同时增加半径。每一步的增长都被设计成不会超过最佳半径，因此半径越来越接近最优值。 ” 在此处输入图像描述

但是，我无法在网上的任何地方找到更具体的信息。增长是如何计算的？向新点的转变有多远？

我正在寻找一个示例实现或足够的信息来实现我自己的解决方案。

4

3 回答 3

11

我意识到这篇文章已经有一年了，但我用 C++ 实现了弹跳气泡算法，并认为也许有些人会觉得它很有用。这是基于我以 18 美元购买的田波的论文。

BoundSphere calculateBoundSphere(vector<Vertex> vertices){
    Vector3D center = vertices[0].position;
    float radius = 0.0001f;
    Vector3D pos, diff;
    float len, alpha, alphaSq;
    vector<Vertex>::iterator it;

    for (int i = 0; i < 2; i++){
        for (it = vertices.begin(); it != vertices.end(); it++){
            pos = it->position;
            diff = pos - center;
            len = diff.length();
            if (len > radius){
                alpha = len / radius;
                alphaSq = alpha * alpha;
                radius = 0.5f * (alpha + 1 / alpha) * radius;
                center = 0.5f * ((1 + 1 / alphaSq) * center + (1 - 1 / alphaSq) * pos);
            }
        }
    }

    for (it = vertices.begin(); it != vertices.end(); it++){
        pos = it->position;
        diff = pos - center;
        len = diff.length();
        if (len > radius){
            radius = (radius + len) / 2.0f;
            center = center + ((len - radius) / len * diff);
        }
    }

    return BoundSphere(center, radius);
}
于 2014-07-18T06:24:52.133 回答
2

这是您要求的实现。对于分析部分，您可以阅读以下内容来获得想法。

这些分析适用于圆（2d），但扩展到球（3d）应该很容易。我相信分析会有所帮助。

O(n2) 时间算法

  • 在圆心 c 处画一个圆，使得给定集合的点位于圆内。显然，这个圆圈可以做得更小（或者我们有解决方案）。
  • 找到离圆心最远的点A，使圆变小，并以相同的中心画一个新的圆，并通过点A。这两个步骤产生一个更小的封闭圆。新圆更小的原因是这个新圆仍然包含给定集合的所有点，除了现在它通过最远的点 x，而不是包围它。
  • 如果圆通过 2 个或更多点，则继续执行步骤 4。否则，通过将中心移向 A 点来使圆变小，直到圆与集合中的另一个点 B 接触。
  • 在这个阶段，我们是一个圆 C，它通过给定集合的两个或多个点。如果圆包含的弧的间隔（无点间隔）大于圆的周长的一半，并且没有点位于该圆弧上，则可以使圆更小。令 D 和 E 为该无点区间末端的点。在将 D 和 E 保持在圆的边界上的同时，减小圆的直径，直到出现情况 (a) 或情况 (b)。
    • 情况 (a) 直径是距离 DE。
      我们完了！
    • 情况 (b) 圆 C 与集合中的另一个点 F 相接触。
      检查是否存在长度超过 C 周长一半的无点弧间隔。
      如果
      没有这样的无点弧间隔存在，那么我们完成了！
      否则
      转到第 4 步。在这种情况下，三个点必须位于小于圆周长度一半的弧上。我们在弧上三个点的外部两个重复步骤 4。

分析

该算法很简单，但实施起来很昂贵。步骤 1、2 和 3 需要给定集合中点数的线性时间。在上面的步骤 4 中，找到每个新点 F 需要线性时间。但是，找到点 F 并不能保证算法的终止。必须重复步骤 4，直到圆不包含长于其周长一半的无点间隔。在最坏的情况下，这需要步骤 4 的 (n-2) 次迭代，这意味着在步骤 4 中花费的总时间可能在点集大小的平方的数量级上。

因此，这个算法是 O(n2)。

O(n) 算法

Nimrod Megiddo 提出了该算法，它使用修剪和搜索技术进行线性规划，以在 O(n) 时间内找到最小封闭圆。

修剪和搜索

Megiddo 算法的本质是修剪和搜索。在修剪和搜索算法中，每一步都进行线性工作，以将输入大小减小一个恒定的分数 f。如果这可以实现，那么完成的工作总量将减少到 O(n)*(1 + (1-f) + (1-f)2 + ...)。在这个公式中，无穷级数是几何的，总和是一个常数，所以总的运行时间是 O(n)。

例如，假设通过检查我们的 n 个输入元素集，我们可以丢弃其中的 1/4，因为它们与解决方案无关。通过对剩余元素重复应用这种检查，我们可以将输入减少到一个容易解决的大小，比如 n≤3。实现这种减少所需的总时间将与 (n + 3n/4 + 9n/16 + ...) 成正比。很容易证明这个数列接近并且永远不会超过 4n 的极限。因此，根据需要，总运行时间与 n 成正比。

使用几何级数将算法简化为线性时间的想法早于 Megiddo 的工作；特别是，它以前曾被用于开发 O(n) 中值查找算法。然而，他是第一个将其应用于计算几何中的一些基本问题的人。

Megiddo 的线性时间算法

为了找到一组点的最小封闭圆 (MEC)，Megiddo 的算法在每次（线性时间）迭代中丢弃至少 n/16 个点。也就是说，给定一个包含 n 个点的集合 S，该算法识别出可以从 S 中删除的 n/16 个点，而不会影响 S 的 MEC。这个过程可以重复应用，直到达到一些琐碎的基本情况（例如 n=3 )，总运行时间与 (n + 15n/16 + 225n/256 + ...) = 16n 成正比。

为了找到要丢弃的 n/16 个点，需要大量的聪明才智。该算法大量使用了两个子程序：

  • 中位数（S，>）：采用一组元素和一个度量来对它们进行成对比较，并返回元素的中位数。
  • MEC-center(S, L)：取一组点S和一条线L，确定S的MEC中心在L的哪一侧。

如上所述，median() 早于 Megiddo 的工作，而这里描述为 MEC-center() 的算法是作为他 1983 年论文的一部分提出的。详细探索这些过程将超出本大纲的范围，但每个过程都使用修剪和搜索以线性时间运行。MEC-center() 使用的算法相当于整个算法的简化版本。

给定这些原语，丢弃 n/16 个输入点的算法运行如下：

  • 将 S 中的 n 个点任意配对得到 n/2 对。
  • 为每对点构造一条平分线，总共得到 n/2 个平分线。
  • 调用 median() 以找到具有中值斜率的平分线。将此斜率称为 mmid。
  • 将斜率≥ mmid 的每个平分线与斜率 < mmid 的每个平分线配对，得到 n/4 个交点。称这些点的集合为 I。
  • 调用 median() 以找到 I 中 y 值中值的点。将此 y 值称为 ymid。
  • 调用 MEC-center() 以查找 MEC 中心 C 位于 y=ymid 线的哪一侧。（不失一般性，假设它位于上面。）
  • 令 I' 是 I 中 y 值小于 ymid 的点的子集。（I' 包含 n/8 个点。）
  • 找到一条斜率为 mmid 的直线 L，使得 I' 中的一半点位于 L 的左侧，一半位于 L 的右侧。
  • 在 L 上调用 MEC-center()。不失一般性，假设 C 位于 L 的右侧。
  • 令 I'' 成为 I' 的子集，其点位于 L 的左侧。（I'' 包含 n/16 个点。）

我们现在可以为 I'' 中的 n/16 个交点中的每一个丢弃 S 中的一个点。推理如下。在两次调用 MEC-center() 之后，我们发现 MEC 中心 C 必须位于 ymid 上方和 L 的右侧，而 I'' 中的任何点都位于 ymid 下方和 L 的左侧。

I'' 中的每个点都在两条平分线的交点处。这些平分线之一的斜率必须≥ mmid，因此决不能通过我们知道 C 所在的象限。将此平分线称为 B。现在，我们知道 BC 位于哪一侧，因此在平分线为 B 的两点中，设 PC 与 C 位于同一侧，另一点为 PX。

很容易证明 PC 必须比 PX 更接近 C。因此，PC 不能位于最小封闭圆上，因此我们可以安全地丢弃 I'' 中 n/16 个交点中的每一个的点 PC。

我们在这里没有讨论如何使该算法处理退化输入（平行平分线、共线点等），但事实证明我们在这种情况下获得了相同的性能保证。事实上，对于简并输入，该算法能够丢弃超过 n/16 个点。简而言之，Megiddo 的算法保证在与输入无关的每次迭代中至少修剪 n/16 个点。

因此，通过基于几何级数的论证，Megiddo 算法在线性时间内计算出最小包围圆。

有关 O(n) 算法的更多信息，请参阅本文

于 2013-06-27T05:11:59.740 回答
0

更新：在仔细查看动画和维基百科文章后，我决定我的算法不是弹跳气泡。从动画中可以清楚地看出，Bouncing Bubble 移动了边界球，而我的算法一次只在一个方向上增长它。另外，我的理解是，Bouncing Bubble 使用近似值，可能不包含所有点；但是，似乎有一个您可以控制的容差参数。

我认为我的算法仍然有一些不错的属性：

  1. 是 O(n)。
  2. 它是增量的。
  3. 它保证包含所有点。
  4. 这很简单。唯一更简单的是找到轴对齐的边界框，然后在其周围放置一个球体，但这肯定会比该算法产生的体积更大。

我自己想出了一个 O(n) 增量算法，从 Wikipedia 上的描述来看，我相信它一定是 Bouncing Bubble 算法。我不知道它离最小边界圆有多近。首先，我将尝试解释我的算法背后的推理。把它画在纸上可能会有所帮助。

想象一下，您有一个以C为中心，半径为r的边界圆。您想扩展圆以包含新点P。您计算从C到P的距离d并发现它大于r，因此它必须在圆外。现在，如果您从P投射一条射线到C ，它会在A处离开圆的背面。

现在想象您将圆固定在A处，然后将其沿射线扩展回P。它将继续包含所有先前的点，现在它包含P。这个新圆的直径是r + d，因此它的半径是r' = (r + d) / 2。沿着从P到A的射线走新半径的距离，你就在新圆的中心。

这是算法的草图：

  1. 将边界球初始化为以半径r为 0的第一个点C为中心。
  2. 对于每个剩余点P：
    1. 如果从P到C的距离d <= r，则跳过它。
    2. 如果d > r：
      1. 新半径r' = (r + d) / 2。
      2. 新中心C' = P + r' (C - P) / d。

这是我今天刚刚写的一些 Objective-C 代码：

- (void)updateBoundingVolume {
    self.boundingSphereCenter = GLKVector3Make(0, 0, 0);
    self.boundingSphereRadius = 0;

    GLfloat* vertex = self.vertices;
    GLfloat* endV = vertex + 3 * self.vertNum;

    if (vertex < endV) {
        // initialize to zero radius sphere centered on the first point
        self.boundingSphereCenter = GLKVector3Make(vertex[0], vertex[1], vertex[2]);
        vertex += 3;
    }

    while (vertex < endV) {
        GLKVector3 p = GLKVector3Make(vertex[0], vertex[1], vertex[2]);
        vertex += 3;

        float d = GLKVector3Distance(self.boundingSphereCenter, p);
        if (d <= self.boundingSphereRadius) {
            // already inside the sphere
            continue;
        }

        // length of line from other side of sphere through the center to the new point
        // divide by 2 for radius
        self.boundingSphereRadius = (self.boundingSphereRadius + d) / 2;

        // unit vector from new point to old center
        GLKVector3 u = GLKVector3DivideScalar(GLKVector3Subtract(self.boundingSphereCenter, p), d);
        // step back from the new point by the new radius to get the new center
        self.boundingSphereCenter = GLKVector3Add(p, GLKVector3MultiplyScalar(u, self.boundingSphereRadius));
    }
}
于 2013-10-10T18:10:16.103 回答