GRASS GIS 7 Programmer's Manual  7.2.0(2016)-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  */
67 struct kdnode
68 {
69  unsigned char dim; /*!< split dimension of this node */
70  unsigned char depth; /*!< depth at this node */
71  double *c; /*!< coordinates */
72  int uid; /*!< unique id of this node */
73  struct kdnode *child[2]; /*!< link to children: `[0]` for smaller, `[1]` for larger */
74 };
75 
76 /*!
77  * \brief k-d tree
78  */
79 struct kdtree
80 {
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 {
94  struct kdtree *tree; /*!< tree being traversed */
95  struct kdnode *curr_node; /*!< current node */
96  struct kdnode *up[256]; /*!< stack of parent nodes */
97  int top; /*!< index for stack */
98  int first; /*!< little helper flag */
99 };
100 
101 /*! creae a new k-d tree */
102 struct kdtree *kdtree_create(char ndims, /*!< number of dimensions */
103  int *btol /*!< optional balancing tolerance */
104  );
105 
106 /*! destroy a tree */
107 void kdtree_destroy(struct kdtree *t);
108 
109 /*! clear a tree, removing all entries */
110 void kdtree_clear(struct kdtree *t);
111 
112 /*! insert an item (coordinates c and uid) into the k-d tree */
113 int kdtree_insert(struct kdtree *t, /*!< k-d tree */
114  double *c, /*!< coordinates */
115  int uid, /*!< the point's unique id */
116  int dc /*!< allow duplicate coordinates */
117  );
118 
119 /*! remove an item from the k-d tree
120  * coordinates c and uid must match */
121 int kdtree_remove(struct kdtree *t, /*!< k-d tree */
122  double *c, /*!< coordinates */
123  int uid /*!< the point's unique id */
124  );
125 
126 /*! find k nearest neighbors
127  * results are stored in uid (uids) and d (squared distances)
128  * optionally an uid to be skipped can be given
129  * useful when searching for the nearest neighbors of an item
130  * that is also in the tree */
131 int kdtree_knn(struct kdtree *t, /*!< k-d tree */
132  double *c, /*!< coordinates */
133  int *uid, /*!< unique ids of the neighbors */
134  double *d, /*!< squared distances to the neighbors */
135  int k, /*!< number of neighbors to find */
136  int *skip /*!< unique id to skip */
137  );
138 
139 /*! find all nearest neighbors within distance aka radius search
140  * results are stored in puid (uids) and pd (squared distances)
141  * memory is allocated as needed, the calling fn must free the memory
142  * optionally an uid to be skipped can be given */
143 int kdtree_dnn(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);
int kdtree_knn(struct kdtree *t, double *c, int *uid, double *d, int k, int *skip)
Definition: kdtree.c:388
int kdtree_insert(struct kdtree *t, double *c, int uid, int dc)
Definition: kdtree.c:157
int csize
Definition: kdtree.h:83
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:267
double * c
Definition: kdtree.h:71
size_t count
Definition: kdtree.h:85
int btol
Definition: kdtree.h:84
int kdtree_traverse(struct kdtrav *trav, double *c, int *uid)
Definition: kdtree.c:737
unsigned char depth
Definition: kdtree.h:70
int kdtree_init_trav(struct kdtrav *trav, struct kdtree *tree)
Definition: kdtree.c:722
int kdtree_remove(struct kdtree *t, double *c, int uid)
Definition: kdtree.c:180
void kdtree_destroy(struct kdtree *t)
Definition: kdtree.c:145
unsigned char ndims
Definition: kdtree.h:81
struct kdtree * tree
Definition: kdtree.h:94
int kdtree_dnn(struct kdtree *t, double *c, int **puid, double **pd, double maxdist, int *skip)
Definition: kdtree.c:511
k-d tree
Definition: kdtree.h:79
double t
int first
Definition: kdtree.h:98
unsigned char * nextdim
Definition: kdtree.h:82
struct kdnode * root
Definition: kdtree.h:86
struct kdnode * child[2]
Definition: kdtree.h:73
struct kdtree * kdtree_create(char ndims, int *btol)
Definition: kdtree.c:88
struct kdnode * curr_node
Definition: kdtree.h:95
int uid
Definition: kdtree.h:72
int kdtree_rnn(struct kdtree *t, double *c, int **puid, int *skip)
Definition: kdtree.c:626
int top
Definition: kdtree.h:97
k-d tree traversal
Definition: kdtree.h:92
void kdtree_clear(struct kdtree *t)
Definition: kdtree.c:117