Octree< MetricType, StatisticType, MatType > Class Template Reference

Classes

class  DualTreeTraverser
 A dual-tree traverser; see dual_tree_traverser.hpp. More...

 
class  SingleTreeTraverser
 A single-tree 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 &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. More...

 
 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. 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 &center) const
 Store the center of the bounding region in the given vector. More...

 
const OctreeChild (const size_t child) const
 Return the specified child. More...

 
OctreeChild (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...

 
Octreeoperator= (const Octree &other)
 Copy the given Octree. More...

 
Octreeoperator= (Octree &&other)
 Take ownership of the given Octree. More...

 
OctreeParent () 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...

 
ElemTypeParentDistance ()
 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< ElemTypeRangeDistance (const Octree &other) const
 Return the minimum and maximum distance to another node. More...

 
template
<
typename
VecType
>
math::RangeType< ElemTypeRangeDistance (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...

 

Detailed Description


template
<
typename
MetricType
=
metric::EuclideanDistance
,
typename
StatisticType
=
EmptyStatistic
,
typename
MatType
=
arma::mat
>

class mlpack::tree::Octree< MetricType, StatisticType, MatType >

Definition at line 25 of file octree.hpp.

Member Typedef Documentation

◆ ElemType

typedef MatType::elem_type ElemType

The type of element held in MatType.

Definition at line 31 of file octree.hpp.

◆ Mat

typedef MatType Mat

So other classes can use TreeType::Mat.

Definition at line 29 of file octree.hpp.

Constructor & Destructor Documentation

◆ Octree() [1/12]

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().

Parameters
dataDataset to create tree from. This will be copied!
maxLeafSizeMaximum number of points in a leaf node.

◆ Octree() [2/12]

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().

Parameters
dataDataset to create tree from. This will be copied!
oldFromNewVector which will be filled with the old positions for each new point.
maxLeafSizeMaximum number of points in a leaf node.

◆ Octree() [3/12]

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().

Parameters
dataDataset to create tree from. This will be copied!
oldFromNewVector which will be filled with the old positions for each new point.
newFromOldVector which will be filled with the new positions for each old point.
maxLeafSizeMaximum number of points in a leaf node.

◆ Octree() [4/12]

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.

Parameters
dataDataset to create tree from. This will be copied!
maxLeafSizeMaximum number of points in a leaf node.

◆ Octree() [5/12]

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.

Parameters
dataDataset to create tree from. This will be copied!
oldFromNewVector which will be filled with the old positions for each new point.
maxLeafSizeMaximum number of points in a leaf node.

◆ Octree() [6/12]

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.

Parameters
dataDataset to create tree from. This will be copied!
oldFromNewVector which will be filled with the old positions for each new point.
newFromOldVector which will be filled with the new positions for each old point.
maxLeafSizeMaximum number of points in a leaf node.

◆ Octree() [7/12]

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 tree-building by the other constructors that don't specify point indices.

Parameters
parentParent of this node. Its dataset will be modified!
beginIndex of point to start tree construction with.
countNumber of points to use to construct tree.
centerCenter of the node (for splitting).
widthWidth of the node in each dimension.
maxLeafSizeMaximum number of points in a leaf node.

◆ Octree() [8/12]

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 tree-building 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.

Parameters
parentParent of this node. Its dataset will be modified!
beginIndex of point to start tree construction with.
countNumber of points to use to construct tree.
oldFromNewVector which will be filled with the old positions for each new point.
centerCenter of the node (for splitting).
widthWidth of the node in each dimension.
maxLeafSizeMaximum number of points in a leaf node.

◆ Octree() [9/12]

Octree ( const Octree< MetricType, StatisticType, MatType > &  other)

Copy the given tree.

Be careful! This may use a lot of memory.

Parameters
otherTree to copy from.

◆ Octree() [10/12]

Octree ( Octree< MetricType, StatisticType, MatType > &&  other)

Move the given tree.

The tree passed as a parameter will be emptied and will not be usable after this call.

Parameters
otherTree to move.

◆ Octree() [11/12]

Octree ( Archive &  ar,
const typename std::enable_if_t< Archive::is_loading::value > *  = 0 
)

Initialize the tree from a boost::serialization archive.

Parameters
arArchive to load tree from. Must be an iarchive, not an oarchive.

◆ ~Octree()

~Octree ( )

Destroy the tree.

◆ Octree() [12/12]

Octree ( )
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().

Member Function Documentation

◆ Bound() [1/2]

const bound::HRectBound<MetricType>& Bound ( ) const
inline

Return the bound object for this node.

Definition at line 261 of file octree.hpp.

◆ Bound() [2/2]

bound::HRectBound<MetricType>& Bound ( )
inline

Modify the bound object for this node.

Definition at line 263 of file octree.hpp.

◆ Center()

void Center ( arma::vec &  center) const
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().

◆ Child() [1/2]

const Octree& Child ( const size_t  child) const
inline

Return the specified child.

If the index is out of bounds, unspecified behavior will occur.

Definition at line 340 of file octree.hpp.

◆ Child() [2/2]

Octree& Child ( const size_t  child)
inline

Return the specified child.

If the index is out of bounds, unspecified behavior will occur.

Definition at line 346 of file octree.hpp.

◆ ChildPtr()

◆ Dataset()

const MatType& Dataset ( ) const
inline

Return the dataset used by this node.

Definition at line 253 of file octree.hpp.

◆ Descendant()

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().

◆ FurthestDescendantDistance()

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().

◆ FurthestPointDistance()

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().

◆ GetFurthestChild() [1/2]

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().

◆ GetFurthestChild() [2/2]

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).

◆ GetNearestChild() [1/2]

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().

◆ GetNearestChild() [2/2]

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).

◆ IsLeaf()

◆ MaxDistance() [1/2]

ElemType MaxDistance ( const Octree< MetricType, StatisticType, MatType > &  other) const

Return the maximum distance to another node.

Referenced by Octree< MetricType, StatisticType, MatType >::ChildPtr().

◆ MaxDistance() [2/2]

ElemType MaxDistance ( const VecType &  point,
typename std::enable_if_t< IsVector< VecType >::value > *  = 0 
) const

Return the maximum distance to the given point.

◆ Metric()

MetricType Metric ( ) const
inline

◆ MinDistance() [1/2]

ElemType MinDistance ( const Octree< MetricType, StatisticType, MatType > &  other) const

Return the minimum distance to another node.

Referenced by Octree< MetricType, StatisticType, MatType >::ChildPtr().

◆ MinDistance() [2/2]

ElemType MinDistance ( const VecType &  point,
typename std::enable_if_t< IsVector< VecType >::value > *  = 0 
) const

Return the minimum distance to the given point.

◆ MinimumBoundDistance()

ElemType MinimumBoundDistance ( ) const

Return the minimum distance from the center of the node to any bound edge.

Referenced by Octree< MetricType, StatisticType, MatType >::IsLeaf().

◆ NumChildren()

size_t NumChildren ( ) const

◆ NumDescendants()

size_t NumDescendants ( ) const

Return the number of descendants of this node.

Referenced by Octree< MetricType, StatisticType, MatType >::ChildPtr().

◆ NumPoints()

size_t NumPoints ( ) const

Return the number of points in this node (0 if not a leaf).

Referenced by Octree< MetricType, StatisticType, MatType >::ChildPtr().

◆ operator=() [1/2]

Octree& operator= ( const Octree< MetricType, StatisticType, MatType > &  other)

Copy the given Octree.

Parameters
otherThe tree to be copied.

◆ operator=() [2/2]

Octree& operator= ( Octree< MetricType, StatisticType, MatType > &&  other)

Take ownership of the given Octree.

Parameters
otherThe tree to take ownership of.

◆ Parent() [1/2]

Octree* Parent ( ) const
inline

Get the pointer to the parent.

Definition at line 256 of file octree.hpp.

◆ Parent() [2/2]

Octree*& Parent ( )
inline

Modify the pointer to the parent (be careful!).

Definition at line 258 of file octree.hpp.

◆ ParentDistance() [1/2]

ElemType ParentDistance ( ) const
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.

◆ ParentDistance() [2/2]

ElemType& ParentDistance ( )
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.

◆ Point()

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().

◆ RangeDistance() [1/2]

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().

◆ RangeDistance() [2/2]

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.

◆ serialize()

void serialize ( Archive &  ar,
const unsigned  int 
)

Serialize the tree.

Referenced by Octree< MetricType, StatisticType, MatType >::Center().

◆ Stat() [1/2]

const StatisticType& Stat ( ) const
inline

Return the statistic object for this node.

Definition at line 266 of file octree.hpp.

◆ Stat() [2/2]

StatisticType& Stat ( )
inline

Modify the statistic object for this node.

Definition at line 268 of file octree.hpp.

References Octree< MetricType, StatisticType, MatType >::NumChildren().


The documentation for this class was generated from the following file:
  • /home/jenkins-mlpack/mlpack.org/_src/mlpack-3.3.1/src/mlpack/core/tree/octree/octree.hpp