Geogram  Version 1.9.1
A programming library of geometric algorithms
GEO::BalancedKdTree Class Reference

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

#include <geogram/points/kd_tree.h>

Inheritance diagram for GEO::BalancedKdTree:
GEO::KdTree GEO::NearestNeighborSearch GEO::Counted

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_tsplitting_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_tpoint_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 NearestNeighborSearchcreate (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.
 

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]dimdimension 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]bfirst index of the point sequence
[in]eone 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_indexindex of the node that represents the subtree to create
[in]bfirst index of the point sequence in the subtree
[in]eone 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]na node index
[in]bthe first point in the node
[in]eone position past the last point in the node
[out]left_childthe node index of the left child of node n.
[out]right_childthe node index of the right child of node n.
[out]splitting_coordThe coordinate along which n is split.
[out]mthe 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_valThe 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_idnode index of the subtree
[in]bfirst index of the points sequence in the subtree
[in]eone 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: