Image Component Library (ICL)
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
KDTree.h
Go to the documentation of this file.
00001 /********************************************************************
00002 **                Image Component Library (ICL)                    **
00003 **                                                                 **
00004 ** Copyright (C) 2006-2013 CITEC, University of Bielefeld          **
00005 **                         Neuroinformatics Group                  **
00006 ** Website: www.iclcv.org and                                      **
00007 **          http://opensource.cit-ec.de/projects/icl               **
00008 **                                                                 **
00009 ** File   : ICLMath/src/ICLMath/KDTree.h                           **
00010 ** Module : ICLMath                                                **
00011 ** Authors: Christian Groszewski                                   **
00012 **                                                                 **
00013 **                                                                 **
00014 ** GNU LESSER GENERAL PUBLIC LICENSE                               **
00015 ** This file may be used under the terms of the GNU Lesser General **
00016 ** Public License version 3.0 as published by the                  **
00017 **                                                                 **
00018 ** Free Software Foundation and appearing in the file LICENSE.LGPL **
00019 ** included in the packaging of this file.  Please review the      **
00020 ** following information to ensure the license requirements will   **
00021 ** be met: http://www.gnu.org/licenses/lgpl-3.0.txt                **
00022 **                                                                 **
00023 ** The development of this software was supported by the           **
00024 ** Excellence Cluster EXC 277 Cognitive Interaction Technology.    **
00025 ** The Excellence Cluster EXC 277 is a grant of the Deutsche       **
00026 ** Forschungsgemeinschaft (DFG) in the context of the German       **
00027 ** Excellence Initiative.                                          **
00028 **                                                                 **
00029 ********************************************************************/
00030 #pragma once
00031 
00032 #include <ICLUtils/CompatMacros.h>
00033 #include <ICLMath/DynMatrix.h>
00034 #include <ICLUtils/Macros.h>
00035 #include <ICLUtils/BasicTypes.h>
00036 #include <ICLUtils/Uncopyable.h>
00037 #include <vector>
00038 
00039 namespace icl{
00040   namespace math{
00041   
00043 
00051     class ICLMath_API KDTree : public utils::Uncopyable{
00052       private:
00054       struct Node{
00056         Node *left;
00058         Node *right;
00060         DynMatrix<icl64f> *point;
00062         double median;
00063         
00065         inline Node():left(0),right(0),point(0),median(0.0){}
00066         
00068         inline ~Node(){
00069           if(right != 0){
00070             delete right;
00071             right = 0;
00072           }
00073           if(left != 0){
00074             delete left;
00075             left = 0;
00076           }
00077           
00078         }
00079       };
00080       
00082       Node root;
00083       
00085       void print(Node *node);
00087       void buildTree(std::vector<math::DynMatrix<icl64f> > &list,unsigned int depth, Node *node);
00089       void buildTree(std::vector<math::DynMatrix<icl64f> *> &list,unsigned int depth, Node *node);
00091       void sortList(std::vector<math::DynMatrix<icl64f> > &list, unsigned int dim);
00093       void sortList(std::vector<math::DynMatrix<icl64f>* > &list, unsigned int dim);
00095       void releaseTree();
00096       
00097       public :
00099 
00102       KDTree(std::vector<math::DynMatrix<icl64f> > &list);
00103   
00105 
00108       KDTree(std::vector<math::DynMatrix<icl64f>* > &list);
00109   
00111 
00113       KDTree(){}
00114      
00116       ~KDTree();
00117       
00119 
00122       inline void buildTree(std::vector<math::DynMatrix<icl64f> *> &list){
00123         releaseTree();
00124         buildTree(list,0,&root);
00125       }
00126       
00128 
00131       inline void buildTree(std::vector<math::DynMatrix<icl64f> > &list){
00132         releaseTree();
00133         buildTree(list,0,&root);
00134       }
00135       
00137       void print();
00138       
00140 
00142       math::DynMatrix<icl64f>* nearestNeighbour(const math::DynMatrix<icl64f> &point);
00143       
00145 
00147       math::DynMatrix<icl64f>* nearestNeighbour(const math::DynMatrix<icl64f> *point);
00148       
00149     };
00150   } // namespace utils
00151 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines