最小包围球的弹跳泡算法

Question

我对Bouncing Bubble算法感兴趣,找到一组点的近似最小包围球.

我理解这个基本概念:" 每次发现球外的一个点时,球都会向它移动并同时增加半径.每一步的增长都是为了不超过最佳半径而设计的,因此,半径越来越接近最佳状态. "

然而,我无法在网上找到任何更具体的信息.如何计算增长？转向新点的距离有多远？

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

Answer 1

我意识到这篇文章已经有一年了,但是我用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);
}