MLPACK  1.0.4
range_search.hpp
Go to the documentation of this file.
00001 
00023 #ifndef __MLPACK_METHODS_RANGE_SEARCH_RANGE_SEARCH_HPP
00024 #define __MLPACK_METHODS_RANGE_SEARCH_RANGE_SEARCH_HPP
00025 
00026 #include <mlpack/core.hpp>
00027 
00028 #include <mlpack/core/metrics/lmetric.hpp>
00029 
00030 #include <mlpack/core/tree/binary_space_tree.hpp>
00031 
00032 namespace mlpack {
00033 namespace range  {
00034 
00038 template<typename MetricType = mlpack::metric::SquaredEuclideanDistance,
00039          typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>,
00040                                                    tree::EmptyStatistic> >
00041 class RangeSearch
00042 {
00043  public:
00063   RangeSearch(const typename TreeType::Mat& referenceSet,
00064               const typename TreeType::Mat& querySet,
00065               const bool naive = false,
00066               const bool singleMode = false,
00067               const size_t leafSize = 20,
00068               const MetricType metric = MetricType());
00069 
00089   RangeSearch(const typename TreeType::Mat& referenceSet,
00090               const bool naive = false,
00091               const bool singleMode = false,
00092               const size_t leafSize = 20,
00093               const MetricType metric = MetricType());
00094 
00124   RangeSearch(TreeType* referenceTree,
00125               TreeType* queryTree,
00126               const typename TreeType::Mat& referenceSet,
00127               const typename TreeType::Mat& querySet,
00128               const bool singleMode = false,
00129               const MetricType metric = MetricType());
00130 
00158   RangeSearch(TreeType* referenceTree,
00159               const typename TreeType::Mat& referenceSet,
00160               const bool singleMode = false,
00161               const MetricType metric = MetricType());
00162 
00167   ~RangeSearch();
00168 
00195   void Search(const math::Range& range,
00196               std::vector<std::vector<size_t> >& neighbors,
00197               std::vector<std::vector<double> >& distances);
00198 
00199  private:
00210   void ComputeBaseCase(const TreeType* referenceNode,
00211                        const TreeType* queryNode,
00212                        const math::Range& range,
00213                        std::vector<std::vector<size_t> >& neighbors,
00214                        std::vector<std::vector<double> >& distances) const;
00215 
00226   void DualTreeRecursion(const TreeType* referenceNode,
00227                          const TreeType* queryNode,
00228                          const math::Range& range,
00229                          std::vector<std::vector<size_t> >& neighbors,
00230                          std::vector<std::vector<double> >& distances);
00231 
00243   template<typename VecType>
00244   void SingleTreeRecursion(const TreeType* referenceNode,
00245                            const VecType& queryPoint,
00246                            const size_t queryIndex,
00247                            const math::Range& range,
00248                            std::vector<size_t>& neighbors,
00249                            std::vector<double>& distances);
00250 
00252   typename TreeType::Mat referenceCopy;
00254   typename TreeType::Mat queryCopy;
00255 
00257   const typename TreeType::Mat& referenceSet;
00259   const typename TreeType::Mat& querySet;
00260 
00262   TreeType* referenceTree;
00264   TreeType* queryTree;
00265 
00267   std::vector<size_t> oldFromNewReferences;
00269   std::vector<size_t> oldFromNewQueries;
00270 
00272   bool ownReferenceTree;
00274   bool ownQueryTree;
00275 
00277   bool naive;
00279   bool singleMode;
00280 
00282   MetricType metric;
00283 
00285   size_t numberOfPrunes;
00286 };
00287 
00288 }; // namespace range
00289 }; // namespace mlpack
00290 
00291 // Include implementation.
00292 #include "range_search_impl.hpp"
00293 
00294 #endif