mlpack 3.4.2
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
19namespace mlpack {
20namespace tree {
21
22template<typename MetricType = metric::EuclideanDistance,
23 typename StatisticType = EmptyStatistic,
24 typename MatType = arma::mat>
25class 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>
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
236
242 template<typename Archive>
244 Archive& ar,
246
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>
282 const VecType& point,
283 typename std::enable_if_t<IsVector<VecType>::value>* = 0) const;
284
289 template<typename VecType>
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
316
325
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;
379
381 template<typename VecType>
383 const VecType& point,
384 typename std::enable_if_t<IsVector<VecType>::value>* = 0) const;
386 template<typename VecType>
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 unsigned int /* version */);
402
403 protected:
411
413 friend class boost::serialization::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 {
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
Hyper-rectangle bound for an L-metric.
Definition: hrectbound.hpp:55
void Center(arma::Col< ElemType > &center) const
Calculates the center of the range, placing it into the given vector.
Simple real-valued range.
Definition: range.hpp:35
A dual-tree traverser; see dual_tree_traverser.hpp.
A single-tree traverser; see single_tree_traverser.hpp.
Octree(MatType &&data, std::vector< size_t > &oldFromNew, std::vector< size_t > &newFromOld, const size_t maxLeafSize=20)
Construct this as the root node of an octree on the given dataset.
Octree(Octree *parent, const size_t begin, const size_t count, const arma::vec &center, const double width, const size_t maxLeafSize=20)
Construct this node as a child of the given parent, starting at column begin and using count points.
ElemType MaxDistance(const Octree &other) const
Return the maximum distance to another node.
Octree & operator=(Octree &&other)
Take ownership of the given Octree.
size_t NumChildren() const
Return the number of children in this node.
ElemType MinimumBoundDistance() const
Return the minimum distance from the center of the node to any bound edge.
MatType::elem_type ElemType
The type of element held in MatType.
Definition: octree.hpp:31
ElemType & ParentDistance()
Modify the distance from the center of this node to the center of the parent node.
Definition: octree.hpp:334
size_t NumDescendants() const
Return the number of descendants of this node.
size_t NumPoints() const
Return the number of points in this node (0 if not a leaf).
Octree & Child(const size_t child)
Return the specified child.
Definition: octree.hpp:346
StatisticType & Stat()
Modify the statistic object for this node.
Definition: octree.hpp:268
Octree * Parent() const
Get the pointer to the parent.
Definition: octree.hpp:256
Octree & operator=(const Octree &other)
Copy the given Octree.
math::RangeType< ElemType > RangeDistance(const Octree &other) const
Return the minimum and maximum distance to another node.
Octree *& ChildPtr(const size_t child)
Return the pointer to the given child.
Definition: octree.hpp:352
ElemType MinDistance(const Octree &other) const
Return the minimum distance to another node.
size_t Point(const size_t index) const
Return the index (with reference to the dataset) of a particular point in this node.
MatType Mat
So other classes can use TreeType::Mat.
Definition: octree.hpp:29
Octree(const MatType &data, std::vector< size_t > &oldFromNew, std::vector< size_t > &newFromOld, const size_t maxLeafSize=20)
Construct this as the root node of an octree on the given dataset.
Octree()
A default constructor.
ElemType MinDistance(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
Return the minimum distance to the given point.
Octree *& Parent()
Modify the pointer to the parent (be careful!).
Definition: octree.hpp:258
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)
Construct this node as a child of the given parent, starting at column begin and using count points.
Octree(const MatType &data, const size_t maxLeafSize=20)
Construct this as the root node of an octree on the given dataset.
bool IsLeaf() const
Return whether or not the node is a leaf.
Definition: octree.hpp:297
size_t Descendant(const size_t index) const
Return the index (with reference to the dataset) of a particular descendant.
size_t GetNearestChild(const Octree &queryNode) const
Return the index of the nearest child node to the given query node.
void Center(arma::vec &center) const
Store the center of the bounding region in the given vector.
Definition: octree.hpp:397
const StatisticType & Stat() const
Return the statistic object for this node.
Definition: octree.hpp:266
const bound::HRectBound< MetricType > & Bound() const
Return the bound object for this node.
Definition: octree.hpp:261
Octree(MatType &&data, const size_t maxLeafSize=20)
Construct this as the root node of an octree on the given dataset.
size_t GetFurthestChild(const Octree &queryNode) const
Return the index of the furthest child node to the given query node.
MetricType Metric() const
Return the metric that this tree uses.
Definition: octree.hpp:274
const Octree & Child(const size_t child) const
Return the specified child.
Definition: octree.hpp:340
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.
Octree(const MatType &data, std::vector< size_t > &oldFromNew, const size_t maxLeafSize=20)
Construct this as the root node of an octree on the given dataset.
ElemType FurthestPointDistance() const
Return the furthest distance to a point held in this node.
math::RangeType< ElemType > RangeDistance(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
Return the minimum and maximum distance to another node.
Octree(Archive &ar, const typename std::enable_if_t< Archive::is_loading::value > *=0)
Initialize the tree from a boost::serialization archive.
~Octree()
Destroy the tree.
Octree(MatType &&data, std::vector< size_t > &oldFromNew, const size_t maxLeafSize=20)
Construct this as the root node of an octree on the given dataset.
const MatType & Dataset() const
Return the dataset used by this node.
Definition: octree.hpp:253
ElemType FurthestDescendantDistance() const
Return the furthest possible descendant distance.
Octree(const Octree &other)
Copy the given tree.
ElemType MaxDistance(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
Return the maximum distance to the given point.
void serialize(Archive &ar, const unsigned int)
Serialize the tree.
Octree(Octree &&other)
Move the given tree.
bound::HRectBound< MetricType > & Bound()
Modify the bound object for this node.
Definition: octree.hpp:263
ElemType ParentDistance() const
Return the distance from the center of this node to the center of the parent node.
Definition: octree.hpp:331
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.
LMetric< 2, true > EuclideanDistance
The Euclidean (L2) distance.
Definition: lmetric.hpp:112
Linear algebra utility functions, generally performed on matrices or vectors.
Definition: cv.hpp:1
typename enable_if< B, T >::type enable_if_t
Definition: prereqs.hpp:70
The core includes that mlpack expects; standard C++ includes and Armadillo.
If value == true, then VecType is some sort of Armadillo vector or subview.
Definition: arma_traits.hpp:36
size_t d
The dimension we are splitting on.
Definition: octree.hpp:453
SplitInfo(const size_t d, const arma::vec &c)
Create the SplitInfo object.
Definition: octree.hpp:450
const arma::vec & center
The center of the node.
Definition: octree.hpp:455