octree.hpp

Go to the documentation of this file.

 
#ifndef MLPACK_CORE_TREE_OCTREE_OCTREE_HPP
#define MLPACK_CORE_TREE_OCTREE_OCTREE_HPP
 
#include <mlpack/prereqs.hpp>
#include "../hrectbound.hpp"
#include "../statistic.hpp"
 
namespace mlpack {
namespace tree {
 
template<typename MetricType = metric::EuclideanDistance,
         typename StatisticType = EmptyStatistic,
         typename MatType = arma::mat>
class Octree
{
 public:
  typedef MatType Mat;
  typedef typename MatType::elem_type ElemType;
 
  template<typename RuleType>
  class SingleTreeTraverser;
 
  template<typename RuleType>
  class DualTreeTraverser;
 
 private:
  std::vector<Octree*> children;
 
  size_t begin;
  size_t count;
  bound::HRectBound<MetricType> bound;
  MatType* dataset;
  Octree* parent;
  StatisticType stat;
  ElemType parentDistance;
  ElemType furthestDescendantDistance;
  MetricType metric;
 
 public:
  Octree(const MatType& data, const size_t maxLeafSize = 20);
 
  Octree(const MatType& data,
         std::vector<size_t>& oldFromNew,
         const size_t maxLeafSize = 20);
 
  Octree(const MatType& data,
         std::vector<size_t>& oldFromNew,
         std::vector<size_t>& newFromOld,
         const size_t maxLeafSize = 20);
 
  Octree(MatType&& data, const size_t maxLeafSize = 20);
 
  Octree(MatType&& data,
         std::vector<size_t>& oldFromNew,
         const size_t maxLeafSize = 20);
 
  Octree(MatType&& data,
         std::vector<size_t>& oldFromNew,
         std::vector<size_t>& newFromOld,
         const size_t maxLeafSize = 20);
 
  Octree(Octree* parent,
         const size_t begin,
         const size_t count,
         const arma::vec& center,
         const double width,
         const size_t maxLeafSize = 20);
 
  Octree(Octree* parent,
         const size_t begin,
         const size_t count,
         std::vector<size_t>& oldFromNew,
         const arma::vec& center,
         const double width,
         const size_t maxLeafSize = 20);
 
  Octree(const Octree& other);
 
  Octree(Octree&& other);
 
  Octree& operator=(const Octree& other);
 
  Octree& operator=(Octree&& other);
 
  template<typename Archive>
  Octree(
      Archive& ar,
      const typename std::enable_if_t<Archive::is_loading::value>* = 0);
 
  ~Octree();
 
  const MatType& Dataset() const { return *dataset; }
 
  Octree* Parent() const { return parent; }
  Octree*& Parent() { return parent; }
 
  const bound::HRectBound<MetricType>& Bound() const { return bound; }
  bound::HRectBound<MetricType>& Bound() { return bound; }
 
  const StatisticType& Stat() const { return stat; }
  StatisticType& Stat() { return stat; }
 
  size_t NumChildren() const;
 
  MetricType Metric() const { return MetricType(); }
 
  template<typename VecType>
  size_t GetNearestChild(
      const VecType& point,
      typename std::enable_if_t<IsVector<VecType>::value>* = 0) const;
 
  template<typename VecType>
  size_t GetFurthestChild(
      const VecType& point,
      typename std::enable_if_t<IsVector<VecType>::value>* = 0) const;
 
  bool IsLeaf() const { return NumChildren() == 0; }
 
  size_t GetNearestChild(const Octree& queryNode) const;
 
  size_t GetFurthestChild(const Octree& queryNode) const;
 
  ElemType FurthestPointDistance() const;
 
  ElemType FurthestDescendantDistance() const;
 
  ElemType MinimumBoundDistance() const;
 
  ElemType ParentDistance() const { return parentDistance; }
  ElemType& ParentDistance() { return parentDistance; }
 
  const Octree& Child(const size_t child) const { return *children[child]; }
 
  Octree& Child(const size_t child) { return *children[child]; }
 
  Octree*& ChildPtr(const size_t child) { return children[child]; }
 
  size_t NumPoints() const;
 
  size_t NumDescendants() const;
 
  size_t Descendant(const size_t index) const;
 
  size_t Point(const size_t index) const;
 
  ElemType MinDistance(const Octree& other) const;
  ElemType MaxDistance(const Octree& other) const;
  math::RangeType<ElemType> RangeDistance(const Octree& other) const;
 
  template<typename VecType>
  ElemType MinDistance(
      const VecType& point,
      typename std::enable_if_t<IsVector<VecType>::value>* = 0) const;
  template<typename VecType>
  ElemType MaxDistance(
      const VecType& point,
      typename std::enable_if_t<IsVector<VecType>::value>* = 0) const;
  template<typename VecType>
  math::RangeType<ElemType> RangeDistance(
      const VecType& point,
      typename std::enable_if_t<IsVector<VecType>::value>* = 0) const;
 
  void Center(arma::vec& center) const { bound.Center(center); }
 
  template<typename Archive>
  void serialize(Archive& ar, const unsigned int /* version */);
 
 protected:
  Octree();
 
  friend class boost::serialization::access;
 
 private:
  void SplitNode(const arma::vec& center,
                 const double width,
                 const size_t maxLeafSize);
 
  void SplitNode(const arma::vec& center,
                 const double width,
                 std::vector<size_t>& oldFromNew,
                 const size_t maxLeafSize);
 
  struct SplitType
  {
    struct SplitInfo
    {
      SplitInfo(const size_t d, const arma::vec& c) : d(d), center(c) {}
 
      size_t d;
      const arma::vec& center;
    };
 
    template<typename VecType>
    static bool AssignToLeftNode(const VecType& point, const SplitInfo& s)
    {
      return point[s.d] < s.center[s.d];
    }
  };
};
 
} // namespace tree
} // namespace mlpack
 
// Include implementation.
#include "octree_impl.hpp"
 
#endif