algorithm.h

任意给定三维空间的点集

/*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
 * algorithm.h -
 *     A wrapper for a diameter calculating algorithm.
 * 
 * Copyright 2000 Sariel Har-Peled ([e-mail])
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation; either version 2, or (at your option) any
 * later version.
 * 
 * Code is based on the paper:
 *   A Practical Approach for Computing the Diameter of a Point-Set.
 *   Sariel Har-Peled (http://www.uiuc.edu/~sariel)
\*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/

#ifndef  __ALGORITHM__H
#define  __ALGORITHM__H

class  TreeDiamAlg;
class  TreeDiamPAlg;

class   DiameterAlgorithm
{
public:
    PointPair  diam;
    double  time;

    virtual ~DiameterAlgorithm() {}

    virtual char   * getID() = 0;
    virtual void   compute( const ArrPoint3d  & arr ) = 0;
    virtual void   dump();
    virtual void   dump_to_file( FILE  * fl );
    double  eps;

    //void   dump();
};




class   BruteDiameter : public  DiameterAlgorithm
{
public:
    static DiameterAlgorithm  * CreateAndCompute( ArrPoint3d  & arr );
    char   * getID();

    void   compute( const ArrPoint3d  & arr );
};

class   DiameterAPBBox : public  DiameterAlgorithm
{
public:
    static DiameterAlgorithm  * CreateAndCompute( ArrPoint3d  & arr );
    char   * getID();

    void   compute( const ArrPoint3d  & arr );
};


class   BruteDiameterLocal : public  DiameterAlgorithm
{
public:
    static DiameterAlgorithm  * CreateAndCompute( ArrPoint3d  & arr );

    char   * getID();

    void   compute( const ArrPoint3d  & arr );
};


class   QuadDiameterByLevel : public  DiameterAlgorithm
{
public:
    TreeDiamAlg  * p_alg;

    static DiameterAlgorithm  * CreateAndCompute( ArrPoint3d  & arr,
                                                  double  eps );
    char   * getID();

    void   compute( const ArrPoint3d  & arr );
};
class   QuadDiameterPtrByLevel : public  DiameterAlgorithm
{
public:
    TreeDiamPAlg  * p_alg;

    static DiameterAlgorithm  * CreateAndCompute( ArrPoint3d  & arr,
                                                  double  eps );
    char   * getID();

    void   compute( const ArrPoint3d  & arr );
};

class   QuadDiameterByDir : public  DiameterAlgorithm
{
public:
    TreeDiamAlg  * p_alg;

    static DiameterAlgorithm  * CreateAndCompute( ArrPoint3d  & arr,
                                                  double  eps );
    char   * getID();

    void   compute( const ArrPoint3d  & arr );
};

class   QuadDiameterByHeap : public  DiameterAlgorithm
{
public:
    TreeDiamAlg  * p_alg;

    static DiameterAlgorithm  * CreateAndCompute( ArrPoint3d  & arr,
                                                  double  eps );
    char   * getID();
    void   compute( const ArrPoint3d  & arr );
};

class   QuadDiameterByGPtrHeap : public  DiameterAlgorithm
{
public:
    static DiameterAlgorithm  * CreateAndCompute( ArrPoint3d  & arr,
                                                  double  eps );
    char   * getID();
    void   compute( const ArrPoint3d  & arr );
};


class   QuadDiameterByGPtrHeapUDMSample : public  DiameterAlgorithm
{
public:
    static DiameterAlgorithm  * CreateAndCompute( ArrPoint3d  & arr,
                                                  double  eps );
    char   * getID();
    void   compute( const ArrPoint3d  & arr );
};


class   QuadDiameterByHeapWSPD : public  DiameterAlgorithm
{
public:
    TreeDiamAlg  * p_alg;

    static DiameterAlgorithm  * CreateAndCompute( ArrPoint3d  & arr,
                                                  double  eps );
    char   * getID();
    void   compute( const ArrPoint3d  & arr );
};


inline void  commatify( char  * str, int  num )
{
    if  ( num < 1000 ) {
        sprintf( str, "%d", num );
        return;
    }
    commatify( str, num / 1000 );
    strcat( str, "," );

    sprintf( str + strlen( str ), "%03d", num % 1000 );
}


class  TesterDiamAlg
{
private:
    Array<DiameterAlgorithm *>  arr;

public:
    int  points_num;

    void  init() {
        arr.init( 10, 45435 );
    }
    void  push(DiameterAlgorithm  * res ) {
        arr.pushx( res );
    }
    void  sort() {
        for  ( int  ind = 0; ind < arr.size() - 1; ind++ )
            for  ( int  jnd = ind + 1; jnd < arr.size(); jnd++ ) {
                if  ( arr[ ind ]->eps > arr[ jnd ]->eps ) {
                    exchange( arr[ ind ], arr[ jnd ] );
                    continue;
                }
                if  ( ( arr[ ind ]->eps == arr[ jnd ]->eps )
                      &&  ( arr[ ind ]->time > arr[ jnd ]->time ) ) {
                    exchange( arr[ ind ], arr[ jnd ] );
                    continue;
                }
            }
    }

    void  dump_to_file( const char  * file_name,
                        const char  * description ) {
        FILE  * fl;
        char  line[ 100 ];

        fl = safe_fopen( file_name, "wt" );

        fprintf( fl, "%s\n", description );
        commatify( line, points_num );
        fprintf( fl, "%s\n", line );
        for  ( int  ind = 0; ind < arr.size(); ind++ ) 
            arr[ ind ]->dump_to_file( fl );
            
        fclose( fl );
    }

    void  dump() {
        //sort();
        for  ( int  ind = 0; ind < arr.size(); ind++ ) {
            arr[ ind ]->dump();

            //printf( "-------------------------------------\n" );
            //printf( "Algorithm: %-40s  %10.3g   %10.3g\n",                   
            //        arr[ ind ]->getID(),
            //        arr[ ind ]->time,
            //        arr[ ind ]->diam.distance );
            
        }
   }
};


class   DiameterDirections : public  DiameterAlgorithm
{
public:
    static DiameterAlgorithm  * CreateAndCompute( ArrPoint3d  & arr,
                                                  double  eps );

    char   * getID();

    void   compute( const ArrPoint3d  & arr );
};


class   DiameterGrid : public  DiameterAlgorithm
{
public:
    static DiameterAlgorithm  * CreateAndCompute( ArrPoint3d  & arr,
                                                  double  eps );

    char   * getID();

    void   compute( const ArrPoint3d  & arr );
};


class   DiameterGridQuadDir : public  DiameterAlgorithm
{
public:
    static DiameterAlgorithm  * CreateAndCompute( ArrPoint3d  & arr,
                                                  double  eps );

    char   * getID();

    void   compute( const ArrPoint3d  & arr );
};


class   DiameterChan : public  DiameterAlgorithm
{
public:
    static DiameterAlgorithm  * CreateAndCompute( ArrPoint3d  & arr,
                                                  double  eps );

    char   * getID();

    void   compute( const ArrPoint3d  & arr );
};

class   DiameterModChan : public  DiameterAlgorithm
{
public:
    static DiameterAlgorithm  * CreateAndCompute( ArrPoint3d  & arr,
                                                  double  eps );

    char   * getID();

    void   compute( const ArrPoint3d  & arr );
};


class   DiameterPCA : public  DiameterAlgorithm
{
public:
    static DiameterAlgorithm  * CreateAndCompute( ArrPoint3d  & arr );

    char   * getID();

    void   compute( const ArrPoint3d  & arr );
};


class   DiameterMassPCA : public  DiameterAlgorithm
{
public:
    static DiameterAlgorithm  * CreateAndCompute( ArrPoint3d  & arr );

    char   * getID();

    void   compute( const ArrPoint3d  & arr );
};


void  tester( const char  * file_name, const char  * description );
PointPair  * tester_inner( ArrPoint3d   * p_arr,
                           const char  * description );
void   compute_mvbb( const ArrPoint3d  & arr );


#else   /* __ALGORITHM__H */
#error  Header file algorithm.h included twice
#endif  /* __ALGORITHM__H */

/* algorithm.h - End of File ------------------------------------------*/