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);