hbf / miniball

Fast computation of the smallest enclosing ball of a point set, in low or moderately high dimensions.
133 stars 41 forks source link

[CPP] Wrong result for simple 3D sphere? #41

Closed zsln closed 6 months ago

zsln commented 6 months ago

I have a relative simple example for which Miniball computes the wrong center. I've been using the following points:

{1, 0, 0}
{0, 1, 0}
{0, 0, 1}
{0, -2, 0}

Following snippet was used:

int main()
{
    typedef double FT;
    typedef Seb::Point<FT> Point;
    typedef std::vector<Point> PointVector;
    typedef Seb::Smallest_enclosing_ball<FT> Miniball;

    using std::cout;
    using std::endl;
    using std::vector;

    const int d = 3;

    PointVector S;
    Point temp(d);
    /// i made the member .c public to avoid hassle but it should not influence the result
    temp.c = {1, 0, 0};
    S.push_back(temp);
    temp.c = {0, 1, 0};
    S.push_back(temp);
    temp.c = {0, 0, 1};
    S.push_back(temp);
    temp.c = {0, 0, 0};
    S.push_back(temp);
    temp.c = {0, -2, 0};
    S.push_back(temp);

    // Compute the miniball by inserting each value
    Miniball mb(d, S);

    // Output
    FT rad = mb.radius();
    FT rad_squared = mb.squared_radius();
    cout << "Radius = " << rad << " (squared: " << rad_squared << ")" << endl << "Center:" << endl;
    Miniball::Coordinate_iterator center_it = mb.center_begin();
    for (int j = 0; j < d; ++j)
        cout << "  " << center_it[j] << endl;
    cout << "=====================================================" << endl;
    mb.verify();
    cout << "=====================================================" << endl;
}

The expected result is (-.5, -.5, -.5), the output however is

Radius = 1.5 (squared: 2.25)
Center:
  0
  -0.5
  0
=====================================================
Solution errors (relative to radius, nonsquared)
  final QR inconsistency     : 0
  minimal convex coefficient : positive
  maximal overlength         : 0
  maximal underlength        : 0
=====================================================

Am I doing something wrong here?

hbf commented 6 months ago

The expected result is (-.5, -.5, -.5)

This squared distance from your proposed center (-.5, -.5, -.5) to the forth point, (0, -2, 0), is 0.5^2+1.5^2+0.5^2 = 2.75. This is strictly larger than the reported ball's squared radius of 2.25.