Ponca  aa50bfdf187919869239c5b44b748842569114c1
Point Cloud Analysis library
Loading...
Searching...
No Matches
Ponca::KdTreeBase< Traits > Class Template Reference

[KdTreeSparse type definition] More...

#include <kdTree.h>

+ Inheritance diagram for Ponca::KdTreeBase< Traits >:
+ Collaboration diagram for Ponca::KdTreeBase< Traits >:

Classes

struct  DefaultConverter
 Convert a custom point container to the KdTree PointContainer using DataPoint default constructor. More...
 

Public Types

using DataPoint = typename Traits::DataPoint
 DataPoint given by user via Traits.
 
using IndexType = typename Traits::IndexType
 Type used to index points into the PointContainer.
 
using LeafSizeType = typename Traits::LeafSizeType
 Type used to store the size of leaf nodes.
 
using PointContainer = typename Traits::PointContainer
 Container for DataPoint used inside the KdTree.
 
using IndexContainer = typename Traits::IndexContainer
 Container for indices used inside the KdTree.
 
using NodeIndexType = typename Traits::NodeIndexType
 Type used to index nodes into the NodeContainer.
 
using NodeType = typename Traits::NodeType
 Type of nodes used inside the KdTree.
 
using NodeContainer = typename Traits::NodeContainer
 Container for nodes used inside the KdTree.
 
using Scalar = typename DataPoint::Scalar
 Scalar given by user via DataPoint.
 
using VectorType = typename DataPoint::VectorType
 VectorType given by user via DataPoint.
 
using AabbType = typename NodeType::AabbType
 Bounding box type given by user via NodeType.
 

Public Member Functions

template<typename PointUserContainer , typename Converter >
void build (PointUserContainer &&points, Converter c)
 Generate a tree from a custom contained type converted using the specified converter.
 
template<typename PointUserContainer >
void build (PointUserContainer &&points)
 Generate a tree from a custom contained type converted using DefaultConverter.
 
void clear ()
 Clear tree data.
 
NodeIndexType node_count () const
 
IndexType sample_count () const
 
IndexType point_count () const
 
NodeIndexType leaf_count () const
 
PointContainerpoints ()
 
const PointContainerpoints () const
 
const NodeContainernodes () const
 
const IndexContainersamples () const
 
LeafSizeType min_cell_size () const
 Read leaf min size.
 
void set_min_cell_size (LeafSizeType min_cell_size)
 Write leaf min size.
 
IndexType pointFromSample (IndexType sample_index) const
 Return the point index associated with the specified sample index.
 
DataPointpointDataFromSample (IndexType sample_index)
 Return the DataPoint associated with the specified sample index.
 
const DataPointpointDataFromSample (IndexType sample_index) const
 Return the DataPoint associated with the specified sample index.
 
KdTreeKNearestPointQuery< Traits > k_nearest_neighbors (const VectorType &point, IndexType k) const
 
KdTreeKNearestIndexQuery< Traits > k_nearest_neighbors (IndexType index, IndexType k) const
 
KdTreeNearestPointQuery< Traits > nearest_neighbor (const VectorType &point) const
 
KdTreeNearestIndexQuery< Traits > nearest_neighbor (IndexType index) const
 
KdTreeRangePointQuery< Traits > range_neighbors (const VectorType &point, Scalar r) const
 
KdTreeRangeIndexQuery< Traits > range_neighbors (IndexType index, Scalar r) const
 
bool valid () const
 
void print (std::ostream &os, bool verbose=false) const
 
template<typename PointUserContainer , typename Converter >
void build (PointUserContainer &&points, Converter c)
 
template<typename PointUserContainer , typename IndexUserContainer , typename Converter >
void buildWithSampling (PointUserContainer &&points, IndexUserContainer sampling, Converter c)
 

Static Public Attributes

static constexpr std::size_t MAX_NODE_COUNT = NodeType::MAX_COUNT
 The maximum number of nodes that the kd-tree can have.
 
static constexpr std::size_t MAX_POINT_COUNT = std::size_t(2) << sizeof(IndexType)*8
 The maximum number of points that can be stored in the kd-tree.
 
static constexpr int MAX_DEPTH = Traits::MAX_DEPTH
 The maximum depth of the kd-tree.
 
static constexpr bool SUPPORTS_SUBSAMPLING = false
 

Protected Member Functions

template<typename PointUserContainer , typename IndexUserContainer , typename Converter >
void buildWithSampling (PointUserContainer &&points, IndexUserContainer sampling, Converter c)
 Generate a tree sampled from a custom contained type converted using a Converter
 
template<typename PointUserContainer , typename IndexUserContainer >
void buildWithSampling (PointUserContainer &&points, IndexUserContainer sampling)
 Generate a tree sampled from a custom contained type converted using a KdTreeBase::DefaultConverter.
 

Protected Attributes

PointContainer m_points
 
NodeContainer m_nodes
 
IndexContainer m_indices
 
LeafSizeType m_min_cell_size {64}
 Minimal number of points per leaf.
 
NodeIndexType m_leaf_count {0}
 Number of leaves in the Kdtree (computed during construction)
 

Detailed Description

template<typename Traits>
class Ponca::KdTreeBase< Traits >

[KdTreeSparse type definition]

Customizable base class for KdTree datastructure implementations

See also
Ponca::KdTreeDense
Ponca::KdTreeSparse
Template Parameters
TraitsTraits type providing the types and constants used by the kd-tree. Must have the same interface as the default traits type.
See also
KdTreeDefaultTraits for the trait interface documentation.

Definition at line 103 of file kdTree.h.

Member Typedef Documentation

◆ AabbType

template<typename Traits >
using Ponca::KdTreeBase< Traits >::AabbType = typename NodeType::AabbType

Bounding box type given by user via NodeType.

Definition at line 117 of file kdTree.h.

◆ DataPoint

template<typename Traits >
using Ponca::KdTreeBase< Traits >::DataPoint = typename Traits::DataPoint

DataPoint given by user via Traits.

Definition at line 106 of file kdTree.h.

◆ IndexContainer

template<typename Traits >
using Ponca::KdTreeBase< Traits >::IndexContainer = typename Traits::IndexContainer

Container for indices used inside the KdTree.

Definition at line 110 of file kdTree.h.

◆ IndexType

template<typename Traits >
using Ponca::KdTreeBase< Traits >::IndexType = typename Traits::IndexType

Type used to index points into the PointContainer.

Definition at line 107 of file kdTree.h.

◆ LeafSizeType

template<typename Traits >
using Ponca::KdTreeBase< Traits >::LeafSizeType = typename Traits::LeafSizeType

Type used to store the size of leaf nodes.

Definition at line 108 of file kdTree.h.

◆ NodeContainer

template<typename Traits >
using Ponca::KdTreeBase< Traits >::NodeContainer = typename Traits::NodeContainer

Container for nodes used inside the KdTree.

Definition at line 113 of file kdTree.h.

◆ NodeIndexType

template<typename Traits >
using Ponca::KdTreeBase< Traits >::NodeIndexType = typename Traits::NodeIndexType

Type used to index nodes into the NodeContainer.

Definition at line 111 of file kdTree.h.

◆ NodeType

template<typename Traits >
using Ponca::KdTreeBase< Traits >::NodeType = typename Traits::NodeType

Type of nodes used inside the KdTree.

Definition at line 112 of file kdTree.h.

◆ PointContainer

template<typename Traits >
using Ponca::KdTreeBase< Traits >::PointContainer = typename Traits::PointContainer

Container for DataPoint used inside the KdTree.

Definition at line 109 of file kdTree.h.

◆ Scalar

template<typename Traits >
using Ponca::KdTreeBase< Traits >::Scalar = typename DataPoint::Scalar

Scalar given by user via DataPoint.

Definition at line 115 of file kdTree.h.

◆ VectorType

template<typename Traits >
using Ponca::KdTreeBase< Traits >::VectorType = typename DataPoint::VectorType

VectorType given by user via DataPoint.

Definition at line 116 of file kdTree.h.

Member Function Documentation

◆ build() [1/3]

template<typename Traits >
template<typename PointUserContainer >
void Ponca::KdTreeBase< Traits >::build ( PointUserContainer &&  points)
inline

Generate a tree from a custom contained type converted using DefaultConverter.

Template Parameters
PointUserContainerInput point container, transformed to PointContainer
Parameters
pointsInput points

Definition at line 169 of file kdTree.h.

◆ build() [2/3]

template<typename Traits >
template<typename PointUserContainer , typename Converter >
void Ponca::KdTreeBase< Traits >::build ( PointUserContainer &&  points,
Converter  c 
)
inline

Generate a tree from a custom contained type converted using the specified converter.

Template Parameters
PointUserContainerInput point container, transformed to PointContainer
IndexUserContainerInput sampling container, transformed to IndexContainer
Parameters
pointsInput points
cCast/Convert input point type to DataType

◆ build() [3/3]

template<typename Traits >
template<typename PointUserContainer , typename Converter >
void Ponca::KdTreeBase< Traits >::build ( PointUserContainer &&  points,
Converter  c 
)
inline

Definition at line 11 of file kdTree.hpp.

◆ buildWithSampling() [1/3]

template<typename Traits >
template<typename PointUserContainer , typename IndexUserContainer >
void Ponca::KdTreeBase< Traits >::buildWithSampling ( PointUserContainer &&  points,
IndexUserContainer  sampling 
)
inlineprotected

Generate a tree sampled from a custom contained type converted using a KdTreeBase::DefaultConverter.

Template Parameters
PointUserContainerInput points, transformed to PointContainer
IndexUserContainerInput sampling, transformed to IndexContainer
Parameters
pointsInput points
samplingSamples used in the tree

Definition at line 326 of file kdTree.h.

◆ buildWithSampling() [2/3]

template<typename Traits >
template<typename PointUserContainer , typename IndexUserContainer , typename Converter >
void Ponca::KdTreeBase< Traits >::buildWithSampling ( PointUserContainer &&  points,
IndexUserContainer  sampling,
Converter  c 
)
inlineprotected

Generate a tree sampled from a custom contained type converted using a Converter

Template Parameters
PointUserContainerInput point, transformed to PointContainer
IndexUserContainerInput sampling, transformed to IndexContainer
Converter
Parameters
pointsInput points
samplingIndices of points used in the tree
cCast/Convert input point type to DataType

◆ buildWithSampling() [3/3]

template<typename Traits >
template<typename PointUserContainer , typename IndexUserContainer , typename Converter >
void Ponca::KdTreeBase< Traits >::buildWithSampling ( PointUserContainer &&  points,
IndexUserContainer  sampling,
Converter  c 
)
inline

Definition at line 121 of file kdTree.hpp.

◆ clear()

template<typename Traits >
void KdTreeBase::clear ( )
inline

Clear tree data.

Definition at line 19 of file kdTree.hpp.

◆ k_nearest_neighbors() [1/2]

template<typename Traits >
KdTreeKNearestPointQuery< Traits > Ponca::KdTreeBase< Traits >::k_nearest_neighbors ( const VectorType point,
IndexType  k 
) const
inline

Definition at line 260 of file kdTree.h.

◆ k_nearest_neighbors() [2/2]

template<typename Traits >
KdTreeKNearestIndexQuery< Traits > Ponca::KdTreeBase< Traits >::k_nearest_neighbors ( IndexType  index,
IndexType  k 
) const
inline

Definition at line 265 of file kdTree.h.

◆ leaf_count()

template<typename Traits >
NodeIndexType Ponca::KdTreeBase< Traits >::leaf_count ( ) const
inline

Definition at line 194 of file kdTree.h.

◆ min_cell_size()

template<typename Traits >
LeafSizeType Ponca::KdTreeBase< Traits >::min_cell_size ( ) const
inline

Read leaf min size.

Definition at line 222 of file kdTree.h.

◆ nearest_neighbor() [1/2]

template<typename Traits >
KdTreeNearestPointQuery< Traits > Ponca::KdTreeBase< Traits >::nearest_neighbor ( const VectorType point) const
inline

Definition at line 270 of file kdTree.h.

◆ nearest_neighbor() [2/2]

template<typename Traits >
KdTreeNearestIndexQuery< Traits > Ponca::KdTreeBase< Traits >::nearest_neighbor ( IndexType  index) const
inline

Definition at line 275 of file kdTree.h.

◆ node_count()

template<typename Traits >
NodeIndexType Ponca::KdTreeBase< Traits >::node_count ( ) const
inline

Definition at line 179 of file kdTree.h.

◆ nodes()

template<typename Traits >
const NodeContainer & Ponca::KdTreeBase< Traits >::nodes ( ) const
inline

Definition at line 209 of file kdTree.h.

◆ point_count()

template<typename Traits >
IndexType Ponca::KdTreeBase< Traits >::point_count ( ) const
inline

Definition at line 189 of file kdTree.h.

◆ pointDataFromSample() [1/2]

template<typename Traits >
DataPoint & Ponca::KdTreeBase< Traits >::pointDataFromSample ( IndexType  sample_index)
inline

Return the DataPoint associated with the specified sample index.

Note
Convenience function, equivalent to point_data()[pointFromSample(sample_index)]

Definition at line 245 of file kdTree.h.

◆ pointDataFromSample() [2/2]

template<typename Traits >
const DataPoint & Ponca::KdTreeBase< Traits >::pointDataFromSample ( IndexType  sample_index) const
inline

Return the DataPoint associated with the specified sample index.

Note
Convenience function, equivalent to point_data()[pointFromSample(sample_index)]

Definition at line 253 of file kdTree.h.

◆ pointFromSample()

template<typename Traits >
IndexType Ponca::KdTreeBase< Traits >::pointFromSample ( IndexType  sample_index) const
inline

Return the point index associated with the specified sample index.

Definition at line 237 of file kdTree.h.

◆ points() [1/2]

template<typename Traits >
PointContainer & Ponca::KdTreeBase< Traits >::points ( )
inline

Definition at line 199 of file kdTree.h.

◆ points() [2/2]

template<typename Traits >
const PointContainer & Ponca::KdTreeBase< Traits >::points ( ) const
inline

Definition at line 204 of file kdTree.h.

◆ print()

template<typename Traits >
void KdTreeBase::print ( std::ostream &  os,
bool  verbose = false 
) const
inline

Definition at line 75 of file kdTree.hpp.

◆ range_neighbors() [1/2]

template<typename Traits >
KdTreeRangePointQuery< Traits > Ponca::KdTreeBase< Traits >::range_neighbors ( const VectorType point,
Scalar  r 
) const
inline

Definition at line 280 of file kdTree.h.

◆ range_neighbors() [2/2]

template<typename Traits >
KdTreeRangeIndexQuery< Traits > Ponca::KdTreeBase< Traits >::range_neighbors ( IndexType  index,
Scalar  r 
) const
inline

Definition at line 285 of file kdTree.h.

◆ sample_count()

template<typename Traits >
IndexType Ponca::KdTreeBase< Traits >::sample_count ( ) const
inline

Definition at line 184 of file kdTree.h.

◆ samples()

template<typename Traits >
const IndexContainer & Ponca::KdTreeBase< Traits >::samples ( ) const
inline

Definition at line 214 of file kdTree.h.

◆ set_min_cell_size()

template<typename Traits >
void Ponca::KdTreeBase< Traits >::set_min_cell_size ( LeafSizeType  min_cell_size)
inline

Write leaf min size.

Definition at line 228 of file kdTree.h.

◆ valid()

template<typename Traits >
bool KdTreeBase::valid ( ) const
inline

Definition at line 28 of file kdTree.hpp.

Member Data Documentation

◆ m_indices

template<typename Traits >
IndexContainer Ponca::KdTreeBase< Traits >::m_indices
protected

Definition at line 299 of file kdTree.h.

◆ m_leaf_count

template<typename Traits >
NodeIndexType Ponca::KdTreeBase< Traits >::m_leaf_count {0}
protected

Number of leaves in the Kdtree (computed during construction)

Definition at line 302 of file kdTree.h.

◆ m_min_cell_size

template<typename Traits >
LeafSizeType Ponca::KdTreeBase< Traits >::m_min_cell_size {64}
protected

Minimal number of points per leaf.

Definition at line 301 of file kdTree.h.

◆ m_nodes

template<typename Traits >
NodeContainer Ponca::KdTreeBase< Traits >::m_nodes
protected

Definition at line 298 of file kdTree.h.

◆ m_points

template<typename Traits >
PointContainer Ponca::KdTreeBase< Traits >::m_points
protected

Definition at line 297 of file kdTree.h.

◆ MAX_DEPTH

template<typename Traits >
constexpr int Ponca::KdTreeBase< Traits >::MAX_DEPTH = Traits::MAX_DEPTH
staticconstexpr

The maximum depth of the kd-tree.

Definition at line 125 of file kdTree.h.

◆ MAX_NODE_COUNT

template<typename Traits >
constexpr std::size_t Ponca::KdTreeBase< Traits >::MAX_NODE_COUNT = NodeType::MAX_COUNT
staticconstexpr

The maximum number of nodes that the kd-tree can have.

Definition at line 120 of file kdTree.h.

◆ MAX_POINT_COUNT

template<typename Traits >
constexpr std::size_t Ponca::KdTreeBase< Traits >::MAX_POINT_COUNT = std::size_t(2) << sizeof(IndexType)*8
staticconstexpr

The maximum number of points that can be stored in the kd-tree.

Definition at line 122 of file kdTree.h.

◆ SUPPORTS_SUBSAMPLING

template<typename Traits >
constexpr bool Ponca::KdTreeBase< Traits >::SUPPORTS_SUBSAMPLING = false
staticconstexpr

Definition at line 127 of file kdTree.h.