treediam.h

任意给定三维空间的点集

/*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
 * TreeDiam.h -
 *     Implementation of algorithms for computing the diameter 
 * using tree heirarchies.
 * 
 * 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  __TREEDIAM__H
#define  __TREEDIAM__H

class  heap_pairs_2d;
class  FSPairArray_2d;

class TreeDiamAlg2d
{
private:
    FS2dTree  tree;
    //double  diam;
    PointPair2d   pair_diam;
    int  threshold_brute;

public:
    TreeDiamAlg2d( const ArrPoint2dPtr  & arr ) {
        tree.init( arr );
        //diam = 0;
        pair_diam.init( *(arr[ 0 ]) );
        threshold_brute = 40;
    }

    const PointPair2d  & getDiameter() const {
        return  pair_diam;
    }

    void  term() {
        tree.term();
    }
    int  nodes_number() const {
        return  tree.nodes_number(); 
    }

    void  addPairHeap( heap_pairs_2d  & heap,
                       FS2dTreeNode  * left,
                       FS2dTreeNode  * right );
    void  split_pair( FS2dPair  & pair,
                      heap_pairs_2d  & heap, double  eps );
    void  compute_by_heap( double  eps );

    double  diameter() {
        return  pair_diam.distance;
    }
};

class  heap_pairs;
//class  heap_pairs_err;
class  FSPairArray;

class TreeDiamAlg
{
private:
    FSTree  tree;
    //double  diam;
    PointPair   pair_diam;
    int  threshold_brute;

public:
    TreeDiamAlg( const ArrPoint3d  & arr ) {
        tree.init( arr );
        //diam = 0;
        pair_diam.init( arr[ 0 ] );
        threshold_brute = 40;
    }

    const PointPair  & getDiameter() const {
        return  pair_diam;
    }

    int  nodes_number() const {
        return  tree.nodes_number(); 
    }

    void  term() {
        tree.term();
    }
    void  addPairHeap( heap_pairs  & heap,
                       FSTreeNode  * left,
                       FSTreeNode  * right );
    void  addPairHeapWSPD( heap_pairs  & heap,
                           FSTreeNode  * left,
                           FSTreeNode  * right,
                           double  eps,
                           int  & count_self_pairs );
                           
    void  addPair( FSPairArray  & queue_out, 
                   FSTreeNode  * left,
                   FSTreeNode  * right );
    void  split_level( FSPairArray  & queue_in,
                       FSPairArray  & queue_out, double  eps );
    void  split_pair_wspd( FSPair  & pair,
                          heap_pairs  & heap, double  eps,
                           int  & count_self_pairs );
    void  split_pair_wspd_one_side( FSPair  & pair,
                                    heap_pairs  & heap, 
                                    double  eps,
                                    int  & count_self_pairs );
    void  split_pair( FSPair  & pair,
                      heap_pairs  & heap, double  eps );
    void  split_pair_dir( FSPair  & pair,
                          heap_pairs  & heap, 
                          double  eps,
                          double  threshold );
    
    void  compute_by_level( double  eps );
    void  compute_by_heap( double  eps );
    void  compute_by_heap_wspd( double  eps );
    void  compute_by_dir( double  eps );

    double  diameter() {
        return  pair_diam.distance;
    }


};

//----------------------------------------------------------------------
// fair split tree that uses pointers
//----------------------------------------------------------------------
class  heap_pairs_p;
class  FSPPairArray;


class TreeDiamPAlg
{
private:
    FSPTree  tree;
    //double  diam;
    PointPair   pair_diam;
    int  points_num;
    int  threshold_brute;

public:
    TreeDiamPAlg( const ArrPoint3d  & arr ) {
        tree.init( arr );
        //diam = 0;
        pair_diam.init( arr[ 0 ] );
        points_num = arr.size();
        threshold_brute = 40;
    }

    void  term() {
        tree.term();
    }
    
    int  size() const {
        return  points_num;
    }
    const PointPair  & getDiameter() const {
        return  pair_diam;
    }

    int  nodes_number() const {
        return  tree.nodes_number(); 
    }

    void  addPairHeap( heap_pairs_p  & heap,
                       FSPTreeNode  * left,
                       FSPTreeNode  * right );

    void  addPair( FSPPairArray  & queue_out, 
                   FSPTreeNode  * left,
                   FSPTreeNode  * right );
    void  split_level( FSPPairArray  & queue_in,
                       FSPPairArray  & queue_out, double  eps );
    void  split_pair( FSPPair  & pair,
                      heap_pairs_p  & heap, double  eps );
    void  split_pair_dir( FSPPair  & pair,
                          heap_pairs_p  & heap, 
                          double  eps,
                          double  threshold );
    
    void  compute_by_level( double  eps );
    void  compute_by_heap( double  eps );

    double  diameter() {
        return  pair_diam.distance;
    }
};

real   brute_diameter( const ArrPoint3d  & arr,
                       PointPair  & diam );
real   brute_diameter_local_bi( const ArrPoint3d  & arr,
                                int  a_start,
                                int  a_end,
                                int  b_start,
                                int  b_end,
                                PointPair  & diam );
real   brute_diameter_local( const ArrPoint3d  & arr,
                             int  start,
                             int  end, 
                             PointPair  & out );
real   brute_diameter_local( const ArrPoint3d  & arr,
                             PointPair  & out );
void  read_poly_file( ArrPoint3d  & arr,
                      char  * file_name );


void  computeExtremePairDir( const ArrPoint3d  & arr,
                             const Point3d  & dir,
                             PointPair  & pp
                             );
void  computeExtremePairDir2d( const ArrPoint2dPtr  & arr,
                               const Point2d  & dir,
                               PointPair2d  & pp
                               );
void  computeExtremePair( const ArrPoint3d  & arr,
                          int  dim, PointPair  & pp );
void  computeExtremePairAllDim( const ArrPoint3d  & arr,
                                PointPair  & pp0,
                                PointPair  & pp1,
                                PointPair  & pp2
                                );
void  computeExtremePairDirs( const ArrPoint3d  & arr,
                              const Point3d  & dir_0,
                              const Point3d  & dir_1,
                              const Point3d  & dir_2,
                              PointPair  & pp_0,
                              PointPair  & pp_1,
                              PointPair  & pp_2
                              );


#else   /* __TREEDIAM__H */
#error  Header file TreeDiam.h included twice
#endif  /* __TREEDIAM__H */

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