/usr/lib/grass72/include/grass/kdtree.h is in grass-dev 7.2.0-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 | /*!
* \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 */
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);
|