mitkKdTree.h

/*=========================================================================

  Program:   3DMed
  Date:      $Date: 2014-02-25 18:30:00 +0800 $
  Version:   $Version: 4.6.0 $
  Copyright: MIPG, Institute of Automation, Chinese Academy of Sciences

=========================================================================*/


#ifndef __mitkKdTree_h
#define __mitkKdTree_h

#include "mitkRegistrationIncludes.h"
#include "mitkObject.h"
#include "mitkPointSet.h"


class mitkKdTreeNode;
class mitk_kd_heap_entry;

class MITK_REGISTRATION_API mitkKdTree
{
public:
    mitkKdTree(mitkPointSet* points, int points_per_leaf=4 );

    ~mitkKdTree();

    void GetPointsKNearest(double* queryPoint, int k, vector<int>& closestIndices);

    void GetPointsInBoundingBox(mitkBoundingBox<double>& box, vector<int>& indices_in_box);

    void GetPointsInRadius(double* query_point, double radius, vector<int>& indices_in_radius);

    void SetFlagUseHeap(bool flag) {m_FlagUseHeap = flag;}

protected:
    mitkBoundingBox<double> Build_inner_box(const vector<int>* indices);

    mitkKdTreeNode* Build_kd_tree(int points_per_leaf,mitkBoundingBox<double>& outer_box,int depth,vector<int>* indices );

    int Find_greatest_variation(const vector<int>* indices);

    void Free_kd_tree(mitkKdTreeNode* p);

    void K_nearest_with_stack(double* query_point, int k, mitkKdTreeNode* root, vector<int>& closestIndices,
        vector<double>& sq_distances, int& num_found);

    void K_nearest_with_heap(double* query_point, int k,mitkKdTreeNode* root, vector<int>& closest_indices,
        vector<double>& sq_distances, int& num_found,int max_leaves);

    void Update_closest(double* query_point, int k, mitkKdTreeNode* p, vector<int>& closestIndices,
        vector<double>& sq_distances, int& num_found );

    bool Bounded_at_leaf(double* query_point, int k, mitkKdTreeNode* current, vector<double>& sq_distances, int& num_found );

    void Points_in_bounding_box(mitkKdTreeNode* current, mitkBoundingBox<double>& box, vector<int>& indices_in_box);

    void Report_all_in_subtree(mitkKdTreeNode* current, vector<int>& indices);

    mitkKdTreeNode* m_RootNode;
    mitkPointSet*   m_Points;

    unsigned int    m_PointSetDimension;
    int             m_Leaf_count;
    int             m_Leaf_examined;
    int             m_Internal_count;
    int             m_Internal_examined;

    bool            m_FlagUseHeap;
    

private:
    mitkKdTree(const mitkKdTree&);
    void operator=(const mitkKdTree&);
};

class mitkKdTreeNode
{
public:
    //for internal node
    mitkKdTreeNode(mitkBoundingBox<double>& outerBox, mitkBoundingBox<double>& innerBox, unsigned int depth);

    //for leaf node
    mitkKdTreeNode(mitkBoundingBox<double>& outerBox, mitkBoundingBox<double>& innerBox, unsigned int depth, vector<int>* pointsInNode);

    mitkBoundingBox<double>     m_OuterBoundingBox;
    mitkBoundingBox<double>     m_InnerBoundingBox;
    vector<int>*                m_PointsInNode;
    unsigned int                m_Depth;
    mitkKdTreeNode*             m_LeftNode;
    mitkKdTreeNode*             m_RightNode;
};

class mitk_kd_heap_entry
{
    public:
        mitk_kd_heap_entry() {}
        //~mitk_kd_heap_entry();
        mitk_kd_heap_entry( double dist, mitkKdTreeNode* p ): dist_(dist), p_(p) {}
        bool operator< ( const mitk_kd_heap_entry& right ) const { return right.dist_ < this->dist_; }

        double dist_;
        mitkKdTreeNode* p_;
};


//#define DEFINED_mitkKdTree



#endif

---