Geogram  Version 1.9.1
A programming library of geometric algorithms
GEO::KdTree Class Referenceabstract

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

#include <geogram/points/kd_tree.h>

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

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

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

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]dimdimension 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]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
[out]minval,maxvalminimum 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_neighborsnumber of neighbors to be searched. Should be smaller or equal to nb_points() (else it triggers an assertion)
[in]query_pointas an array of dimension() doubles
[out]neighborsarray of nb_neighbors index_t
[out]neighbors_sq_distarray 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_neighborsnumber of neighbors to be searched. Should be smaller or equal to nb_points() (else it triggers an assertion)
[in]query_pointas an array of dimension() doubles
[out]neighborsarray of nb_neighbors index_t
[out]neighbors_sq_distarray 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_neighborsnumber of neighbors to be searched. Should be smaller or equal to nb_points() (else it triggers an assertion)
[in]query_pointas an array of dimension() doubles
[out]neighborsarray of nb_neighbors index_t
[out]neighbors_sq_distarray 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_indexindex of the leaf to be traversed.
[in]bindex of the first point in the leaf.
[in]eone position past the index of the last point in the leaf.
[in]query_pointthe query point
[in,out]neighborsthe 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_indexindex of the current node in the Kd tree
[in]bindex of the first point in the subtree under node node_index
[in]eone position past the index of the last point in the subtree under node node_index
[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.
[in,out]bbox_maxcoordinates of the upper corner of the bounding box. Allocated and managed by caller. Modified by the function and restored on exit.
[in]bbox_distsquared 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_pointthe query point
[in,out]neighborsthe 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]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.

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_mina pointer to an array of dimension() doubles, managed by client code (typically on the stack).
[out]bbox_maxa pointer to an array of dimension() doubles, managed by client code (typically on the stack).
[out]box_distthe squared distance between the query point and the box.
[in]query_pointa 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_pointsnumber of points
[in]pointsan 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_pointsnumber of points
[in]pointsan 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]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
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: