GRASS GIS 8 Programmer's Manual 8.2.1RC1(2022)-exported
kdtree.h
Go to the documentation of this file.
1/*!
2 * \file kdtree.h
3 *
4 * \brief Dynamic balanced k-d tree implementation
5 *
6 * k-d tree is a multidimensional (k-dimensional) binary search tree for
7 * nearest neighbor search and is part of \ref btree2.
8 *
9 * Copyright and license:
10 *
11 * (C) 2014 by the GRASS Development Team
12 *
13 * This program is free software under the GNU General Public License
14 * (>=v2). Read the file COPYING that comes with GRASS for details.
15 *
16 * \author Markus Metz
17 *
18 * \par References
19 * Bentley, J. L. (1975). "Multidimensional binary search trees used for
20 * associative searching". Communications of the ACM 18 (9): 509.
21 * doi:10.1145/361002.361007
22 *
23 * \par Features
24 * - This k-d tree is a dynamic tree:
25 * elements can be inserted and removed any time.
26 * - This k-d tree is balanced:
27 * subtrees have a similar depth (the difference in subtrees' depths is
28 * not allowed to be larger than the balancing tolerance).
29 *
30 * Here is a structure of basic usage:
31 *
32 * Create a new k-d tree:
33 *
34 * kdtree_create(...);
35 *
36 * Insert points into the tree:
37 *
38 * kdtree_insert(...);
39 *
40 * Optionally optimize the tree:
41 *
42 * kdtree_optimize(...);
43 *
44 * Search k nearest neighbors:
45 *
46 * kdtree_knn(...);
47 *
48 * Search all neighbors in radius:
49 *
50 * kdtree_dnn(...);
51 *
52 * Destroy the tree:
53 *
54 * kdtree_destroy(...);
55 *
56 * \todo
57 * Doxygen ignores comment for last parameter after `);`.
58 * The parameter description now goes to the end of function description.
59 *
60 * \todo
61 * Include formatting to function descriptions.
62 */
63
64/*!
65 * \brief Node for k-d tree
66 */
67struct kdnode
68{
69 unsigned char dim; /*!< split dimension of this node */
70 unsigned char depth; /*!< depth at this node */
71 unsigned char balance; /*!< flag to indicate if balancing is needed */
72 double *c; /*!< coordinates */
73 int uid; /*!< unique id of this node */
74 struct kdnode *child[2]; /*!< link to children: `[0]` for smaller, `[1]` for larger */
75};
76
77/*!
78 * \brief k-d tree
79 */
80struct kdtree
81{
82 unsigned char ndims; /*!< number of dimensions */
83 unsigned char *nextdim; /*!< split dimension of child nodes */
84 int csize; /*!< size of coordinates in bytes */
85 int btol; /*!< balancing tolerance */
86 size_t count; /*!< number of items in the tree */
87 struct kdnode *root; /*!< tree root */
88};
89
90/*!
91 * \brief k-d tree traversal
92 */
93struct kdtrav
94{
95 struct kdtree *tree; /*!< tree being traversed */
96 struct kdnode *curr_node; /*!< current node */
97 struct kdnode *up[256]; /*!< stack of parent nodes */
98 int top; /*!< index for stack */
99 int first; /*!< little helper flag */
100};
101
102/*! creae a new k-d tree */
103struct kdtree *kdtree_create(char ndims, /*!< number of dimensions */
104 int *btol /*!< optional balancing tolerance */
105 );
106
107/*! destroy a tree */
108void kdtree_destroy(struct kdtree *t);
109
110/*! clear a tree, removing all entries */
111void kdtree_clear(struct kdtree *t);
112
113/*! insert an item (coordinates c and uid) into the k-d tree */
114int kdtree_insert(struct kdtree *t, /*!< k-d tree */
115 double *c, /*!< coordinates */
116 int uid, /*!< the point's unique id */
117 int dc /*!< allow duplicate coordinates */
118 );
119
120/*! remove an item from the k-d tree
121 * coordinates c and uid must match */
122int kdtree_remove(struct kdtree *t, /*!< k-d tree */
123 double *c, /*!< coordinates */
124 int uid /*!< the point's unique id */
125 );
126
127/*! find k nearest neighbors
128 * results are stored in uid (uids) and d (squared distances)
129 * optionally an uid to be skipped can be given
130 * useful when searching for the nearest neighbors of an item
131 * that is also in the tree */
132int kdtree_knn(struct kdtree *t, /*!< k-d tree */
133 double *c, /*!< coordinates */
134 int *uid, /*!< unique ids of the neighbors */
135 double *d, /*!< squared distances to the neighbors */
136 int k, /*!< number of neighbors to find */
137 int *skip /*!< unique id to skip */
138 );
139
140/*! find all nearest neighbors within distance aka radius search
141 * results are stored in puid (uids) and pd (squared distances)
142 * memory is allocated as needed, the calling fn must free the memory
143 * optionally an uid to be skipped can be given */
144int kdtree_dnn(struct kdtree *t, /*!< k-d tree */
145 double *c, /*!< coordinates */
146 int **puid, /*!< unique ids of the neighbors */
147 double **pd, /*!< squared distances to the neighbors */
148 double maxdist, /*!< radius to search around the given coordinates */
149 int *skip /*!< unique id to skip */
150 );
151
152/*! find all nearest neighbors within range aka box search
153 * the range is specified with min and max for each dimension as
154 * (min1, min2, ..., minn, max1, max2, ..., maxn)
155 * results are stored in puid (uids) and pd (squared distances)
156 * memory is allocated as needed, the calling fn must free the memory
157 * optionally an uid to be skipped can be given */
158int kdtree_rnn(struct kdtree *t, /*!< k-d tree */
159 double *c, /*!< coordinates for range */
160 int **puid, /*!< unique ids of the neighbors */
161 int *skip /*!< unique id to skip */
162 );
163
164/*! k-d tree optimization, only useful if the tree will be heavily used
165 * (more searches than items in the tree)
166 * level 0 = a bit, 1 = more, 2 = a lot */
167void kdtree_optimize(struct kdtree *t, /*!< k-d tree */
168 int level /*!< optimization level */
169 );
170
171/*! initialize tree traversal
172 * (re-)sets trav structure
173 * returns 0
174 */
175int kdtree_init_trav(struct kdtrav *trav, struct kdtree *tree);
176
177/*! traverse the tree
178 * useful to get all items in the tree non-recursively
179 * struct kdtrav *trav needs to be initialized first
180 * returns 1, 0 when finished
181 */
182int kdtree_traverse(struct kdtrav *trav, double *c, int *uid);
double t
void kdtree_optimize(struct kdtree *t, int level)
Definition: kdtree.c:331
int kdtree_rnn(struct kdtree *t, double *c, int **puid, int *skip)
Definition: kdtree.c:739
struct kdtree * kdtree_create(char ndims, int *btol)
Definition: kdtree.c:110
int kdtree_traverse(struct kdtrav *trav, double *c, int *uid)
Definition: kdtree.c:850
void kdtree_clear(struct kdtree *t)
Definition: kdtree.c:138
int kdtree_insert(struct kdtree *t, double *c, int uid, int dc)
Definition: kdtree.c:178
int kdtree_knn(struct kdtree *t, double *c, int *uid, double *d, int k, int *skip)
Definition: kdtree.c:501
void kdtree_destroy(struct kdtree *t)
Definition: kdtree.c:166
int kdtree_dnn(struct kdtree *t, double *c, int **puid, double **pd, double maxdist, int *skip)
Definition: kdtree.c:624
int kdtree_init_trav(struct kdtrav *trav, struct kdtree *tree)
Definition: kdtree.c:835
int kdtree_remove(struct kdtree *t, double *c, int uid)
Definition: kdtree.c:201
Node for k-d tree.
Definition: kdtree.h:68
unsigned char dim
Definition: kdtree.h:69
unsigned char balance
Definition: kdtree.h:71
unsigned char depth
Definition: kdtree.h:70
struct kdnode * child[2]
Definition: kdtree.h:74
int uid
Definition: kdtree.h:73
double * c
Definition: kdtree.h:72
k-d tree traversal
Definition: kdtree.h:94
struct kdtree * tree
Definition: kdtree.h:95
struct kdnode * curr_node
Definition: kdtree.h:96
struct kdnode * up[256]
Definition: kdtree.h:97
int top
Definition: kdtree.h:98
int first
Definition: kdtree.h:99
k-d tree
Definition: kdtree.h:81
unsigned char * nextdim
Definition: kdtree.h:83
unsigned char ndims
Definition: kdtree.h:82
int btol
Definition: kdtree.h:85
size_t count
Definition: kdtree.h:86
int csize
Definition: kdtree.h:84
struct kdnode * root
Definition: kdtree.h:87