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

Implements NearestNeighborSearch using an Adaptive Kd-tree. More...

#include <geogram/points/kd_tree.h>

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

Public Member Functions

 AdaptiveKdTree (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

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...
 
virtual index_t create_kd_tree_recursive (index_t b, index_t e, double *bbox_min, double *bbox_max)
 Creates the subtree under a node. More...
 
virtual void split_kd_node (index_t b, index_t e, double *bbox_min, double *bbox_max, index_t &m, coord_index_t &cut_dim, double &cut_val)
 Computes and stores the splitting coordinate and splitting value of the node node_index, that corresponds to the [b,e) points sequence. 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. More...
 
virtual void plane_split (index_t b, index_t e, coord_index_t coord, double val, index_t &br1, index_t &br2)
 Reorders the points in a sequence in such a way that the specified coordinate in the beginning of the sequence is smaller than the specified cutting value. More...
 
double point_coord (int index, coord_index_t coord)
 Gets a point coordinate by index and coordinate. More...
 
index_t nb_nodes () const
 Gets the number of nodes. More...
 
virtual index_t new_node ()
 Creates a new 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...
 

Protected Attributes

vector< coord_index_tsplitting_coord_
 One per node, splitting coordinate.
 
vector< double > splitting_val_
 One per node, splitting coordinate value.
 
vector< index_tnode_m_
 One per node, node splitting index. More...
 
vector< index_tnode_right_child_
 One per node, right child index. More...
 
- 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 an Adaptive Kd-tree.

This corresponds to the same algorithm as in the ANN library (by David Mount), but stored in flat arrays (rather than dynamically allocated tree structure). The data structure is more compact, and slightly faster. As compared with BalancedKdTree, when the distribution of points is heterogeneous, it will be faster, at the expensen of a slightly more requires storage (uses an additional 8 bytes per node), and construction is not parallel, because size of left subtree needs to be known before starting constructing the right subtree. This does not make a big difference since in general Kd-tree query time dominates construction time in most of the algorithms that use a Kd-tree.

Definition at line 570 of file kd_tree.h.

Constructor & Destructor Documentation

◆ AdaptiveKdTree()

GEO::AdaptiveKdTree::AdaptiveKdTree ( coord_index_t  dim)

Creates a new BalancedKdTree.

Parameters
[in]dimdimension of the points

Member Function Documentation

◆ build_tree()

index_t GEO::AdaptiveKdTree::build_tree ( )
overrideprotectedvirtual

Builds the tree.

Returns
the index of the root node.

Implements GEO::KdTree.

◆ create_kd_tree_recursive()

virtual index_t GEO::AdaptiveKdTree::create_kd_tree_recursive ( index_t  b,
index_t  e,
double *  bbox_min,
double *  bbox_max 
)
protectedvirtual

Creates the subtree under a node.

Parameters
[in]bfirst index of the point sequence in the subtree
[in]eone position past the last index of the point index in the subtree
[in,out]bbox_mincoordinates of the lower corner of the bounding box. Allocated and managed by caller. Modified by the function and restored on exit.
Returns
the node index of the root of the created tree.

◆ get_node()

void GEO::AdaptiveKdTree::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.

◆ nb_nodes()

index_t GEO::AdaptiveKdTree::nb_nodes ( ) const
inlineprotected

Gets the number of nodes.

Returns
the number of nodes.

Definition at line 667 of file kd_tree.h.

◆ new_node()

virtual index_t GEO::AdaptiveKdTree::new_node ( )
protectedvirtual

Creates a new node.

Returns
the index of the newly created node.

◆ plane_split()

virtual void GEO::AdaptiveKdTree::plane_split ( index_t  b,
index_t  e,
coord_index_t  coord,
double  val,
index_t br1,
index_t br2 
)
protectedvirtual

Reorders the points in a sequence in such a way that the specified coordinate in the beginning of the sequence is smaller than the specified cutting value.

Parameters
[in]bfirst index of the point sequence
[in]eone position past the last index of the point sequence
[in]coordcoordinate along which the extent is measured
[in]valthe cutting value
[out]br1,br2on exit, point indices are reordered in such a way that:
  • the sequence b .. br1-1 has points with coord smaller than val
  • the sequence br1 .. br2-1 has points with coord equal to val
  • the sequence br2 .. e-1 has points with coord larger than val

◆ point_coord()

double GEO::AdaptiveKdTree::point_coord ( int  index,
coord_index_t  coord 
)
inlineprotected

Gets a point coordinate by index and coordinate.

Parameters
[in]indexindex of the point.
[in]coordcoordinate, in 0..dimension()-1
Returns
the coordinate of the point, after re-numerotation.

Definition at line 653 of file kd_tree.h.

◆ split_kd_node()

virtual void GEO::AdaptiveKdTree::split_kd_node ( index_t  b,
index_t  e,
double *  bbox_min,
double *  bbox_max,
index_t m,
coord_index_t cut_dim,
double &  cut_val 
)
protectedvirtual

Computes and stores the splitting coordinate and splitting value of the node node_index, that corresponds to the [b,e) points sequence. 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.

Parameters
[in,out]bbox_mincoordinates of the lower corner of the bounding box. Allocated and managed by caller. Modified by the function and restored on exit.
[out]mthe point index.
[out]cut_dimthe coordinate along which the node is split.
[out]cut_valthe splitting value.

Member Data Documentation

◆ node_m_

vector<index_t> GEO::AdaptiveKdTree::node_m_
protected

One per node, node splitting index.

Children points sequences:

  • left child points: b .. node_m_[node_index]-1
  • right child points: node_m_[node_index] .. e-1

Definition at line 694 of file kd_tree.h.

◆ node_right_child_

vector<index_t> GEO::AdaptiveKdTree::node_right_child_
protected

One per node, right child index.

left child is implicit (left_child(n) = n+1).

Definition at line 700 of file kd_tree.h.


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