|
| BalancedKdTree (coord_index_t dim) |
| Creates a new BalancedKdTree. More...
|
|
| 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...
|
|
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...
|
|
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...
|
|
|
| ~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...
|
|
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.
|
|
| NearestNeighborSearch (coord_index_t dimension) |
| Constructs a NearestNeighborSearch. More...
|
|
| ~NearestNeighborSearch () override |
| NearestNeighborSearch destructor.
|
|
| Counted () |
| Creates a reference counted object. More...
|
|
virtual | ~Counted () |
| Destroys a reference counted object. More...
|
|
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.