KDTree.h

Go to the documentation of this file.
00001 /*
00002 * Copyright (C) 2007-2008 Anael Orlinski
00003 *
00004 * This file is part of Panomatic.
00005 *
00006 * Panomatic is free software; you can redistribute it and/or modify
00007 * it under the terms of the GNU General Public License as published by
00008 * the Free Software Foundation; either version 2 of the License, or
00009 * (at your option) any later version.
00010 *
00011 * Panomatic is distributed in the hope that it will be useful,
00012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 * GNU General Public License for more details.
00015 *
00016 * You should have received a copy of the GNU General Public License
00017 * along with Panomatic; if not, write to the Free Software
00018 * <http://www.gnu.org/licenses/>.
00019 */
00020 
00021 #ifndef __kdtree_h
00022 #define __kdtree_h
00023 
00024 #include <vector>
00025 #include <list>
00026 #include <functional>  // for std::greater
00027 
00028 #include <localfeatures/BoundedSet.h>
00029 
00030 // implementation of a kdtree is based on this book
00031 // A. Moore, An introductory tutorial on kd-trees,
00032 // tech. report Technical Report No. 209, Computer Laboratory,
00033 // University of Cambridge, Robotics Institute, Carnegie Mellon University, 1991.
00034 
00035 namespace KDTreeSpace
00036 {
00037 
00038 template <class KE>                                     class BestMatch;
00039 template <class KE, class TYPE>         class HyperRectangle;
00040 template <class KE, class VTYPE>        class QueueEntry;
00041 template <class KE, class VTYPE>        class KDTree;
00042 
00043 template <class VTYPE>
00044 class KDTreeElemInterface
00045 {
00046     virtual VTYPE& getVectorElem (int iPos) const = 0;  // access to the vector elements.
00047 };
00048 
00049 /******************************************************************************
00050 * BestMatch
00051 ******************************************************************************/
00052 template <class KE>
00053 class BestMatch
00054 {
00055 public:
00056     BestMatch(const KE* iMatch, double iDistance) : _distance(iDistance), _match(iMatch) {}
00057     double      _distance;                      // square distance from target
00058     const KE*   _match;
00059 };
00060 
00061 /******************************************************************************
00062 * HyperRectangle
00063 ******************************************************************************/
00064 template <class KE, class TYPE>
00065 class HyperRectangle
00066 {
00067 public:
00068     HyperRectangle();
00069     explicit HyperRectangle(int iDim);
00070     HyperRectangle(HyperRectangle& iOther);
00071     bool split(HyperRectangle& oLeft, HyperRectangle& oRight, int iSplitDim, TYPE iSplitVal);
00072     double calcSqDistance (const KE& iTarget);
00073     bool hasHyperSphereIntersect(const KE& iTarget, double iSqDistance);
00074     void display();
00075     bool isTargetIn (const KE& iTarget);
00076 
00077     int _dim;
00078     std::vector<TYPE> _leftTop, _rightBottom;
00079 };
00080 
00081 /******************************************************************************
00082 * QueueEntry
00083 ******************************************************************************/
00084 template <class KE, class VTYPE>
00085 class QueueEntry
00086 {
00087 public:
00088     QueueEntry(HyperRectangle<KE, VTYPE> & iHR, KDTree<KE, VTYPE> * iKDTree, double iDistance) :
00089         _dist(iDistance), _HR(iHR), _kdTree(iKDTree) {}
00090     double _dist;                                       // the distance from target to HyperRectangle
00091     HyperRectangle<KE, VTYPE> & _HR;    // reference to the hyperrectangle
00092     KDTree<KE, VTYPE> * _kdTree;
00093 
00094     // operator < to be put in a regular set.
00095     //bool operator < (const QueueEntry<KE> & iOther) { return (_dist < iOther._dist); }
00096 
00097 };
00098 
00099 /******************************************************************************
00100 * KDTree
00101 ******************************************************************************/
00102 template <class KE, class VTYPE>
00103 class KDTree
00104 {
00105 public:
00106     typedef typename std::vector<KE>                                                                            ItemVector_t;
00107     typedef typename std::vector<KE>::const_iterator                                            ItemVectorIt_t;
00108     typedef typename std::vector<const KE*>                                                             ItemPtrVector_t;
00109     typedef typename std::vector<const KE*>::const_iterator                             ItemPtrVectorIt_t;
00110     typedef typename std::set<BestMatch<KE>, std::greater<BestMatch<KE> > >     BestMatchSet_t;
00111     typedef lfeat::bounded_set<BestMatch<KE>, std::greater<BestMatch<KE> > >            BestMatchLimitedSet_t;
00112     typedef typename std::list<QueueEntry<KE, VTYPE> >                                          QueueEntryList_t;
00113 
00114     // constructor for the root.
00115     KDTree(const ItemVector_t& iElemsList, int iDimensions);
00116 
00117     // recursive construct.
00118     KDTree(const ItemPtrVector_t& iElemsPtrList, int iDimensions);
00119 
00120     // Destructor
00121     ~KDTree();
00122 
00123     BestMatchSet_t              getNearestNeighboursBBF(        const KE& iTarget,
00124             int iNbBestMatches,
00125             int iNbSearchSteps);
00126 
00127     // calc the square distance between 2 entries.
00128     double                              calcSqDist(const KE* i1, const KE* i2);
00129 
00130 private:
00131     void                                init(const ItemPtrVector_t& iElemsPtrList);                     // prepare the structure.
00132     ItemPtrVectorIt_t   choosePivot(const ItemPtrVector_t& iElemsPtrList);              // choose the pivot point
00133     void                                recurseNearestNeighboursBBF(const KE& iTarget,
00134             HyperRectangle<KE, VTYPE> & iHR,
00135             BestMatchLimitedSet_t& ioBestMatches,
00136             QueueEntryList_t& ioSearchQueue,
00137             int& ioRemainingUnqueues);
00138     // dimension of the vectors
00139     int                                 _dims;
00140 
00141     // The element stored on this leaf
00142     const KE*                   _pivot;
00143     int                                 _splitDim;
00144 
00145     // The left and the right kd-subtree.
00146     KDTree<KE, VTYPE> *                 _leftKD;
00147     KDTree<KE, VTYPE> *                 _rightKD;
00148 
00149 };
00150 
00151 } // namespace KDTree
00152 
00153 #endif

Generated on 2 Aug 2015 for Hugintrunk by  doxygen 1.4.7