optimisation_sphere_d.h

很多二维 三维几何计算算法 C++ 类库

// Copyright (c) 1997  ETH Zurich (Switzerland).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.3-branch/Min_sphere_d/include/CGAL/Min_sphere_d/Optimisation_sphere_d.h $
// $Id: Optimisation_sphere_d.h 37153 2007-03-16 10:21:25Z afabri $
// 
//
// Author(s)     : Sven Schoenherr <[e-mail]>
//                 Bernd Gaertner

#ifndef CGAL_OPTIMISATION_SPHERE_D_H
#define CGAL_OPTIMISATION_SPHERE_D_H

CGAL_BEGIN_NAMESPACE

// Class declarations
// ==================
// general template
template <class Rep_tag, class FT, class RT, class PT, class Traits>
class Optimisation_sphere_d;

template <class FT, class RT, class PT, class Traits>
class Optimisation_sphere_d<Homogeneous_tag, FT, RT, PT, Traits>;

template <class FT, class RT, class PT, class Traits>
class Optimisation_sphere_d<Cartesian_tag, FT, RT, PT, Traits>;
    
CGAL_END_NAMESPACE

    // Class interfaces and implementation
    // ==================================
    // includes


    #include <CGAL/Optimisation/basic.h>

    #include <CGAL/Optimisation/assertions.h>


    CGAL_BEGIN_NAMESPACE

    // Cartesian version
    // -----------------
    template <class FT, class RT, class PT, class Traits>
    class Optimisation_sphere_d<Cartesian_tag, FT, RT, PT, Traits>
    {
    private:
        typedef
          typename Traits::Access_coordinates_begin_d::Coordinate_iterator  It;
        
        // hack needed for egcs, see also test programs
        typedef             FT                              FT_;
        
        int                 d;                      // dimension
        int                 m;                      // |B|
        int                 s;                      // |B\cup S|
        
        FT**                q;                      // the q_j's
        FT***               inv;                    // the A^{-1}_{B^j}'s
        FT*                 v_basis;                // the vector v_B
        
        FT*                 x;                      // solution vector
        FT*                 v;                      // auxiliary vector
        
        FT*                 c;                      // center, for internal use
        PT                  ctr;                    // center, for external use
        FT                  sqr_r;                  // squared_radius
        
        Traits              tco;
        

    public:

        Optimisation_sphere_d& get_sphere (Cartesian_tag)
        {return *this;}

        const Optimisation_sphere_d&
          get_sphere (Cartesian_tag) const
        {return *this;}

        Optimisation_sphere_d (const Traits& t = Traits())
            : d(-1), m(0), s(0), tco (t)
        {}
        
        void set_tco (const Traits& tcobj)
        {
            tco = tcobj;
        }
        
        
        void init (int ambient_dimension)
        {
            d = ambient_dimension;
            m = 0;
            s = 0;
            sqr_r = -FT(1);
        
            q =             new FT*[d+1];
            inv =           new FT**[d+1];
            v_basis =       new FT[d+2];
            x =             new FT[d+2];
            v =             new FT[d+2];
            c =             new FT[d];
        
            for (int j=0; j<d+1; ++j) {
                q[j] =      new FT[d];
                inv[j] =    new FT*[j+2];
                for (int row=0; row<j+2; ++row)
                    inv[j][row] = new FT[row+1];
            }
        
            for (int i=0; i<d; ++i)
                c[i] = FT(0);
            v_basis[0] = FT(1);
        }
        
        
        ~Optimisation_sphere_d ()
        {
            if (d != -1)
               destroy();
        }
        
        
        void destroy ()
        {
            for (int j=0; j<d+1; ++j) {
                for (int row=0; row<j+2; ++row)
                    delete[] inv[j][row];
                delete[] inv[j];
                delete[] q[j];
            }
            delete[] c;
            delete[] v;
            delete[] x;
            delete[] v_basis;
            delete[] inv;
            delete[] q;
        }
        
        
        void set_size (int ambient_dimension)
        {
            if (d != -1)
                destroy();
            if (ambient_dimension != -1)
                init(ambient_dimension);
            else {
                d = -1;
                m = 0;
                s = 0;
            }
        }
        
        
        void push (const PT& p)
        {
            // store q_m = p by copying its cartesian coordinates into q[m]
            It i(tco.access_coordinates_begin_d_object()(p)); FT *o;
            for (o=q[m]; o<q[m]+d; *(o++)=*(i++));
        
            // update v_basis by appending q_m^Tq_m
            v_basis[m+1] = prod(q[m],q[m],d);
        
            if (m==0)
            {
                // set up A^{-1}_{B^0} directly
                FT** M = inv[0];
                M[0][0] = -FT_(2)*v_basis[1];
                M[1][0] = FT_(1);
                M[1][1] = FT_(0);
            } else {
                // set up vector v by computing 2q_j^T q_m, j=0,...,m-1
                v[0] = FT_(1);
                for (int j=0; j<m; ++j)
                    v[j+1] = FT_(2)*prod(q[j],q[m],d);
        
                // compute a_0,...,a_m
                multiply (m-1, v, x);               // x[j]=a_j, j=0,...,m
        
                // compute z
                FT z = FT_(2)*v_basis[m+1] - prod(v,x,m+1);
                CGAL_optimisation_assertion (!CGAL_NTS is_zero (z));
                FT inv_z = FT_(1)/z;
        
                // set up A^{-1}_{B^m}
                FT** M = inv[m-1];          // A^{-1}_B, old matrix
                FT** M_new = inv[m];        // A^{-1}_{B'}, new matrix
        
                // first m rows
                int row, col;
                for (row=0; row<m+1; ++row)
                    for (col=0; col<row+1; ++col)
                        M_new [row][col] = M[row][col] + x[row]*x[col]*inv_z;
        
                // last row
                for (col=0; col<m+1; ++col)
                    M_new [m+1][col] = -x[col]*inv_z;
                M_new [m+1][m+1] = inv_z;
            }
            s = ++m;
            compute_c_and_sqr_r();  // side effect: sets x
        }
        
        
        void pop ()
        {
            --m;
        }
        
        
        FT excess (const PT& p) const
        {
            // compute (c-p)^2
            FT sqr_dist (FT(0));
            It i(tco.access_coordinates_begin_d_object()(p));
            FT *j;
            for (j=c; j<c+d; ++i, ++j)
                sqr_dist += CGAL_NTS square(*i-*j);
            return sqr_dist - sqr_r;
         }
        
        
        
        PT center () const
        {
             return tco.construct_point_d_object()(d, c, c+d);
        }
        
        FT squared_radius () const
        {
             return sqr_r;
        }
        
        int number_of_support_points () const
        {
             return s;
        }
        
        int size_of_basis () const
        {
             return m;
        }
        
        
      bool is_valid (bool verbose = false, int /* level */ = true) const
        {
            Verbose_ostream verr (verbose);
            for (int j=1; j<m+1; ++j)
                if (!CGAL_NTS is_positive (x[j]))
                    return (_optimisation_is_valid_fail
                        (verr, "center not in convex hull of support points"));
            return (true);
        }
        
        
    private:
        void multiply (int j, const FT* vec, FT* res)
        {
            FT** M = inv[j];
            for (int row=0; row<j+2; ++row) {
                res[row] = prod(M[row],vec,row+1);
                for (int col = row+1; col<j+2; ++col)
                    res[row] += M[col][row]*vec[col];
            }
        }
        
        
        void compute_c_and_sqr_r ()
        {
            multiply (m-1, v_basis, x);
        
            for (int i=0; i<d; ++i) c[i] = FT(0);
            for (int j=0; j<m; ++j) {
                FT l = x[j+1], *q_j = q[j];
                for (int i=0; i<d; ++i)
                    c[i] += l*q_j[i];
            }
            sqr_r = x[0] + prod(c,c,d);
        }
        
        
        FT prod (const FT* v1, const FT* v2, int k) const
        {
            FT res(FT(0));
            for (const FT *i=v1, *j=v2; i<v1+k; res += (*(i++))*(*(j++)));
            return res;
        }
        
        
    };