Image Component Library (ICL)
|
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.GPL ** 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 <ICLMath/DynMatrix.h> 00033 #include <ICLUtils/Macros.h> 00034 #include <ICLUtils/BasicTypes.h> 00035 #include <ICLUtils/Uncopyable.h> 00036 #include <vector> 00037 00038 namespace icl{ 00039 namespace math{ 00040 00042 00050 class KDTree : public utils::Uncopyable{ 00051 private: 00053 struct Node{ 00055 Node *left; 00057 Node *right; 00059 DynMatrix<icl64f> *point; 00061 double median; 00062 00064 inline Node():left(0),right(0),point(0),median(0.0){} 00065 00067 inline ~Node(){ 00068 if(right != 0){ 00069 delete right; 00070 right = 0; 00071 } 00072 if(left != 0){ 00073 delete left; 00074 left = 0; 00075 } 00076 00077 } 00078 }; 00079 00081 Node root; 00082 00084 void print(Node *node); 00086 void buildTree(std::vector<math::DynMatrix<icl64f> > &list,unsigned int depth, Node *node); 00088 void buildTree(std::vector<math::DynMatrix<icl64f> *> &list,unsigned int depth, Node *node); 00090 void sortList(std::vector<math::DynMatrix<icl64f> > &list, unsigned int dim); 00092 void sortList(std::vector<math::DynMatrix<icl64f>* > &list, unsigned int dim); 00094 void releaseTree(); 00095 00096 public : 00098 00101 KDTree(std::vector<math::DynMatrix<icl64f> > &list); 00102 00104 00107 KDTree(std::vector<math::DynMatrix<icl64f>* > &list); 00108 00110 00112 KDTree(){} 00113 00115 ~KDTree(); 00116 00118 00121 inline void buildTree(std::vector<math::DynMatrix<icl64f> *> &list){ 00122 releaseTree(); 00123 buildTree(list,0,&root); 00124 } 00125 00127 00130 inline void buildTree(std::vector<math::DynMatrix<icl64f> > &list){ 00131 releaseTree(); 00132 buildTree(list,0,&root); 00133 } 00134 00136 void print(); 00137 00139 00141 math::DynMatrix<icl64f>* nearestNeighbour(const math::DynMatrix<icl64f> &point); 00142 00144 00146 math::DynMatrix<icl64f>* nearestNeighbour(const math::DynMatrix<icl64f> *point); 00147 00148 }; 00149 } // namespace utils 00150 }