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