KDTree.h

Go to the documentation of this file.

/********************************************************************
**                Image Component Library (ICL)                    **
**                                                                 **
** Copyright (C) 2006-2013 CITEC, University of Bielefeld          **
**                         Neuroinformatics Group                  **
** Website: www.iclcv.org and                                      **
**          http://opensource.cit-ec.de/projects/icl               **
**                                                                 **
** File   : ICLMath/src/ICLMath/KDTree.h                           **
** Module : ICLMath                                                **
** Authors: Christian Groszewski                                   **
**                                                                 **
**                                                                 **
** GNU LESSER GENERAL PUBLIC LICENSE                               **
** This file may be used under the terms of the GNU Lesser General **
** Public License version 3.0 as published by the                  **
**                                                                 **
** Free Software Foundation and appearing in the file LICENSE.LGPL **
** included in the packaging of this file.  Please review the      **
** following information to ensure the license requirements will   **
** be met: http://www.gnu.org/licenses/lgpl-3.0.txt                **
**                                                                 **
** The development of this software was supported by the           **
** Excellence Cluster EXC 277 Cognitive Interaction Technology.    **
** The Excellence Cluster EXC 277 is a grant of the Deutsche       **
** Forschungsgemeinschaft (DFG) in the context of the German       **
** Excellence Initiative.                                          **
**                                                                 **
********************************************************************/
#pragma once

#include <ICLUtils/CompatMacros.h>
#include <ICLMath/DynMatrix.h>
#include <ICLUtils/Macros.h>
#include <ICLUtils/BasicTypes.h>
#include <ICLUtils/Uncopyable.h>
#include <vector>

namespace icl{
  namespace math{


    class ICLMath_API KDTree : public utils::Uncopyable{
      private:
      struct Node{
        Node *left;
        Node *right;
        DynMatrix<icl64f> *point;
        double median;

        inline Node():left(0),right(0),point(0),median(0.0){}

        inline ~Node(){
          if(right != 0){
            delete right;
            right = 0;
          }
          if(left != 0){
            delete left;
            left = 0;
          }

        }
      };

      Node root;

      void print(Node *node);
      void buildTree(std::vector<math::DynMatrix<icl64f> > &list,unsigned int depth, Node *node);
      void buildTree(std::vector<math::DynMatrix<icl64f> *> &list,unsigned int depth, Node *node);
      void sortList(std::vector<math::DynMatrix<icl64f> > &list, unsigned int dim);
      void sortList(std::vector<math::DynMatrix<icl64f>* > &list, unsigned int dim);
      void releaseTree();

      public :

      KDTree(std::vector<math::DynMatrix<icl64f> > &list);


      KDTree(std::vector<math::DynMatrix<icl64f>* > &list);


      KDTree(){}

      ~KDTree();


      inline void buildTree(std::vector<math::DynMatrix<icl64f> *> &list){
        releaseTree();
        buildTree(list,0,&root);
      }


      inline void buildTree(std::vector<math::DynMatrix<icl64f> > &list){
        releaseTree();
        buildTree(list,0,&root);
      }

      void print();


      math::DynMatrix<icl64f>* nearestNeighbour(const math::DynMatrix<icl64f> &point);


      math::DynMatrix<icl64f>* nearestNeighbour(const math::DynMatrix<icl64f> *point);

    };
  } // namespace utils
}