octree.hpp
Go to the documentation of this file.
1 
12 #ifndef MLPACK_CORE_TREE_OCTREE_OCTREE_HPP
13 #define MLPACK_CORE_TREE_OCTREE_OCTREE_HPP
14 
15 #include <mlpack/prereqs.hpp>
16 #include "../hrectbound.hpp"
17 #include "../statistic.hpp"
18 
19 namespace mlpack {
20 namespace tree {
21 
22 template<typename MetricType = metric::EuclideanDistance,
23  typename StatisticType = EmptyStatistic,
24  typename MatType = arma::mat>
25 class Octree
26 {
27  public:
29  typedef MatType Mat;
31  typedef typename MatType::elem_type ElemType;
32 
34  template<typename RuleType>
36 
38  template<typename RuleType>
39  class DualTreeTraverser;
40 
41  private:
43  std::vector<Octree*> children;
44 
47  size_t begin;
50  size_t count;
55  MatType* dataset;
57  Octree* parent;
59  StatisticType stat;
61  ElemType parentDistance;
63  ElemType furthestDescendantDistance;
65  MetricType metric;
66 
67  public:
76  Octree(const MatType& data, const size_t maxLeafSize = 20);
77 
90  Octree(const MatType& data,
91  std::vector<size_t>& oldFromNew,
92  const size_t maxLeafSize = 20);
93 
109  Octree(const MatType& data,
110  std::vector<size_t>& oldFromNew,
111  std::vector<size_t>& newFromOld,
112  const size_t maxLeafSize = 20);
113 
122  Octree(MatType&& data, const size_t maxLeafSize = 20);
123 
136  Octree(MatType&& data,
137  std::vector<size_t>& oldFromNew,
138  const size_t maxLeafSize = 20);
139 
155  Octree(MatType&& data,
156  std::vector<size_t>& oldFromNew,
157  std::vector<size_t>& newFromOld,
158  const size_t maxLeafSize = 20);
159 
173  Octree(Octree* parent,
174  const size_t begin,
175  const size_t count,
176  const arma::vec& center,
177  const double width,
178  const size_t maxLeafSize = 20);
179 
200  Octree(Octree* parent,
201  const size_t begin,
202  const size_t count,
203  std::vector<size_t>& oldFromNew,
204  const arma::vec& center,
205  const double width,
206  const size_t maxLeafSize = 20);
207 
213  Octree(const Octree& other);
214 
221  Octree(Octree&& other);
222 
228  Octree& operator=(const Octree& other);
229 
235  Octree& operator=(Octree&& other);
236 
242  template<typename Archive>
243  Octree(
244  Archive& ar,
245  const typename std::enable_if_t<cereal::is_loading<Archive>()>* = 0);
246 
250  ~Octree();
251 
253  const MatType& Dataset() const { return *dataset; }
254 
256  Octree* Parent() const { return parent; }
258  Octree*& Parent() { return parent; }
259 
261  const bound::HRectBound<MetricType>& Bound() const { return bound; }
264 
266  const StatisticType& Stat() const { return stat; }
268  StatisticType& Stat() { return stat; }
269 
271  size_t NumChildren() const;
272 
274  MetricType Metric() const { return MetricType(); }
275 
280  template<typename VecType>
281  size_t GetNearestChild(
282  const VecType& point,
283  typename std::enable_if_t<IsVector<VecType>::value>* = 0) const;
284 
289  template<typename VecType>
290  size_t GetFurthestChild(
291  const VecType& point,
292  typename std::enable_if_t<IsVector<VecType>::value>* = 0) const;
293 
297  bool IsLeaf() const { return NumChildren() == 0; }
298 
303  size_t GetNearestChild(const Octree& queryNode) const;
304 
309  size_t GetFurthestChild(const Octree& queryNode) const;
310 
315  ElemType FurthestPointDistance() const;
316 
324  ElemType FurthestDescendantDistance() const;
325 
327  ElemType MinimumBoundDistance() const;
328 
331  ElemType ParentDistance() const { return parentDistance; }
334  ElemType& ParentDistance() { return parentDistance; }
335 
340  const Octree& Child(const size_t child) const { return *children[child]; }
341 
346  Octree& Child(const size_t child) { return *children[child]; }
347 
352  Octree*& ChildPtr(const size_t child) { return children[child]; }
353 
355  size_t NumPoints() const;
356 
358  size_t NumDescendants() const;
359 
364  size_t Descendant(const size_t index) const;
365 
371  size_t Point(const size_t index) const;
372 
374  ElemType MinDistance(const Octree& other) const;
376  ElemType MaxDistance(const Octree& other) const;
378  math::RangeType<ElemType> RangeDistance(const Octree& other) const;
379 
381  template<typename VecType>
382  ElemType MinDistance(
383  const VecType& point,
384  typename std::enable_if_t<IsVector<VecType>::value>* = 0) const;
386  template<typename VecType>
387  ElemType MaxDistance(
388  const VecType& point,
389  typename std::enable_if_t<IsVector<VecType>::value>* = 0) const;
391  template<typename VecType>
393  const VecType& point,
394  typename std::enable_if_t<IsVector<VecType>::value>* = 0) const;
395 
397  void Center(arma::vec& center) const { bound.Center(center); }
398 
400  template<typename Archive>
401  void serialize(Archive& ar, const uint32_t /* version */);
402 
403  protected:
410  Octree();
411 
413  friend class cereal::access;
414 
415  private:
424  void SplitNode(const arma::vec& center,
425  const double width,
426  const size_t maxLeafSize);
427 
437  void SplitNode(const arma::vec& center,
438  const double width,
439  std::vector<size_t>& oldFromNew,
440  const size_t maxLeafSize);
441 
445  struct SplitType
446  {
447  struct SplitInfo
448  {
450  SplitInfo(const size_t d, const arma::vec& c) : d(d), center(c) {}
451 
453  size_t d;
455  const arma::vec& center;
456  };
457 
458  template<typename VecType>
459  static bool AssignToLeftNode(const VecType& point, const SplitInfo& s)
460  {
461  return point[s.d] < s.center[s.d];
462  }
463  };
464 };
465 
466 } // namespace tree
467 } // namespace mlpack
468 
469 // Include implementation.
470 #include "octree_impl.hpp"
471 
472 #endif
size_t Point(const size_t index) const
Return the index (with reference to the dataset) of a particular point in this node.
A dual-tree traverser; see dual_tree_traverser.hpp.
Octree()
A default constructor.
ElemType FurthestPointDistance() const
Return the furthest distance to a point held in this node.
Octree * Parent() const
Get the pointer to the parent.
Definition: octree.hpp:256
typename enable_if< B, T >::type enable_if_t
Definition: prereqs.hpp:70
ElemType MaxDistance(const Octree &other) const
Return the maximum distance to another node.
Linear algebra utility functions, generally performed on matrices or vectors.
void Center(arma::vec &center) const
Store the center of the bounding region in the given vector.
Definition: octree.hpp:397
const bound::HRectBound< MetricType > & Bound() const
Return the bound object for this node.
Definition: octree.hpp:261
void serialize(Archive &ar, const uint32_t)
Serialize the tree.
MatType::elem_type ElemType
The type of element held in MatType.
Definition: octree.hpp:31
The core includes that mlpack expects; standard C++ includes and Armadillo.
size_t GetNearestChild(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
Return the index of the nearest child node to the given query point.
bound::HRectBound< MetricType > & Bound()
Modify the bound object for this node.
Definition: octree.hpp:263
MetricType Metric() const
Return the metric that this tree uses.
Definition: octree.hpp:274
ElemType MinimumBoundDistance() const
Return the minimum distance from the center of the node to any bound edge.
const Octree & Child(const size_t child) const
Return the specified child.
Definition: octree.hpp:340
ElemType ParentDistance() const
Return the distance from the center of this node to the center of the parent node.
Definition: octree.hpp:331
Octree & operator=(const Octree &other)
Copy the given Octree.
bool IsLeaf() const
Return whether or not the node is a leaf.
Definition: octree.hpp:297
constexpr auto data(Container const &container) noexcept -> decltype(container.data())
Definition: iterator.hpp:79
const StatisticType & Stat() const
Return the statistic object for this node.
Definition: octree.hpp:266
size_t NumDescendants() const
Return the number of descendants of this node.
~Octree()
Destroy the tree.
A single-tree traverser; see single_tree_traverser.hpp.
Definition: octree.hpp:35
ElemType MinDistance(const Octree &other) const
Return the minimum distance to another node.
ElemType & ParentDistance()
Modify the distance from the center of this node to the center of the parent node.
Definition: octree.hpp:334
SplitInfo(const size_t d, const arma::vec &c)
Create the SplitInfo object.
Definition: octree.hpp:450
Octree & Child(const size_t child)
Return the specified child.
Definition: octree.hpp:346
math::RangeType< ElemType > RangeDistance(const Octree &other) const
Return the minimum and maximum distance to another node.
StatisticType & Stat()
Modify the statistic object for this node.
Definition: octree.hpp:268
Octree *& Parent()
Modify the pointer to the parent (be careful!).
Definition: octree.hpp:258
const arma::vec & center
The center of the node.
Definition: octree.hpp:455
auto count(Range &&rng, T const &value) -> enable_if_t< is_range< Range >::value, decltype(::std::count(::std::begin(::core::forward< Range >(rng)), ::std::end(::core::forward< Range >(rng)), value)) >
Definition: algorithm.hpp:225
MatType Mat
So other classes can use TreeType::Mat.
Definition: octree.hpp:29
size_t Descendant(const size_t index) const
Return the index (with reference to the dataset) of a particular descendant.
void Center(arma::Col< ElemType > &center) const
Calculates the center of the range, placing it into the given vector.
ElemType FurthestDescendantDistance() const
Return the furthest possible descendant distance.
LMetric< 2, true > EuclideanDistance
The Euclidean (L2) distance.
Definition: lmetric.hpp:112
size_t NumChildren() const
Return the number of children in this node.
Octree *& ChildPtr(const size_t child)
Return the pointer to the given child.
Definition: octree.hpp:352
const MatType & Dataset() const
Return the dataset used by this node.
Definition: octree.hpp:253
size_t NumPoints() const
Return the number of points in this node (0 if not a leaf).
If value == true, then VecType is some sort of Armadillo vector or subview.
Definition: arma_traits.hpp:35
size_t GetFurthestChild(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
Return the index of the furthest child node to the given query point.
size_t d
The dimension we are splitting on.
Definition: octree.hpp:453