Geogram
Version 1.9.1
A programming library of geometric algorithms
|
Base class for all Kd-tree implementations. More...
#include <geogram/points/kd_tree.h>
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... | |
GEO::KdTree::KdTree | ( | coord_index_t | dim | ) |
KdTree constructor.
[in] | dim | dimension of the points. |
|
protectedpure virtual |
Builds the tree.
Implemented in GEO::AdaptiveKdTree, and GEO::BalancedKdTree.
|
inlineprotected |
Computes the minimum and maximum point coordinates along a coordinate.
[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 |
|
overridevirtual |
Finds the nearest neighbors of a point given by coordinates.
[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.
|
overridevirtual |
Finds the nearest neighbors of a point given by coordinates.
[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.
|
overridevirtual |
Finds the nearest neighbors of a point given by coordinates.
[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.
|
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.
[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 |
|
virtual |
The recursive function to implement KdTree traversal and nearest neighbors computation.
Traverses the subtree under the node_index node that corresponds to the [b,e) point sequence. Nearest neighbors are inserted into neighbors during traversal.
[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 |
|
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).
[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.
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.
This functions needs to be called before get_nearest_neighbors_recursive()
[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. |
|
inline |
|
overridevirtual |
Sets the points and create the search data structure.
[in] | nb_points | number of points |
[in] | points | an array of nb_points * dimension() |
Reimplemented from GEO::NearestNeighborSearch.
|
overridevirtual |
Sets the points and create the search data structure.
[in] | nb_points | number of points |
[in] | points | an array of nb_points * dimension() |
Reimplemented from GEO::NearestNeighborSearch.
|
inlineprotected |
Computes the extent of a point sequence along a given coordinate.
[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 |
|
overridevirtual |
Tests whether the stride variant of set_points() is supported.
Reimplemented from GEO::NearestNeighborSearch.