algorithm - 最小封闭球体的弹跳气泡算法

Question

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

我理解基本概念:“每次找到球外的一个点，球就会向它移动并同时增加半径。每一步的增长都经过精心设计，因此它会不超过最佳半径，因此半径越来越接近最佳。"

然而，我无法在网上任何地方找到更具体的信息。增长是如何计算的？向新点移动了多远？

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

Answer 1

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

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);
}