GEO::AdaptiveKdTree Class Reference
Implements NearestNeighborSearch using an Adaptive Kd-tree. More...
#include <geogram/points/kd_tree.h>
Inheritance diagram for GEO::AdaptiveKdTree:
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_t > | splitting_coord_ |
| One per node, splitting coordinate. | |
| vector< double > | splitting_val_ |
| One per node, splitting coordinate value. | |
| vector< index_t > | node_m_ |
| One per node, node splitting index. More... | |
| vector< index_t > | node_right_child_ |
| One per node, right child index. More... | |
| Protected Attributes inherited from GEO::KdTree | |
| 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_ |
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... | |
| 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. | |
| 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... | |
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.
Constructor & Destructor Documentation
◆ AdaptiveKdTree()
| GEO::AdaptiveKdTree::AdaptiveKdTree | ( | coord_index_t | dim | ) |
Creates a new BalancedKdTree.
- Parameters
-
[in] dim dimension of the points
Member Function Documentation
◆ build_tree()
|
overrideprotectedvirtual |
◆ create_kd_tree_recursive()
|
protectedvirtual |
Creates the subtree under a node.
- Parameters
-
[in] b first index of the point sequence in the subtree [in] e one position past the last index of the point index in the subtree [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.
- Returns
- the node index of the root of the created tree.
◆ get_node()
|
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] 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 nis split.[out] m the point m such that [b,m-1] corresponds to the points in the left child of nand [m,e-1] corresponds to the points in the right child ofn.[out] splitting_val The coordinate value that separates points in the left and right children.
Implements GEO::KdTree.
◆ nb_nodes()
|
inlineprotected |
◆ new_node()
|
protectedvirtual |
Creates a new node.
- Returns
- the index of the newly created node.
◆ plane_split()
|
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] 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 [in] val the cutting value [out] br1,br2 on 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()
|
inlineprotected |
Gets a point coordinate by index and coordinate.
- Parameters
-
[in] index index of the point. [in] coord coordinate, in 0..dimension()-1
- Returns
- the coordinate of the point, after re-numerotation.
◆ split_kd_node()
|
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_min coordinates of the lower corner of the bounding box. Allocated and managed by caller. Modified by the function and restored on exit. [out] m the point index. [out] cut_dim the coordinate along which the node is split. [out] cut_val the splitting value.
Member Data Documentation
◆ node_m_
◆ node_right_child_
The documentation for this class was generated from the following file:
- geogram/points/kd_tree.h
