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.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 }