Implements NearestNeighborSearch using a balanced Kd-tree. More...

#include <geogram/points/kd_tree.h>

Inheritance diagram for GEO::BalancedKdTree:

Public Member Functions
	BalancedKdTree (coord_index_t dim)
	Creates a new BalancedKdTree. More...

Public Member Functions inherited from GEO::KdTree
	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
	~BalancedKdTree () override
	BalancedKdTree destructor.

coord_index_t	best_splitting_coord (index_t b, index_t e)
	Computes the coordinate along which a point sequence will be split. More...

void	create_kd_tree_recursive (index_t node_index, index_t b, index_t e)
	Creates the subtree under a node. More...

index_t	split_kd_node (index_t node_index, index_t b, index_t e)
	Computes and stores the splitting coordinate and splitting value of the node node_index, that corresponds to the [b,e) points sequence. More...

index_t	build_tree () override
	Builds the tree. More...

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 override
	Gets all the attributes of a node. More...

Protected Member Functions inherited from GEO::KdTree
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...

Static Protected Member Functions
static index_t	max_node_index (index_t node_id, index_t b, index_t e)
	Returns the maximum node index in subtree. More...

Protected Attributes
vector< coord_index_t >	splitting_coord_
	One per node, splitting coordinate.

vector< double >	splitting_val_
	One per node, splitting coordinate value.

index_t	m0_
	Indices for multithreaded tree construction.

index_t	m1_

index_t	m2_

index_t	m3_

index_t	m4_

index_t	m5_

index_t	m6_

index_t	m7_

index_t	m8_

Protected Attributes inherited from GEO::KdTree
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_

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

Static Protected Attributes inherited from GEO::KdTree
static const index_t	MAX_LEAF_SIZE = 16
	Number of points stored in the leafs of the tree.

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

Implements NearestNeighborSearch using a balanced Kd-tree.

The tree is perfectly balanced, thus no combinatorics is stored: the two children of node n are 2n+1 and 2n+2. For regular to moderately irregular pointsets it works well. For highly irregular pointsets, AdaptiveKdTree is more efficient.

Definition at line 447 of file kd_tree.h.

Constructor & Destructor Documentation

◆ BalancedKdTree()

GEO::BalancedKdTree::BalancedKdTree ( coord_index_t dim )

Creates a new BalancedKdTree.

Parameters

[in] dim dimension of the points

Member Function Documentation

◆ best_splitting_coord()

coord_index_t GEO::BalancedKdTree::best_splitting_coord	(	index_t	b,
		index_t	e
	)

protected

Computes the coordinate along which a point sequence will be split.

Parameters

[in]	b	first index of the point sequence
[in]	e	one position past the last index of the point sequence

◆ build_tree()

index_t GEO::BalancedKdTree::build_tree ( )

overrideprotectedvirtual

Builds the tree.

Returns: the index of the root node.

Implements GEO::KdTree.

◆ create_kd_tree_recursive()

void GEO::BalancedKdTree::create_kd_tree_recursive	(	index_t	node_index,
		index_t	b,
		index_t	e
	)

inlineprotected

Creates the subtree under a node.

Parameters

[in]	node_index	index of the node that represents the subtree to create
[in]	b	first index of the point sequence in the subtree
[in]	e	one position past the last index of the point index in the subtree

Definition at line 497 of file kd_tree.h.

◆ get_node()

void GEO::BalancedKdTree::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

overrideprotectedvirtual

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.

Implements GEO::KdTree.

◆ max_node_index()

static index_t GEO::BalancedKdTree::max_node_index	(	index_t	node_id,
		index_t	b,
		index_t	e
	)

inlinestaticprotected

Returns the maximum node index in subtree.

Parameters

[in]	node_id	node index of the subtree
[in]	b	first index of the points sequence in the subtree
[in]	e	one position past the last index of the point sequence in the subtree

Definition at line 468 of file kd_tree.h.

◆ split_kd_node()

index_t GEO::BalancedKdTree::split_kd_node	(	index_t	node_index,
		index_t	b,
		index_t	e
	)

protected

Computes and stores the splitting coordinate and splitting value of the node node_index, that corresponds to the [b,e) points sequence.

Returns: a node index m. The point sequences [b,m) and [m,e) correspond to the left child (2*node_index) and right child (2*node_index+1) of node_index.

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

geogram/points/kd_tree.h

Public Member Functions

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ BalancedKdTree()

Member Function Documentation

◆ best_splitting_coord()

◆ build_tree()

◆ create_kd_tree_recursive()

◆ get_node()

◆ max_node_index()

◆ split_kd_node()