Classes  
class  DualTreeTraverser 
A dualtree traverser; see dual_tree_traverser.hpp. More...  
class  SingleTreeTraverser 
A singletree traverser; see single_tree_traverser.hpp. More...  
Public Types  
typedef MatType::elem_type  ElemType 
The type of element held in MatType. More...  
typedef MatType  Mat 
So other classes can use TreeType::Mat. More...  
Public Member Functions  
Octree (const MatType &data, const size_t maxLeafSize=20)  
Construct this as the root node of an octree on the given dataset. More...  
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. More...  
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. More...  
Octree (MatType &&data, const size_t maxLeafSize=20)  
Construct this as the root node of an octree on the given dataset. More...  
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. More...  
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. More...  
Octree (Octree *parent, const size_t begin, const size_t count, const arma::vec ¢er, 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. More...  
Octree (Octree *parent, const size_t begin, const size_t count, std::vector< size_t > &oldFromNew, const arma::vec ¢er, 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. More...  
Octree (const Octree &other)  
Copy the given tree. More...  
Octree (Octree &&other)  
Move the given tree. More...  
template < typename Archive >  
Octree (Archive &ar, const typename std::enable_if_t< Archive::is_loading::value > *=0)  
Initialize the tree from a boost::serialization archive. More...  
~Octree ()  
Destroy the tree. More...  
const bound::HRectBound< MetricType > &  Bound () const 
Return the bound object for this node. More...  
bound::HRectBound< MetricType > &  Bound () 
Modify the bound object for this node. More...  
void  Center (arma::vec ¢er) const 
Store the center of the bounding region in the given vector. More...  
const Octree &  Child (const size_t child) const 
Return the specified child. More...  
Octree &  Child (const size_t child) 
Return the specified child. More...  
Octree *&  ChildPtr (const size_t child) 
Return the pointer to the given child. More...  
const MatType &  Dataset () const 
Return the dataset used by this node. More...  
size_t  Descendant (const size_t index) const 
Return the index (with reference to the dataset) of a particular descendant. More...  
ElemType  FurthestDescendantDistance () const 
Return the furthest possible descendant distance. More...  
ElemType  FurthestPointDistance () const 
Return the furthest distance to a point held in this node. More...  
template < typename VecType >  
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. More...  
size_t  GetFurthestChild (const Octree &queryNode) const 
Return the index of the furthest child node to the given query node. More...  
template < typename VecType >  
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. More...  
size_t  GetNearestChild (const Octree &queryNode) const 
Return the index of the nearest child node to the given query node. More...  
bool  IsLeaf () const 
Return whether or not the node is a leaf. More...  
ElemType  MaxDistance (const Octree &other) const 
Return the maximum distance to another node. More...  
template < typename VecType >  
ElemType  MaxDistance (const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const 
Return the maximum distance to the given point. More...  
MetricType  Metric () const 
Return the metric that this tree uses. More...  
ElemType  MinDistance (const Octree &other) const 
Return the minimum distance to another node. More...  
template < typename VecType >  
ElemType  MinDistance (const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const 
Return the minimum distance to the given point. More...  
ElemType  MinimumBoundDistance () const 
Return the minimum distance from the center of the node to any bound edge. More...  
size_t  NumChildren () const 
Return the number of children in this node. More...  
size_t  NumDescendants () const 
Return the number of descendants of this node. More...  
size_t  NumPoints () const 
Return the number of points in this node (0 if not a leaf). More...  
Octree &  operator= (const Octree &other) 
Copy the given Octree. More...  
Octree &  operator= (Octree &&other) 
Take ownership of the given Octree. More...  
Octree *  Parent () const 
Get the pointer to the parent. More...  
Octree *&  Parent () 
Modify the pointer to the parent (be careful!). More...  
ElemType  ParentDistance () const 
Return the distance from the center of this node to the center of the parent node. More...  
ElemType &  ParentDistance () 
Modify the distance from the center of this node to the center of the parent node. More...  
size_t  Point (const size_t index) const 
Return the index (with reference to the dataset) of a particular point in this node. More...  
math::RangeType< ElemType >  RangeDistance (const Octree &other) const 
Return the minimum and maximum distance to another node. More...  
template < typename VecType >  
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. More...  
template < typename Archive >  
void  serialize (Archive &ar, const unsigned int) 
Serialize the tree. More...  
const StatisticType &  Stat () const 
Return the statistic object for this node. More...  
StatisticType &  Stat () 
Modify the statistic object for this node. More...  
Protected Member Functions  
Octree ()  
A default constructor. More...  
Definition at line 25 of file octree.hpp.
typedef MatType::elem_type ElemType 
The type of element held in MatType.
Definition at line 31 of file octree.hpp.
typedef MatType Mat 
So other classes can use TreeType::Mat.
Definition at line 29 of file octree.hpp.
Octree  (  const MatType &  data, 
const size_t  maxLeafSize = 20 

) 
Construct this as the root node of an octree on the given dataset.
This copies the dataset. If you don't want to copy the input dataset, consider using the constructor that takes an rvalue reference and use std::move().
data  Dataset to create tree from. This will be copied! 
maxLeafSize  Maximum number of points in a leaf node. 
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.
This copies the dataset and modifies its ordering; a mapping of the old point indices to the new point indices is filled. If you don't want the matrix to be copied, consider using the constructor that takes an rvalue reference and use std::move().
data  Dataset to create tree from. This will be copied! 
oldFromNew  Vector which will be filled with the old positions for each new point. 
maxLeafSize  Maximum number of points in a leaf node. 
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.
This copies the dataset and modifies its ordering; a mapping of the old point indices to the new point indices is filled, and a mapping of the new point indices to the old point indices is filled. If you don't want the matrix to be copied, consider using the constructor that takes an rvalue reference and use std::move().
data  Dataset to create tree from. This will be copied! 
oldFromNew  Vector which will be filled with the old positions for each new point. 
newFromOld  Vector which will be filled with the new positions for each old point. 
maxLeafSize  Maximum number of points in a leaf node. 
Octree  (  MatType &&  data, 
const size_t  maxLeafSize = 20 

) 
Construct this as the root node of an octree on the given dataset.
This will take ownership of the dataset; if you don't want this, consider using the constructor that takes a const reference to the dataset.
data  Dataset to create tree from. This will be copied! 
maxLeafSize  Maximum number of points in a leaf node. 
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.
This will take ownership of the dataset; if you don't want this, consider using the constructor that takes a const reference to the dataset. This modifies the ordering of the dataset; a mapping of the old point indices to the new point indices is filled.
data  Dataset to create tree from. This will be copied! 
oldFromNew  Vector which will be filled with the old positions for each new point. 
maxLeafSize  Maximum number of points in a leaf node. 
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.
This will take ownership of the dataset; if you don't want this, consider using the constructor that takes a const reference to the dataset. This modifies the ordering of the dataset; a mapping of the old point indices to the new point indices is filled, and a mapping of the new point indices to the old point indices is filled.
data  Dataset to create tree from. This will be copied! 
oldFromNew  Vector which will be filled with the old positions for each new point. 
newFromOld  Vector which will be filled with the new positions for each old point. 
maxLeafSize  Maximum number of points in a leaf node. 
Octree  (  Octree< MetricType, StatisticType, MatType > *  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.
The ordering of that subset of points in the parent's data matrix will be modified! This is used for recursive treebuilding by the other constructors that don't specify point indices.
parent  Parent of this node. Its dataset will be modified! 
begin  Index of point to start tree construction with. 
count  Number of points to use to construct tree. 
center  Center of the node (for splitting). 
width  Width of the node in each dimension. 
maxLeafSize  Maximum number of points in a leaf node. 
Octree  (  Octree< MetricType, StatisticType, MatType > *  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.
The ordering of that subset of points in the parent's data matrix will be modified! This is used for recursive treebuilding by the other constructors that don't specify point indices.
A mapping of the old point indices to the new point indices is filled, but it is expected that the vector is already allocated with size greater than or equal to (begin + count), and if that is not true, invalid memory reads (and writes) will occur.
parent  Parent of this node. Its dataset will be modified! 
begin  Index of point to start tree construction with. 
count  Number of points to use to construct tree. 
oldFromNew  Vector which will be filled with the old positions for each new point. 
center  Center of the node (for splitting). 
width  Width of the node in each dimension. 
maxLeafSize  Maximum number of points in a leaf node. 
Copy the given tree.
Be careful! This may use a lot of memory.
other  Tree to copy from. 
Move the given tree.
The tree passed as a parameter will be emptied and will not be usable after this call.
other  Tree to move. 
Octree  (  Archive &  ar, 
const typename std::enable_if_t< Archive::is_loading::value > *  = 0 

) 
Initialize the tree from a boost::serialization archive.
ar  Archive to load tree from. Must be an iarchive, not an oarchive. 
~Octree  (  ) 
Destroy the tree.

protected 
A default constructor.
This is meant to only be used with boost::serialization, which is allowed with the friend declaration below. This does not return a valid treee! The method must be protected, so that the serialization shim can work with the default constructor.
Referenced by Octree< MetricType, StatisticType, MatType >::Center().

inline 
Return the bound object for this node.
Definition at line 261 of file octree.hpp.

inline 
Modify the bound object for this node.
Definition at line 263 of file octree.hpp.

inline 
Store the center of the bounding region in the given vector.
Definition at line 397 of file octree.hpp.
References HRectBound< MetricType, ElemType >::Center(), Octree< MetricType, StatisticType, MatType >::Octree(), and Octree< MetricType, StatisticType, MatType >::serialize().

inline 
Return the specified child.
If the index is out of bounds, unspecified behavior will occur.
Definition at line 340 of file octree.hpp.

inline 
Return the specified child.
If the index is out of bounds, unspecified behavior will occur.
Definition at line 346 of file octree.hpp.

inline 
Return the pointer to the given child.
This allows the child itself to be modified.
Definition at line 352 of file octree.hpp.
References Octree< MetricType, StatisticType, MatType >::Descendant(), Octree< MetricType, StatisticType, MatType >::MaxDistance(), Octree< MetricType, StatisticType, MatType >::MinDistance(), Octree< MetricType, StatisticType, MatType >::NumDescendants(), Octree< MetricType, StatisticType, MatType >::NumPoints(), Octree< MetricType, StatisticType, MatType >::Point(), and Octree< MetricType, StatisticType, MatType >::RangeDistance().

inline 
Return the dataset used by this node.
Definition at line 253 of file octree.hpp.
size_t Descendant  (  const size_t  index  )  const 
Return the index (with reference to the dataset) of a particular descendant.
Referenced by Octree< MetricType, StatisticType, MatType >::ChildPtr().
ElemType FurthestDescendantDistance  (  )  const 
Return the furthest possible descendant distance.
This returns the maximum distance from the centroid to the edge of the bound and not the empirical quantity which is the actual furthest descendant distance. So the actual furthest descendant distance may be less than what this method returns (but it will never be greater than this).
Referenced by Octree< MetricType, StatisticType, MatType >::IsLeaf().
ElemType FurthestPointDistance  (  )  const 
Return the furthest distance to a point held in this node.
If this is not a leaf node, then the distance is 0 because the node holds no points.
Referenced by Octree< MetricType, StatisticType, MatType >::IsLeaf().
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.
If this is a leaf node, it will return NumChildren() (invalid index).
Referenced by Octree< MetricType, StatisticType, MatType >::IsLeaf(), and Octree< MetricType, StatisticType, MatType >::Metric().
size_t GetFurthestChild  (  const Octree< MetricType, StatisticType, MatType > &  queryNode  )  const 
Return the index of the furthest child node to the given query node.
If it can't decide, it will return NumChildren() (invalid index).
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.
If this is a leaf node, it will return NumChildren() (invalid index).
Referenced by Octree< MetricType, StatisticType, MatType >::IsLeaf(), and Octree< MetricType, StatisticType, MatType >::Metric().
size_t GetNearestChild  (  const Octree< MetricType, StatisticType, MatType > &  queryNode  )  const 
Return the index of the nearest child node to the given query node.
If it can't decide, it will return NumChildren() (invalid index).

inline 
Return whether or not the node is a leaf.
Definition at line 297 of file octree.hpp.
References Octree< MetricType, StatisticType, MatType >::FurthestDescendantDistance(), Octree< MetricType, StatisticType, MatType >::FurthestPointDistance(), Octree< MetricType, StatisticType, MatType >::GetFurthestChild(), Octree< MetricType, StatisticType, MatType >::GetNearestChild(), Octree< MetricType, StatisticType, MatType >::MinimumBoundDistance(), and Octree< MetricType, StatisticType, MatType >::NumChildren().
Return the maximum distance to another node.
Referenced by Octree< MetricType, StatisticType, MatType >::ChildPtr().
ElemType MaxDistance  (  const VecType &  point, 
typename std::enable_if_t< IsVector< VecType >::value > *  = 0 

)  const 
Return the maximum distance to the given point.

inline 
Return the metric that this tree uses.
Definition at line 274 of file octree.hpp.
References Octree< MetricType, StatisticType, MatType >::GetFurthestChild(), and Octree< MetricType, StatisticType, MatType >::GetNearestChild().
Return the minimum distance to another node.
Referenced by Octree< MetricType, StatisticType, MatType >::ChildPtr().
ElemType MinDistance  (  const VecType &  point, 
typename std::enable_if_t< IsVector< VecType >::value > *  = 0 

)  const 
Return the minimum distance to the given point.
ElemType MinimumBoundDistance  (  )  const 
Return the minimum distance from the center of the node to any bound edge.
Referenced by Octree< MetricType, StatisticType, MatType >::IsLeaf().
size_t NumChildren  (  )  const 
Return the number of children in this node.
Referenced by Octree< MetricType, StatisticType, MatType >::IsLeaf(), and Octree< MetricType, StatisticType, MatType >::Stat().
size_t NumDescendants  (  )  const 
Return the number of descendants of this node.
Referenced by Octree< MetricType, StatisticType, MatType >::ChildPtr().
size_t NumPoints  (  )  const 
Return the number of points in this node (0 if not a leaf).
Referenced by Octree< MetricType, StatisticType, MatType >::ChildPtr().
Copy the given Octree.
other  The tree to be copied. 
Take ownership of the given Octree.
other  The tree to take ownership of. 

inline 
Get the pointer to the parent.
Definition at line 256 of file octree.hpp.

inline 
Modify the pointer to the parent (be careful!).
Definition at line 258 of file octree.hpp.

inline 
Return the distance from the center of this node to the center of the parent node.
Definition at line 331 of file octree.hpp.

inline 
Modify the distance from the center of this node to the center of the parent node.
Definition at line 334 of file octree.hpp.
size_t Point  (  const size_t  index  )  const 
Return the index (with reference to the dataset) of a particular point in this node.
If the given index is invalid (i.e. if it is greater than NumPoints()), the indices returned will be invalid.
Referenced by Octree< MetricType, StatisticType, MatType >::ChildPtr().
math::RangeType<ElemType> RangeDistance  (  const Octree< MetricType, StatisticType, MatType > &  other  )  const 
Return the minimum and maximum distance to another node.
Referenced by Octree< MetricType, StatisticType, MatType >::ChildPtr().
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.
void serialize  (  Archive &  ar, 
const unsigned  int  
) 
Serialize the tree.
Referenced by Octree< MetricType, StatisticType, MatType >::Center().

inline 
Return the statistic object for this node.
Definition at line 266 of file octree.hpp.

inline 
Modify the statistic object for this node.
Definition at line 268 of file octree.hpp.
References Octree< MetricType, StatisticType, MatType >::NumChildren().