GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-535c39c9fc
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  unsigned char dim; /*!< split dimension of this node */
69  unsigned char depth; /*!< depth at this node */
70  unsigned char balance; /*!< flag to indicate if balancing is needed */
71  double *c; /*!< coordinates */
72  int uid; /*!< unique id of this node */
73  struct kdnode
74  *child[2]; /*!< link to children: `[0]` for smaller, `[1]` for larger */
75 };
76 
77 /*!
78  * \brief k-d tree
79  */
80 struct kdtree {
81  unsigned char ndims; /*!< number of dimensions */
82  unsigned char *nextdim; /*!< split dimension of child nodes */
83  int csize; /*!< size of coordinates in bytes */
84  int btol; /*!< balancing tolerance */
85  size_t count; /*!< number of items in the tree */
86  struct kdnode *root; /*!< tree root */
87 };
88 
89 /*!
90  * \brief k-d tree traversal
91  */
92 struct kdtrav {
93  struct kdtree *tree; /*!< tree being traversed */
94  struct kdnode *curr_node; /*!< current node */
95  struct kdnode *up[256]; /*!< stack of parent nodes */
96  int top; /*!< index for stack */
97  int first; /*!< little helper flag */
98 };
99 
100 /*! creae a new k-d tree */
101 struct kdtree *kdtree_create(char ndims, /*!< number of dimensions */
102  int *btol /*!< optional balancing tolerance */
103 );
104 
105 /*! destroy a tree */
106 void kdtree_destroy(struct kdtree *t);
107 
108 /*! clear a tree, removing all entries */
109 void kdtree_clear(struct kdtree *t);
110 
111 /*! insert an item (coordinates c and uid) into the k-d tree */
112 int kdtree_insert(struct kdtree *t, /*!< k-d tree */
113  double *c, /*!< coordinates */
114  int uid, /*!< the point's unique id */
115  int dc /*!< allow duplicate coordinates */
116 );
117 
118 /*! remove an item from the k-d tree
119  * coordinates c and uid must match */
120 int kdtree_remove(struct kdtree *t, /*!< k-d tree */
121  double *c, /*!< coordinates */
122  int uid /*!< the point's unique id */
123 );
124 
125 /*! find k nearest neighbors
126  * results are stored in uid (uids) and d (squared distances)
127  * optionally an uid to be skipped can be given
128  * useful when searching for the nearest neighbors of an item
129  * that is also in the tree */
130 int kdtree_knn(struct kdtree *t, /*!< k-d tree */
131  double *c, /*!< coordinates */
132  int *uid, /*!< unique ids of the neighbors */
133  double *d, /*!< squared distances to the neighbors */
134  int k, /*!< number of neighbors to find */
135  int *skip /*!< unique id to skip */
136 );
137 
138 /*! find all nearest neighbors within distance aka radius search
139  * results are stored in puid (uids) and pd (squared distances)
140  * memory is allocated as needed, the calling fn must free the memory
141  * optionally an uid to be skipped can be given */
142 int kdtree_dnn(
143  struct kdtree *t, /*!< k-d tree */
144  double *c, /*!< coordinates */
145  int **puid, /*!< unique ids of the neighbors */
146  double **pd, /*!< squared distances to the neighbors */
147  double maxdist, /*!< radius to search around the given coordinates */
148  int *skip /*!< unique id to skip */
149 );
150 
151 /*! find all nearest neighbors within range aka box search
152  * the range is specified with min and max for each dimension as
153  * (min1, min2, ..., minn, max1, max2, ..., maxn)
154  * results are stored in puid (uids) and pd (squared distances)
155  * memory is allocated as needed, the calling fn must free the memory
156  * optionally an uid to be skipped can be given */
157 int kdtree_rnn(struct kdtree *t, /*!< k-d tree */
158  double *c, /*!< coordinates for range */
159  int **puid, /*!< unique ids of the neighbors */
160  int *skip /*!< unique id to skip */
161 );
162 
163 /*! k-d tree optimization, only useful if the tree will be heavily used
164  * (more searches than items in the tree)
165  * level 0 = a bit, 1 = more, 2 = a lot */
166 void kdtree_optimize(struct kdtree *t, /*!< k-d tree */
167  int level /*!< optimization level */
168 );
169 
170 /*! initialize tree traversal
171  * (re-)sets trav structure
172  * returns 0
173  */
174 int kdtree_init_trav(struct kdtrav *trav, struct kdtree *tree);
175 
176 /*! traverse the tree
177  * useful to get all items in the tree non-recursively
178  * struct kdtrav *trav needs to be initialized first
179  * returns 1, 0 when finished
180  */
181 int kdtree_traverse(struct kdtrav *trav, double *c, int *uid);
void kdtree_optimize(struct kdtree *t, int level)
Definition: kdtree.c:334
int kdtree_rnn(struct kdtree *t, double *c, int **puid, int *skip)
Definition: kdtree.c:751
struct kdtree * kdtree_create(char ndims, int *btol)
Definition: kdtree.c:111
int kdtree_traverse(struct kdtrav *trav, double *c, int *uid)
Definition: kdtree.c:862
void kdtree_clear(struct kdtree *t)
Definition: kdtree.c:139
int kdtree_insert(struct kdtree *t, double *c, int uid, int dc)
Definition: kdtree.c:179
int kdtree_knn(struct kdtree *t, double *c, int *uid, double *d, int k, int *skip)
Definition: kdtree.c:512
void kdtree_destroy(struct kdtree *t)
Definition: kdtree.c:167
int kdtree_dnn(struct kdtree *t, double *c, int **puid, double **pd, double maxdist, int *skip)
Definition: kdtree.c:636
int kdtree_init_trav(struct kdtrav *trav, struct kdtree *tree)
Definition: kdtree.c:847
int kdtree_remove(struct kdtree *t, double *c, int uid)
Definition: kdtree.c:202
double t
Definition: r_raster.c:39
Node for k-d tree.
Definition: kdtree.h:67
unsigned char dim
Definition: kdtree.h:68
unsigned char balance
Definition: kdtree.h:70
unsigned char depth
Definition: kdtree.h:69
struct kdnode * child[2]
Definition: kdtree.h:73
int uid
Definition: kdtree.h:72
double * c
Definition: kdtree.h:71
k-d tree traversal
Definition: kdtree.h:92
struct kdtree * tree
Definition: kdtree.h:93
struct kdnode * curr_node
Definition: kdtree.h:94
struct kdnode * up[256]
Definition: kdtree.h:95
int top
Definition: kdtree.h:96
int first
Definition: kdtree.h:97
k-d tree
Definition: kdtree.h:80
unsigned char * nextdim
Definition: kdtree.h:82
unsigned char ndims
Definition: kdtree.h:81
int btol
Definition: kdtree.h:84
size_t count
Definition: kdtree.h:85
int csize
Definition: kdtree.h:83
struct kdnode * root
Definition: kdtree.h:86