algorithm - 最小包囲球のバウンス バブル アルゴリズム

Question

バウンス バブル アルゴリズムに興味を持って、一連の点を囲む最小の近似球を見つけます。

「ボールの外側の点が見つかるたびに、ボールはそこに向かって移動し、同時に半径を増やします。各ステップでの成長は、最適な半径を超えないように設計されています。したがって、半径はますます最適に近づいています。」

しかし、オンラインのどこでも、それについてより具体的なものを見つけることができませんでした. 成長率はどのように計算されますか？新しいポイントへのシフトはどこまでですか？

実装例または独自のソリューションを実装するのに十分な情報を探しています。

Answer 1

この投稿が 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);
}