GRASS GIS 7 Programmer's Manual  7.5.svn(2018)-r72114
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
kdtree.h File Reference

Dynamic balanced k-d tree implementation. More...

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  kdnode
 Node for k-d tree. More...
 
struct  kdtree
 k-d tree More...
 
struct  kdtrav
 k-d tree traversal More...
 

Functions

struct kdtreekdtree_create (char ndims, int *btol)
 
void kdtree_destroy (struct kdtree *t)
 
void kdtree_clear (struct kdtree *t)
 
int kdtree_insert (struct kdtree *t, double *c, int uid, int dc)
 
int kdtree_remove (struct kdtree *t, double *c, int uid)
 
int kdtree_knn (struct kdtree *t, double *c, int *uid, double *d, int k, int *skip)
 
int kdtree_dnn (struct kdtree *t, double *c, int **puid, double **pd, double maxdist, int *skip)
 
int kdtree_rnn (struct kdtree *t, double *c, int **puid, int *skip)
 
void kdtree_optimize (struct kdtree *t, int level)
 
int kdtree_init_trav (struct kdtrav *trav, struct kdtree *tree)
 
int kdtree_traverse (struct kdtrav *trav, double *c, int *uid)
 

Detailed Description

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 btree2 library.

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

Definition in file kdtree.h.

Function Documentation

void kdtree_clear ( struct kdtree t)

clear a tree, removing all entries

Definition at line 143 of file kdtree.c.

References kdnode::child, NULL, and kdtree::root.

Referenced by kdtree_destroy().

struct kdtree* kdtree_create ( char  ndims,
int btol 
)

creae a new k-d tree

Parameters
ndimsnumber of dimensions
btoloptional balancing tolerance

Definition at line 115 of file kdtree.c.

References kdtree::btol, kdtree::count, kdtree::csize, KD_BTOL, kdtree::ndims, kdtree::nextdim, NULL, kdtree::root, and t.

void kdtree_destroy ( struct kdtree t)

destroy a tree

Definition at line 171 of file kdtree.c.

References G_free(), kdtree_clear(), kdtree::nextdim, and NULL.

int kdtree_dnn ( struct kdtree t,
double *  c,
int **  puid,
double **  pd,
double  maxdist,
int 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

Parameters
tk-d tree
ccoordinates
puidunique ids of the neighbors
pdsquared distances to the neighbors
maxdistradius to search around the given coordinates
skipunique id to skip

Definition at line 629 of file kdtree.c.

References kdnode::c, kdnode::dim, G_fatal_error(), int, kdtree::ndims, NULL, kdtree::root, and kdnode::uid.

int kdtree_init_trav ( struct kdtrav trav,
struct kdtree tree 
)

initialize tree traversal (re-)sets trav structure returns 0

Definition at line 840 of file kdtree.c.

References kdtrav::curr_node, kdtrav::first, kdtree::root, kdtrav::top, and kdtrav::tree.

int kdtree_insert ( struct kdtree t,
double *  c,
int  uid,
int  dc 
)

insert an item (coordinates c and uid) into the k-d tree

Parameters
tk-d tree
ccoordinates
uidthe point's unique id
dcallow duplicate coordinates

Definition at line 183 of file kdtree.c.

References kdnode::c, count, kdtree::count, kdtree::csize, kdtree::root, and kdnode::uid.

int kdtree_knn ( struct kdtree t,
double *  c,
int uid,
double *  d,
int  k,
int skip 
)

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

Parameters
tk-d tree
ccoordinates
uidunique ids of the neighbors
dsquared distances to the neighbors
knumber of neighbors to find
skipunique id to skip

Definition at line 506 of file kdtree.c.

References kdnode::c, kdnode::dim, G_fatal_error(), int, kdtree::ndims, kdtree::root, and kdnode::uid.

void kdtree_optimize ( struct kdtree t,
int  level 
)

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

Parameters
tk-d tree
leveloptimization level

Definition at line 336 of file kdtree.c.

References kdnode::child, kdtree::count, kdnode::depth, G_debug(), MAX, and kdtree::root.

int kdtree_remove ( struct kdtree t,
double *  c,
int  uid 
)

remove an item from the k-d tree coordinates c and uid must match

Parameters
tk-d tree
ccoordinates
uidthe point's unique id

Definition at line 206 of file kdtree.c.

References kdnode::balance, kdnode::c, kdnode::child, kdnode::depth, kdnode::dim, G_warning(), NULL, r, kdtree::root, and kdnode::uid.

int kdtree_rnn ( struct kdtree t,
double *  c,
int **  puid,
int 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

Parameters
tk-d tree
ccoordinates for range
puidunique ids of the neighbors
skipunique id to skip

Definition at line 744 of file kdtree.c.

References kdnode::c, kdnode::dim, int, kdtree::ndims, NULL, kdtree::root, and kdnode::uid.

int kdtree_traverse ( struct kdtrav trav,
double *  c,
int uid 
)

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

Definition at line 855 of file kdtree.c.

References kdtrav::curr_node, kdtrav::first, G_debug(), and NULL.