40 #ifndef GEOGRAM_POINTS_KD_TREE
41 #define GEOGRAM_POINTS_KD_TREE
79 const double* query_point,
81 double* neighbors_sq_dist
87 const double* query_point,
89 double* neighbors_sq_dist,
98 double* neighbors_sq_dist
132 double* user_neighbors_sq_dist_in,
134 double* work_neighbors_sq_dist_in
137 nb_neighbors_max(nb_neighbors_in),
138 neighbors(work_neighbors_in),
139 neighbors_sq_dist(work_neighbors_sq_dist_in),
140 user_neighbors(user_neighbors_in),
141 user_neighbors_sq_dist(user_neighbors_sq_dist_in),
146 for(
index_t i = 0; i <= nb_neighbors; ++i) {
158 nb_neighbors == nb_neighbors_max ?
159 neighbors_sq_dist[nb_neighbors - 1] :
174 index_t neighbor,
double sq_dist
177 sq_dist <= furthest_neighbor_sq_dist()
181 for(i=
int(nb_neighbors); i>0; --i) {
182 if(neighbors_sq_dist[i - 1] < sq_dist) {
185 neighbors[i] = neighbors[i - 1];
186 neighbors_sq_dist[i] = neighbors_sq_dist[i - 1];
189 neighbors[i] = neighbor;
190 neighbors_sq_dist[i] = sq_dist;
192 if(nb_neighbors < nb_neighbors_max) {
205 for(
index_t i=0; i<nb_neighbors_max; ++i) {
206 neighbors[i] = user_neighbors[i];
207 neighbors_sq_dist[i] = user_neighbors_sq_dist[i];
209 neighbors[nb_neighbors_max] =
index_t(-1);
211 nb_neighbors = nb_neighbors_max;
221 for(
index_t i=0; i<nb_neighbors_max; ++i) {
222 user_neighbors[i] = neighbors[i];
223 user_neighbors_sq_dist[i] = neighbors_sq_dist[i];
297 double* bbox_min,
double* bbox_max,
298 double bbox_dist,
const double* query_point,
318 double* bbox_min,
double* bbox_max,
319 double& box_dist,
const double* query_point
366 double& splitting_val
386 const double* query_point,
400 double& minval,
double& maxval
404 for(
index_t i = b; i < e; ++i) {
405 double val = point_ptr(point_index_[i])[coord];
406 minval = std::min(minval, val);
407 maxval = std::max(maxval, val);
420 double minval,maxval;
421 get_minmax(b,e,coord,minval,maxval);
422 return maxval - minval;
471 if(e - b <= MAX_LEAF_SIZE) {
476 max_node_index(2 * node_id, b, m),
477 max_node_index(2 * node_id + 1, m, e)
500 if(e - b <= MAX_LEAF_SIZE) {
503 index_t m = split_kd_node(node_index, b, e);
504 create_kd_tree_recursive(2 * node_index, b, m);
505 create_kd_tree_recursive(2 * node_index + 1, m, e);
531 double& splitting_val
588 double& splitting_val
604 double* bbox_min,
double* bbox_max
624 double* bbox_min,
double* bbox_max,
659 return (points_ + direct_index * stride_)[coord];
668 return splitting_coord_.size();
#define geo_debug_assert(x)
Verifies that a condition is met.
Implements NearestNeighborSearch using an Adaptive Kd-tree.
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,...
vector< index_t > node_m_
One per node, node splitting index.
double point_coord(int index, coord_index_t coord)
Gets a point coordinate by index and coordinate.
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.
index_t build_tree() override
Builds the tree.
vector< double > splitting_val_
One per node, splitting coordinate value.
virtual index_t new_node()
Creates a new node.
vector< index_t > node_right_child_
One per node, right child index.
AdaptiveKdTree(coord_index_t dim)
Creates a new BalancedKdTree.
vector< coord_index_t > splitting_coord_
One per node, splitting coordinate.
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...
index_t nb_nodes() const
Gets the number of nodes.
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.
Implements NearestNeighborSearch using a balanced Kd-tree.
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.
void create_kd_tree_recursive(index_t node_index, index_t b, index_t e)
Creates the subtree under a node.
BalancedKdTree(coord_index_t dim)
Creates a new BalancedKdTree.
vector< coord_index_t > splitting_coord_
One per node, splitting coordinate.
~BalancedKdTree() override
BalancedKdTree destructor.
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,...
coord_index_t best_splitting_coord(index_t b, index_t e)
Computes the coordinate along which a point sequence will be split.
index_t build_tree() override
Builds the tree.
vector< double > splitting_val_
One per node, splitting coordinate value.
index_t m0_
Indices for multithreaded tree construction.
static index_t max_node_index(index_t node_id, index_t b, index_t e)
Returns the maximum node index in subtree.
Base class for all Kd-tree implementations.
index_t root() const
Gets the root node.
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.
bool stride_supported() const override
Tests whether the stride variant of set_points() is supported.
virtual index_t build_tree()=0
Builds the tree.
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.
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.
void set_points(index_t nb_points, const double *points, index_t stride) override
Sets the points and create the search data structure.
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.
KdTree(coord_index_t dim)
KdTree constructor.
void set_points(index_t nb_points, const double *points) override
Sets the points and create the search data structure.
double spread(index_t b, index_t e, coord_index_t coord) const
Computes the extent of a point sequence along a given coordinate.
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.
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.
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.
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.
~KdTree() override
KdTree destructor.
Abstract interface for nearest neighbor search algorithms.
Common include file, providing basic definitions. Should be included before anything else by all head...
float64 max_float64()
Gets 64 bits float maximum positive value.
float64 min_float64()
Gets 64 bits float minimum negative value.
Global Vorpaline namespace.
geo_index_t index_t
The type for storing and manipulating indices.
geo_coord_index_t coord_index_t
The type for storing coordinate indices, and iterating on the coordinates of a point.
Abstract interface for nearest neighbor searching.
The context for traversing a KdTree.
void copy_from_user()
Copies the user neighbors and distances into the work zone and initializes nb_neighbors to max_nb_nei...
double furthest_neighbor_sq_dist() const
Gets the squared distance to the furthest neighbor.
index_t nb_neighbors
Current number of neighbors.
index_t * neighbors
Internal array of neighbors.
index_t nb_neighbors_max
Maximum number of neighbors.
double * user_neighbors_sq_dist
User-provided array of neighbors squared distances.
void insert(index_t neighbor, double sq_dist)
Inserts a new neighbor.
size_t nb_visited
Number of points visited during traversal.
double * neighbors_sq_dist
Internal squared distance to neigbors.
index_t * user_neighbors
User-provided array of neighbors.
NearestNeighbors(index_t nb_neighbors_in, index_t *user_neighbors_in, double *user_neighbors_sq_dist_in, index_t *work_neighbors_in, double *work_neighbors_sq_dist_in)
Creates a new NearestNeighbors.
void copy_to_user()
Copies the found nearest neighbors from the work zone to the user neighbors and squared distance arra...
A structure to discriminate between the two versions of get_nearest_neighbors()