ellipsoid_tree::KDTree Class Reference

k-nearest-neighbor kd-tree over a fixed set of points. More...

#include <ellipsoid_tree/kd_tree.hpp>

Public Member Functions
	KDTree ()=default
	Constructs an empty tree; call build() before querying.
	KDTree (const Eigen::Ref< const Eigen::MatrixXd > &points)
	Builds an index over the columns of a (dim, n) matrix (one point per column).
void	build (const Eigen::Ref< const Eigen::MatrixXd > &input_points)
	(Re)builds the median-split layout over the columns of a (dim, n) matrix, snapshotting block_size for this layout.
int	size () const
	Number of indexed points.
int	dim () const
	Spatial dimension of the indexed points.
const Eigen::MatrixXd &	ordered_points () const
	Structure inspection (e.g.
int	external_index (int internal_index) const
	Internal (tree-order) index -> external (original input) index.
int	built_block_size () const
	Leaf-block size the current layout was built with.
std::pair< Eigen::MatrixXi, Eigen::MatrixXd >	query (const Eigen::Ref< const Eigen::MatrixXd > &query_points, int num_neighbors, int num_threads=0) const
	k nearest neighbors of each query point (columns).

Public Attributes
int	block_size = 32
	Leaf ranges of at most this many points are scanned linearly.

Detailed Description

k-nearest-neighbor kd-tree over a fixed set of points.

Construct from a (dim, n) matrix whose columns are the points, then call query() for the k nearest neighbors of one or more query points.

Constructor & Destructor Documentation

KDTree() [1/2]

ellipsoid_tree::KDTree::KDTree ( )

default

Constructs an empty tree; call build() before querying.

KDTree() [2/2]

ellipsoid_tree::KDTree::KDTree ( const Eigen::Ref< const Eigen::MatrixXd > &  points )

inlineexplicit

Builds an index over the columns of a (dim, n) matrix (one point per column).

Member Function Documentation

build()

void ellipsoid_tree::KDTree::build ( const Eigen::Ref< const Eigen::MatrixXd > &  input_points )

inline

(Re)builds the median-split layout over the columns of a (dim, n) matrix, snapshotting block_size for this layout.

size()

int ellipsoid_tree::KDTree::size ( ) const

inline

Number of indexed points.

dim()

int ellipsoid_tree::KDTree::dim ( ) const

inline

Spatial dimension of the indexed points.

ordered_points()

const Eigen::MatrixXd & ellipsoid_tree::KDTree::ordered_points ( ) const

inline

Structure inspection (e.g.

for visualization): points permuted into tree order, the internal->external index map, and the leaf-block size the current layout was built with.

external_index()

int ellipsoid_tree::KDTree::external_index ( int  internal_index ) const

inline

Internal (tree-order) index -> external (original input) index.

built_block_size()

int ellipsoid_tree::KDTree::built_block_size ( ) const

inline

Leaf-block size the current layout was built with.

query()

std::pair< Eigen::MatrixXi, Eigen::MatrixXd > ellipsoid_tree::KDTree::query ( const Eigen::Ref< const Eigen::MatrixXd > &  query_points, int  num_neighbors, int  num_threads = 0  ) const

inline

k nearest neighbors of each query point (columns).

Returns (indices, squared distances), each of shape (k_eff, num_queries) with k_eff = min(k, size()), sorted by increasing distance per query.

Member Data Documentation

block_size

int ellipsoid_tree::KDTree::block_size = 32

Leaf ranges of at most this many points are scanned linearly.

---

The documentation for this class was generated from the following file:

• ellipsoid_tree/kd_tree.hpp