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 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00019 */
00020 
00021 #ifndef __kdtree_h
00022 #define __kdtree_h
00023 
00024 #include <vector>
00025 #include <list>
00026 
00027 #include <localfeatures/BoundedSet.h>
00028 
00029 // implementation of a kdtree is based on this book
00030 // A. Moore, An introductory tutorial on kd-trees,
00031 // tech. report Technical Report No. 209, Computer Laboratory,
00032 // University of Cambridge, Robotics Institute, Carnegie Mellon University, 1991.
00033 
00034 namespace KDTreeSpace
00035 {
00036 
00037 template <class KE>                                     class BestMatch;
00038 template <class KE, class TYPE>         class HyperRectangle;
00039 template <class KE, class VTYPE>        class QueueEntry;
00040 template <class KE, class VTYPE>        class KDTree;
00041 
00042 template <class VTYPE>
00043 class KDTreeElemInterface
00044 {
00045     virtual VTYPE& getVectorElem (int iPos) const = 0;  // access to the vector elements.
00046 };
00047 
00048 /******************************************************************************
00049 * BestMatch
00050 ******************************************************************************/
00051 template <class KE>
00052 class BestMatch
00053 {
00054 public:
00055     BestMatch(const KE* iMatch, double iDistance) : _distance(iDistance), _match(iMatch) {}
00056     double      _distance;                      // square distance from target
00057     const KE*   _match;
00058 };
00059 
00060 /******************************************************************************
00061 * HyperRectangle
00062 ******************************************************************************/
00063 template <class KE, class TYPE>
00064 class HyperRectangle
00065 {
00066 public:
00067     HyperRectangle();
00068     HyperRectangle(int iDim);
00069     HyperRectangle(HyperRectangle& iOther);
00070     bool split(HyperRectangle& oLeft, HyperRectangle& oRight, int iSplitDim, TYPE iSplitVal);
00071     double calcSqDistance (const KE& iTarget);
00072     bool hasHyperSphereIntersect(const KE& iTarget, double iSqDistance);
00073     void display();
00074     bool isTargetIn (const KE& iTarget);
00075 
00076     int _dim;
00077     std::vector<TYPE> _leftTop, _rightBottom;
00078 };
00079 
00080 /******************************************************************************
00081 * QueueEntry
00082 ******************************************************************************/
00083 template <class KE, class VTYPE>
00084 class QueueEntry
00085 {
00086 public:
00087     QueueEntry(HyperRectangle<KE, VTYPE> & iHR, KDTree<KE, VTYPE> * iKDTree, double iDistance) :
00088         _dist(iDistance), _HR(iHR), _kdTree(iKDTree) {}
00089     double _dist;                                       // the distance from target to HyperRectangle
00090     HyperRectangle<KE, VTYPE> & _HR;    // reference to the hyperrectangle
00091     KDTree<KE, VTYPE> * _kdTree;
00092 
00093     // operator < to be put in a regular set.
00094     //bool operator < (const QueueEntry<KE> & iOther) { return (_dist < iOther._dist); }
00095 
00096 };
00097 
00098 /******************************************************************************
00099 * KDTree
00100 ******************************************************************************/
00101 template <class KE, class VTYPE>
00102 class KDTree
00103 {
00104 public:
00105     typedef typename std::vector<KE>                                                                            ItemVector_t;
00106     typedef typename std::vector<KE>::const_iterator                                            ItemVectorIt_t;
00107     typedef typename std::vector<const KE*>                                                             ItemPtrVector_t;
00108     typedef typename std::vector<const KE*>::const_iterator                             ItemPtrVectorIt_t;
00109     typedef typename std::set<BestMatch<KE>, std::greater<BestMatch<KE> > >     BestMatchSet_t;
00110     typedef lfeat::bounded_set<BestMatch<KE>, std::greater<BestMatch<KE> > >            BestMatchLimitedSet_t;
00111     typedef typename std::list<QueueEntry<KE, VTYPE> >                                          QueueEntryList_t;
00112 
00113     // constructor for the root.
00114     KDTree(const ItemVector_t& iElemsList, int iDimensions);
00115 
00116     // recursive construct.
00117     KDTree(const ItemPtrVector_t& iElemsPtrList, int iDimensions);
00118 
00119     // Destructor
00120     ~KDTree();
00121 
00122     BestMatchSet_t              getNearestNeighboursBBF(        const KE& iTarget,
00123             int iNbBestMatches,
00124             int iNbSearchSteps);
00125 
00126     // calc the square distance between 2 entries.
00127     double                              calcSqDist(const KE* i1, const KE* i2);
00128 
00129 private:
00130     void                                init(const ItemPtrVector_t& iElemsPtrList);                     // prepare the structure.
00131     ItemPtrVectorIt_t   choosePivot(const ItemPtrVector_t& iElemsPtrList);              // choose the pivot point
00132     void                                recurseNearestNeighboursBBF(const KE& iTarget,
00133             HyperRectangle<KE, VTYPE> & iHR,
00134             BestMatchLimitedSet_t& ioBestMatches,
00135             QueueEntryList_t& ioSearchQueue,
00136             int& ioRemainingUnqueues);
00137     // dimension of the vectors
00138     int                                 _dims;
00139 
00140     // The element stored on this leaf
00141     const KE*                   _pivot;
00142     int                                 _splitDim;
00143 
00144     // The left and the right kd-subtree.
00145     KDTree<KE, VTYPE> *                 _leftKD;
00146     KDTree<KE, VTYPE> *                 _rightKD;
00147 
00148 };
00149 
00150 } // namespace KDTree
00151 
00152 #endif

Generated on 20 Oct 2014 for Hugintrunk by  doxygen 1.4.7