GRASS GIS 8 Programmer's Manual 8.4.1(2025)-45ca3179ab
Loading...
Searching...
No Matches
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 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 */
80struct 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 */
92struct 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 */
101struct kdtree *kdtree_create(char ndims, /*!< number of dimensions */
102 int *btol /*!< optional balancing tolerance */
103);
104
105/*! destroy a tree */
106void kdtree_destroy(struct kdtree *t);
107
108/*! clear a tree, removing all entries */
109void kdtree_clear(struct kdtree *t);
110
111/*! insert an item (coordinates c and uid) into the k-d tree */
112int 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 */
120int 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 */
130int 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 */
142int 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 */
157int 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 */
166void 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 */
174int 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 */
181int kdtree_traverse(struct kdtrav *trav, double *c, int *uid);
double t
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
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