Geogram  Version 1.9.1-rc
A programming library of geometric algorithms
GEO::KdTree::NearestNeighbors Struct Reference

The context for traversing a KdTree. More...

#include <geogram/points/kd_tree.h>

Public Member Functions

 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. More...
 
double furthest_neighbor_sq_dist () const
 Gets the squared distance to the furthest neighbor.
 
void insert (index_t neighbor, double sq_dist)
 Inserts a new neighbor. More...
 
void copy_from_user ()
 Copies the user neighbors and distances into the work zone and initializes nb_neighbors to max_nb_neighbors. More...
 
void copy_to_user ()
 Copies the found nearest neighbors from the work zone to the user neighbors and squared distance arrays. More...
 

Public Attributes

index_t nb_neighbors
 Current number of neighbors.
 
index_t nb_neighbors_max
 Maximum number of neighbors.
 
index_tneighbors
 Internal array of neighbors. More...
 
double * neighbors_sq_dist
 Internal squared distance to neigbors. More...
 
index_tuser_neighbors
 User-provided array of neighbors. More...
 
double * user_neighbors_sq_dist
 User-provided array of neighbors squared distances. More...
 
size_t nb_visited
 Number of points visited during traversal.
 

Detailed Description

The context for traversing a KdTree.

Stores a sorted sequence of (point,distance) couples.

Definition at line 108 of file kd_tree.h.

Constructor & Destructor Documentation

◆ NearestNeighbors()

GEO::KdTree::NearestNeighbors::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 
)
inline

Creates a new NearestNeighbors.

Storage is provided and managed by the caller. Initializes neighbors_sq_dist[0..nb_neigh-1] to Numeric::max_float64() and neighbors[0..nb_neigh-1] to index_t(-1).

Parameters
[in]nb_neighbors_innumber of neighbors to retrieve
[in]user_neighbors_instorage for the neighbors, allocated and managed by caller, with space for nb_neighbors_in integers
[in]user_neighbors_sq_dist_instorage for neighbors squared distance, allocated and managed by caller, with space for nb_neighbors_in doubles
[in]work_neighbors_instorage for the neighbors, allocated and managed by caller, with space for nb_neighbors_in + 1 integers
[in]work_neighbors_sq_dist_instorage for neighbors squared distance, allocated and managed by caller, with space for nb_neighbors_in + 1 doubles

Definition at line 129 of file kd_tree.h.

Member Function Documentation

◆ copy_from_user()

void GEO::KdTree::NearestNeighbors::copy_from_user ( )
inline

Copies the user neighbors and distances into the work zone and initializes nb_neighbors to max_nb_neighbors.

This function is called by nearest neighbors search when KeepInitialValues is specified, to initialize search from user-provided initial guess.

Definition at line 204 of file kd_tree.h.

◆ copy_to_user()

void GEO::KdTree::NearestNeighbors::copy_to_user ( )
inline

Copies the found nearest neighbors from the work zone to the user neighbors and squared distance arrays.

This function is called by find_nearest_neighbors() after traversal of the tree.

Definition at line 220 of file kd_tree.h.

◆ insert()

void GEO::KdTree::NearestNeighbors::insert ( index_t  neighbor,
double  sq_dist 
)
inline

Inserts a new neighbor.

Only the nb_neighbor nearest points are kept.

Parameters
[in]neighborthe index of the point
[in]sq_distthe squared distance between the point and the query point.
Precondition
sq_dist <= furthest_neighbor_sq_dist() (needs to be tested by client code before insertion).

Definition at line 173 of file kd_tree.h.

Member Data Documentation

◆ neighbors

index_t* GEO::KdTree::NearestNeighbors::neighbors

Internal array of neighbors.

size = nb_neigbors_max + 1

Definition at line 237 of file kd_tree.h.

◆ neighbors_sq_dist

double* GEO::KdTree::NearestNeighbors::neighbors_sq_dist

Internal squared distance to neigbors.

size = nb_neigbors_max + 1

Definition at line 243 of file kd_tree.h.

◆ user_neighbors

index_t* GEO::KdTree::NearestNeighbors::user_neighbors

User-provided array of neighbors.

size = nb_neighbors_max

Definition at line 249 of file kd_tree.h.

◆ user_neighbors_sq_dist

double* GEO::KdTree::NearestNeighbors::user_neighbors_sq_dist

User-provided array of neighbors squared distances.

size = nb_neighbors_max

Definition at line 256 of file kd_tree.h.


The documentation for this struct was generated from the following file: