Loading...
Searching...
No Matches
kdtree.h
Go to the documentation of this file.
/*!
* \file kdtree.h
*
* \brief Dynamic balanced k-d tree implementation
*
* k-d tree is a multidimensional (k-dimensional) binary search tree for
* nearest neighbor search and is part of \ref btree2.
*
* Copyright and license:
*
* (C) 2014 by the GRASS Development Team
*
* This program is free software under the GNU General Public License
* (>=v2). Read the file COPYING that comes with GRASS for details.
*
* \author Markus Metz
*
* \par References
* Bentley, J. L. (1975). "Multidimensional binary search trees used for
* associative searching". Communications of the ACM 18 (9): 509.
* doi:10.1145/361002.361007
*
* \par Features
* - This k-d tree is a dynamic tree:
* elements can be inserted and removed any time.
* - This k-d tree is balanced:
* subtrees have a similar depth (the difference in subtrees' depths is
* not allowed to be larger than the balancing tolerance).
*
* Here is a structure of basic usage:
*
* Create a new k-d tree:
*
* kdtree_create(...);
*
* Insert points into the tree:
*
* kdtree_insert(...);
*
* Optionally optimize the tree:
*
* kdtree_optimize(...);
*
* Search k nearest neighbors:
*
* kdtree_knn(...);
*
* Search all neighbors in radius:
*
* kdtree_dnn(...);
*
* Destroy the tree:
*
* kdtree_destroy(...);
*
* \todo
* Doxygen ignores comment for last parameter after `);`.
* The parameter description now goes to the end of function description.
*
* \todo
* Include formatting to function descriptions.
*/
/*!
* \brief Node for k-d tree
*/
struct kdnode {
unsigned char dim; /*!< split dimension of this node */
unsigned char depth; /*!< depth at this node */
unsigned char balance; /*!< flag to indicate if balancing is needed */
double *c; /*!< coordinates */
int uid; /*!< unique id of this node */
struct kdnode
*child[2]; /*!< link to children: `[0]` for smaller, `[1]` for larger */
};
/*!
* \brief k-d tree
*/
struct kdtree {
unsigned char ndims; /*!< number of dimensions */
unsigned char *nextdim; /*!< split dimension of child nodes */
int csize; /*!< size of coordinates in bytes */
int btol; /*!< balancing tolerance */
size_t count; /*!< number of items in the tree */
struct kdnode *root; /*!< tree root */
};
/*!
* \brief k-d tree traversal
*/
struct kdtrav {
struct kdtree *tree; /*!< tree being traversed */
struct kdnode *curr_node; /*!< current node */
struct kdnode *up[256]; /*!< stack of parent nodes */
int top; /*!< index for stack */
int first; /*!< little helper flag */
};
/*! creae a new k-d tree */
struct kdtree *kdtree_create(char ndims, /*!< number of dimensions */
int *btol /*!< optional balancing tolerance */
);
/*! destroy a tree */
void kdtree_destroy(struct kdtree *t);
/*! clear a tree, removing all entries */
void kdtree_clear(struct kdtree *t);
/*! insert an item (coordinates c and uid) into the k-d tree */
int kdtree_insert(struct kdtree *t, /*!< k-d tree */
double *c, /*!< coordinates */
int uid, /*!< the point's unique id */
int dc /*!< allow duplicate coordinates */
);
/*! remove an item from the k-d tree
* coordinates c and uid must match */
int kdtree_remove(struct kdtree *t, /*!< k-d tree */
double *c, /*!< coordinates */
int uid /*!< the point's unique id */
);
/*! find k nearest neighbors
* results are stored in uid (uids) and d (squared distances)
* optionally an uid to be skipped can be given
* useful when searching for the nearest neighbors of an item
* that is also in the tree */
int kdtree_knn(struct kdtree *t, /*!< k-d tree */
double *c, /*!< coordinates */
int *uid, /*!< unique ids of the neighbors */
double *d, /*!< squared distances to the neighbors */
int k, /*!< number of neighbors to find */
int *skip /*!< unique id to skip */
);
/*! find all nearest neighbors within distance aka radius search
* results are stored in puid (uids) and pd (squared distances)
* memory is allocated as needed, the calling fn must free the memory
* optionally an uid to be skipped can be given */
int kdtree_dnn(
struct kdtree *t, /*!< k-d tree */
double *c, /*!< coordinates */
int **puid, /*!< unique ids of the neighbors */
double **pd, /*!< squared distances to the neighbors */
double maxdist, /*!< radius to search around the given coordinates */
int *skip /*!< unique id to skip */
);
/*! find all nearest neighbors within range aka box search
* the range is specified with min and max for each dimension as
* (min1, min2, ..., minn, max1, max2, ..., maxn)
* results are stored in puid (uids) and pd (squared distances)
* memory is allocated as needed, the calling fn must free the memory
* optionally an uid to be skipped can be given */
int kdtree_rnn(struct kdtree *t, /*!< k-d tree */
double *c, /*!< coordinates for range */
int **puid, /*!< unique ids of the neighbors */
int *skip /*!< unique id to skip */
);
/*! k-d tree optimization, only useful if the tree will be heavily used
* (more searches than items in the tree)
* level 0 = a bit, 1 = more, 2 = a lot */
void kdtree_optimize(struct kdtree *t, /*!< k-d tree */
int level /*!< optimization level */
);
/*! initialize tree traversal
* (re-)sets trav structure
* returns 0
*/
int kdtree_init_trav(struct kdtrav *trav, struct kdtree *tree);
/*! traverse the tree
* useful to get all items in the tree non-recursively
* struct kdtrav *trav needs to be initialized first
* returns 1, 0 when finished
*/
int kdtree_traverse(struct kdtrav *trav, double *c, int *uid);
t
double t
Definition driver/set_window.c:5
kdtree_optimize
void kdtree_optimize(struct kdtree *t, int level)
Definition kdtree.c:334
kdtree_rnn
int kdtree_rnn(struct kdtree *t, double *c, int **puid, int *skip)
Definition kdtree.c:751
kdtree_create
struct kdtree * kdtree_create(char ndims, int *btol)
Definition kdtree.c:111
kdtree_traverse
int kdtree_traverse(struct kdtrav *trav, double *c, int *uid)
Definition kdtree.c:862
kdtree_clear
void kdtree_clear(struct kdtree *t)
Definition kdtree.c:139
kdtree_insert
int kdtree_insert(struct kdtree *t, double *c, int uid, int dc)
Definition kdtree.c:179
kdtree_knn
int kdtree_knn(struct kdtree *t, double *c, int *uid, double *d, int k, int *skip)
Definition kdtree.c:512
kdtree_destroy
void kdtree_destroy(struct kdtree *t)
Definition kdtree.c:167
kdtree_dnn
int kdtree_dnn(struct kdtree *t, double *c, int **puid, double **pd, double maxdist, int *skip)
Definition kdtree.c:636
kdtree_init_trav
int kdtree_init_trav(struct kdtrav *trav, struct kdtree *tree)
Definition kdtree.c:847
kdtree_remove
int kdtree_remove(struct kdtree *t, double *c, int uid)
Definition kdtree.c:202
kdnode
Node for k-d tree.
Definition kdtree.h:67
kdnode::dim
unsigned char dim
Definition kdtree.h:68
kdnode::balance
unsigned char balance
Definition kdtree.h:70
kdnode::depth
unsigned char depth
Definition kdtree.h:69
kdnode::child
struct kdnode * child[2]
Definition kdtree.h:73
kdnode::uid
int uid
Definition kdtree.h:72
kdnode::c
double * c
Definition kdtree.h:71
kdtrav
k-d tree traversal
Definition kdtree.h:92
kdtrav::tree
struct kdtree * tree
Definition kdtree.h:93
kdtrav::curr_node
struct kdnode * curr_node
Definition kdtree.h:94
kdtrav::up
struct kdnode * up[256]
Definition kdtree.h:95
kdtrav::top
int top
Definition kdtree.h:96
kdtrav::first
int first
Definition kdtree.h:97
kdtree
k-d tree
Definition kdtree.h:80
kdtree::nextdim
unsigned char * nextdim
Definition kdtree.h:82
kdtree::ndims
unsigned char ndims
Definition kdtree.h:81
kdtree::btol
int btol
Definition kdtree.h:84
kdtree::count
size_t count
Definition kdtree.h:85
kdtree::csize
int csize
Definition kdtree.h:83
kdtree::root
struct kdnode * root
Definition kdtree.h:86