GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
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  */
67 struct 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  */
80 struct 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  */
93 struct 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 */
103 struct kdtree *kdtree_create(char ndims, /*!< number of dimensions */
104  int *btol /*!< optional balancing tolerance */
105  );
106 
107 /*! destroy a tree */
108 void kdtree_destroy(struct kdtree *t);
109 
110 /*! clear a tree, removing all entries */
111 void kdtree_clear(struct kdtree *t);
112 
113 /*! insert an item (coordinates c and uid) into the k-d tree */
114 int 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 */
122 int 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 */
132 int 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 */
144 int 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 */
158 int 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 */
167 void 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  */
175 int 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  */
182 int kdtree_traverse(struct kdtrav *trav, double *c, int *uid);
int kdtree_knn(struct kdtree *t, double *c, int *uid, double *d, int k, int *skip)
Definition: kdtree.c:501
int kdtree_insert(struct kdtree *t, double *c, int uid, int dc)
Definition: kdtree.c:178
int csize
Definition: kdtree.h:84
unsigned char dim
Definition: kdtree.h:69
Node for k-d tree.
Definition: kdtree.h:67
void kdtree_optimize(struct kdtree *t, int level)
Definition: kdtree.c:331
double * c
Definition: kdtree.h:72
size_t count
Definition: kdtree.h:86
int btol
Definition: kdtree.h:85
int kdtree_traverse(struct kdtrav *trav, double *c, int *uid)
Definition: kdtree.c:850
unsigned char depth
Definition: kdtree.h:70
unsigned char balance
Definition: kdtree.h:71
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
void kdtree_destroy(struct kdtree *t)
Definition: kdtree.c:166
unsigned char ndims
Definition: kdtree.h:82
struct kdtree * tree
Definition: kdtree.h:95
double t
Definition: r_raster.c:39
int kdtree_dnn(struct kdtree *t, double *c, int **puid, double **pd, double maxdist, int *skip)
Definition: kdtree.c:624
k-d tree
Definition: kdtree.h:80
int first
Definition: kdtree.h:99
unsigned char * nextdim
Definition: kdtree.h:83
struct kdnode * root
Definition: kdtree.h:87
struct kdnode * child[2]
Definition: kdtree.h:74
struct kdtree * kdtree_create(char ndims, int *btol)
Definition: kdtree.c:110
struct kdnode * curr_node
Definition: kdtree.h:96
int uid
Definition: kdtree.h:73
int kdtree_rnn(struct kdtree *t, double *c, int **puid, int *skip)
Definition: kdtree.c:739
int top
Definition: kdtree.h:98
k-d tree traversal
Definition: kdtree.h:93
void kdtree_clear(struct kdtree *t)
Definition: kdtree.c:138