Base class for all Kd-tree implementations. More...

#include <geogram/points/kd_tree.h>

Inheritance diagram for GEO::KdTree:

Classes
struct	NearestNeighbors
	The context for traversing a KdTree. More...

Public Member Functions
	KdTree (coord_index_t dim)
	KdTree constructor. More...

void	set_points (index_t nb_points, const double *points) override
	Sets the points and create the search data structure. More...

bool	stride_supported () const override
	Tests whether the stride variant of set_points() is supported. More...

void	set_points (index_t nb_points, const double *points, index_t stride) override
	Sets the points and create the search data structure. More...

void	get_nearest_neighbors (index_t nb_neighbors, const double query_point, index_t neighbors, double *neighbors_sq_dist) const override
	Finds the nearest neighbors of a point given by coordinates. More...

void	get_nearest_neighbors (index_t nb_neighbors, const double query_point, index_t neighbors, double *neighbors_sq_dist, KeepInitialValues) const override
	Finds the nearest neighbors of a point given by coordinates. More...

void	get_nearest_neighbors (index_t nb_neighbors, index_t query_point, index_t neighbors, double neighbors_sq_dist) const override
	Finds the nearest neighbors of a point given by coordinates. More...

virtual void	get_nearest_neighbors_recursive (index_t node_index, index_t b, index_t e, double bbox_min, double bbox_max, double bbox_dist, const double *query_point, NearestNeighbors &neighbors) const
	The recursive function to implement KdTree traversal and nearest neighbors computation. More...

void	init_bbox_and_bbox_dist_for_traversal (double bbox_min, double bbox_max, double &box_dist, const double *query_point) const
	Initializes bounding box and box distance for Kd-Tree traversal. More...

index_t	root () const
	Gets the root node. More...

Public Member Functions inherited from GEO::NearestNeighborSearch
index_t	get_nearest_neighbor (const double *query_point) const
	Nearest neighbor search. More...

coord_index_t	dimension () const
	Gets the dimension of the points. More...

index_t	nb_points () const
	Gets the number of points. More...

const double *	point_ptr (index_t i) const
	Gets a point by its index. More...

bool	exact () const
	Search can be exact or approximate. Approximate search may be faster. More...

virtual void	set_exact (bool x)
	Search can be exact or approximate. Approximate search may be faster. More...

Public Member Functions inherited from GEO::Counted
void	ref () const
	Increments the reference count. More...

void	unref () const
	Decrements the reference count. More...

bool	is_shared () const
	Check if the object is shared. More...

int	nb_refs () const
	Gets the number of references that point to this object. More...

Protected Member Functions
virtual index_t	build_tree ()=0
	Builds the tree. More...

virtual void	get_node (index_t n, index_t b, index_t e, index_t &left_child, index_t &right_child, coord_index_t &splitting_coord, index_t &m, double &splitting_val) const =0
	Gets all the attributes of a node. More...

virtual void	get_nearest_neighbors_leaf (index_t node_index, index_t b, index_t e, const double *query_point, NearestNeighbors &neighbors) const
	The recursive function to implement KdTree traversal and nearest neighbors computation in a leaf. More...

void	get_minmax (index_t b, index_t e, coord_index_t coord, double &minval, double &maxval) const
	Computes the minimum and maximum point coordinates along a coordinate. More...

double	spread (index_t b, index_t e, coord_index_t coord) const
	Computes the extent of a point sequence along a given coordinate. More...

	~KdTree () override
	KdTree destructor.

Protected Member Functions inherited from GEO::NearestNeighborSearch
	NearestNeighborSearch (coord_index_t dimension)
	Constructs a NearestNeighborSearch. More...

	~NearestNeighborSearch () override
	NearestNeighborSearch destructor.

Protected Member Functions inherited from GEO::Counted
	Counted ()
	Creates a reference counted object. More...

virtual	~Counted ()
	Destroys a reference counted object. More...

Protected Attributes
vector< index_t >	point_index_

vector< double >	bbox_min_

vector< double >	bbox_max_

index_t	root_

Protected Attributes inherited from GEO::NearestNeighborSearch
coord_index_t	dimension_

index_t	nb_points_

index_t	stride_

const double *	points_

bool	exact_

Static Protected Attributes
static const index_t	MAX_LEAF_SIZE = 16
	Number of points stored in the leafs of the tree.

Additional Inherited Members
Static Public Member Functions inherited from GEO::NearestNeighborSearch
static NearestNeighborSearch *	create (coord_index_t dimension, const std::string &name="default")
	Creates a new search algorithm. More...

Static Public Member Functions inherited from GEO::Counted
static void	ref (const Counted *counted)
	Increments the reference count. More...

static void	unref (const Counted *counted)
	Decrements the reference count. More...

Related Functions inherited from GEO::NearestNeighborSearch
typedef SmartPointer< NearestNeighborSearch >	NearestNeighborSearch_var
	A smart pointer that contains a NearestNeighborSearch object.

typedef Factory1< NearestNeighborSearch, coord_index_t >	NearestNeighborSearchFactory
	NearestNeighborSearch Factory. More...

Detailed Description

Base class for all Kd-tree implementations.

Definition at line 57 of file kd_tree.h.

Constructor & Destructor Documentation

◆ KdTree()

GEO::KdTree::KdTree ( coord_index_t dim )

KdTree constructor.

Parameters

[in] dim dimension of the points.

Member Function Documentation

◆ build_tree()

virtual index_t GEO::KdTree::build_tree ( )

protectedpure virtual

Builds the tree.

Returns: the index of the root node.

Implemented in GEO::AdaptiveKdTree, and GEO::BalancedKdTree.

◆ get_minmax()

void GEO::KdTree::get_minmax	(	index_t	b,
		index_t	e,
		coord_index_t	coord,
		double &	minval,
		double &	maxval
	)		const

inlineprotected

Computes the minimum and maximum point coordinates along a coordinate.

Parameters

[in]	b	first index of the point sequence
[in]	e	one position past the last index of the point sequence
[in]	coord	coordinate along which the extent is measured
[out]	minval,maxval	minimum and maximum

Definition at line 398 of file kd_tree.h.

◆ get_nearest_neighbors() [1/3]

void GEO::KdTree::get_nearest_neighbors	(	index_t	nb_neighbors,
		const double *	query_point,
		index_t *	neighbors,
		double *	neighbors_sq_dist
	)		const

overridevirtual

Finds the nearest neighbors of a point given by coordinates.

Parameters

[in]	nb_neighbors	number of neighbors to be searched. Should be smaller or equal to nb_points() (else it triggers an assertion)
[in]	query_point	as an array of dimension() doubles
[out]	neighbors	array of nb_neighbors index_t
[out]	neighbors_sq_dist	array of nb_neighbors doubles

Implements GEO::NearestNeighborSearch.

◆ get_nearest_neighbors() [2/3]

void GEO::KdTree::get_nearest_neighbors	(	index_t	nb_neighbors,
		const double *	query_point,
		index_t *	neighbors,
		double *	neighbors_sq_dist,
		KeepInitialValues
	)		const

overridevirtual

Finds the nearest neighbors of a point given by coordinates.

Parameters

[in]	nb_neighbors	number of neighbors to be searched. Should be smaller or equal to nb_points() (else it triggers an assertion)
[in]	query_point	as an array of dimension() doubles
[out]	neighbors	array of nb_neighbors index_t
[out]	neighbors_sq_dist	array of nb_neighbors doubles

Reimplemented from GEO::NearestNeighborSearch.

◆ get_nearest_neighbors() [3/3]

void GEO::KdTree::get_nearest_neighbors	(	index_t	nb_neighbors,
		index_t	query_point,
		index_t *	neighbors,
		double *	neighbors_sq_dist
	)		const

overridevirtual

Finds the nearest neighbors of a point given by coordinates.

Parameters

[in]	nb_neighbors	number of neighbors to be searched. Should be smaller or equal to nb_points() (else it triggers an assertion)
[in]	query_point	as an array of dimension() doubles
[out]	neighbors	array of nb_neighbors index_t
[out]	neighbors_sq_dist	array of nb_neighbors doubles

Reimplemented from GEO::NearestNeighborSearch.

◆ get_nearest_neighbors_leaf()

virtual void GEO::KdTree::get_nearest_neighbors_leaf	(	index_t	node_index,
		index_t	b,
		index_t	e,
		const double *	query_point,
		NearestNeighbors &	neighbors
	)		const

protectedvirtual

The recursive function to implement KdTree traversal and nearest neighbors computation in a leaf.

Traverses the node_index leaf that corresponds to the [b,e) point sequence. Nearest neighbors are inserted into neighbors during traversal.

Parameters

[in]	node_index	index of the leaf to be traversed.
[in]	b	index of the first point in the leaf.
[in]	e	one position past the index of the last point in the leaf.
[in]	query_point	the query point
[in,out]	neighbors	the computed nearest neighbors

◆ get_nearest_neighbors_recursive()

virtual void GEO::KdTree::get_nearest_neighbors_recursive	(	index_t	node_index,
		index_t	b,
		index_t	e,
		double *	bbox_min,
		double *	bbox_max,
		double	bbox_dist,
		const double *	query_point,
		NearestNeighbors &	neighbors
	)		const

virtual

The recursive function to implement KdTree traversal and nearest neighbors computation.

Note: This is a lower-level function, most users will not use it.

Traverses the subtree under the node_index node that corresponds to the [b,e) point sequence. Nearest neighbors are inserted into neighbors during traversal.

Parameters

[in]	node_index	index of the current node in the Kd tree
[in]	b	index of the first point in the subtree under node `node_index`
[in]	e	one position past the index of the last point in the subtree under node `node_index`
[in,out]	bbox_min	coordinates of the lower corner of the bounding box. Allocated and managed by caller. Modified by the function and restored on exit.
[in,out]	bbox_max	coordinates of the upper corner of the bounding box. Allocated and managed by caller. Modified by the function and restored on exit.
[in]	bbox_dist	squared distance between the query point and a bounding box of the [b,e) point sequence. It is used to early prune traversals that do not generate nearest neighbors.
[in]	query_point	the query point
[in,out]	neighbors	the computed nearest neighbors

◆ get_node()

virtual void GEO::KdTree::get_node	(	index_t	n,
		index_t	b,
		index_t	e,
		index_t &	left_child,
		index_t &	right_child,
		coord_index_t &	splitting_coord,
		index_t &	m,
		double &	splitting_val
	)		const

protectedpure virtual

Gets all the attributes of a node.

This function is virtual, because indices can be either computed on the fly (as in BalancedKdTree) or stored (as in AdaptiveKdTree).

Parameters

[in]	n	a node index
[in]	b	the first point in the node
[in]	e	one position past the last point in the node
[out]	left_child	the node index of the left child of node `n`.
[out]	right_child	the node index of the right child of node `n`.
[out]	splitting_coord	The coordinate along which `n` is split.
[out]	m	the point m such that [b,m-1] corresponds to the points in the left child of `n` and [m,e-1] corresponds to the points in the right child of `n`.
[out]	splitting_val	The coordinate value that separates points in the left and right children.

Implemented in GEO::AdaptiveKdTree, and GEO::BalancedKdTree.

◆ init_bbox_and_bbox_dist_for_traversal()

void GEO::KdTree::init_bbox_and_bbox_dist_for_traversal	(	double *	bbox_min,
		double *	bbox_max,
		double &	box_dist,
		const double *	query_point
	)		const

Initializes bounding box and box distance for Kd-Tree traversal.

Note: This is a lower-level function, most users will not use it.

This functions needs to be called before get_nearest_neighbors_recursive()

Parameters

[out]	bbox_min	a pointer to an array of dimension() doubles, managed by client code (typically on the stack).
[out]	bbox_max	a pointer to an array of dimension() doubles, managed by client code (typically on the stack).
[out]	box_dist	the squared distance between the query point and the box.
[in]	query_point	a const pointer to the coordinates of the query point.

◆ root()

index_t GEO::KdTree::root ( ) const

inline

Gets the root node.

Returns: the index of the root node.

Definition at line 326 of file kd_tree.h.

◆ set_points() [1/2]

void GEO::KdTree::set_points	(	index_t	nb_points,
		const double *	points
	)

overridevirtual

Sets the points and create the search data structure.

Parameters

[in]	nb_points	number of points
[in]	points	an array of nb_points * dimension()

Reimplemented from GEO::NearestNeighborSearch.

◆ set_points() [2/2]

void GEO::KdTree::set_points	(	index_t	nb_points,
		const double *	points,
		index_t	stride
	)

overridevirtual

Sets the points and create the search data structure.

Parameters

[in]	nb_points	number of points
[in]	points	an array of nb_points * dimension()

Reimplemented from GEO::NearestNeighborSearch.

◆ spread()

double GEO::KdTree::spread	(	index_t	b,
		index_t	e,
		coord_index_t	coord
	)		const

inlineprotected

Computes the extent of a point sequence along a given coordinate.

Parameters

[in]	b	first index of the point sequence
[in]	e	one position past the last index of the point sequence
[in]	coord	coordinate along which the extent is measured

Returns: the extent of the sequence along the coordinate

Definition at line 419 of file kd_tree.h.

◆ stride_supported()

bool GEO::KdTree::stride_supported ( ) const

overridevirtual

Tests whether the stride variant of set_points() is supported.

Returns: true if stride different from dimension can be used in set_points(), false otherwise

Reimplemented from GEO::NearestNeighborSearch.

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

geogram/points/kd_tree.h

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Static Protected Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ KdTree()

Member Function Documentation

◆ build_tree()

◆ get_minmax()

◆ get_nearest_neighbors() [1/3]

◆ get_nearest_neighbors() [2/3]

◆ get_nearest_neighbors() [3/3]

◆ get_nearest_neighbors_leaf()

◆ get_nearest_neighbors_recursive()

◆ get_node()

◆ init_bbox_and_bbox_dist_for_traversal()

◆ root()

◆ set_points() [1/2]

◆ set_points() [2/2]

◆ spread()

◆ stride_supported()