1 /*
2 # This file is part of libkd.
3 # Licensed under a 3-clause BSD style license - see LICENSE
4 */
5
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <assert.h>
9 #include <string.h>
10 #include <math.h>
11
12 #include "os-features.h"
13 #include "kdtree.h"
14 #include "kdtree_internal.h"
15 #include "kdtree_internal_common.h"
16 #include "kdtree_mem.h"
17 #include "keywords.h"
18 #include "an-fls.h"
19 #include "errors.h"
20 #include "log.h"
21
kdtree_build(kdtree_t * kd,void * data,int N,int D,int Nleaf,int treetype,unsigned int options)22 kdtree_t* kdtree_build(kdtree_t* kd, void *data, int N, int D, int Nleaf,
23 int treetype, unsigned int options) {
24 return kdtree_build_2(kd, data, N, D, Nleaf, treetype, options,
25 NULL, NULL);
26 }
27
kdtree_print(kdtree_t * kd)28 void kdtree_print(kdtree_t* kd) {
29 printf("kdtree:\n");
30 printf(" type 0x%x\n", kd->treetype);
31 printf(" lr %p\n", kd->lr);
32 printf(" perm %p\n", kd->perm);
33 printf(" bb %p\n", kd->bb.any);
34 printf(" nbb %i\n", kd->n_bb);
35 printf(" split %p\n", kd->split.any);
36 printf(" splitdim %p\n", kd->splitdim);
37 printf(" dimbits %i\n", kd->dimbits);
38 printf(" dimmask 0x%x\n", kd->dimmask);
39 printf(" splitmask 0x%x\n", kd->splitmask);
40 printf(" data %p\n", kd->data.any);
41 printf(" free data %i\n", (int)kd->free_data);
42 printf(" range");
43 if (kd->minval && kd->maxval) {
44 int i;
45 for (i=0; i<kd->ndim; i++)
46 printf(" [%g, %g]", kd->minval[i], kd->maxval[i]);
47 } else
48 printf(" (none)\n");
49 printf("\n");
50 printf(" scale %g\n", kd->scale);
51 printf(" invscale %g\n", kd->invscale);
52 printf(" Ndata %i\n", kd->ndata);
53 printf(" Ndim %i\n", kd->ndim);
54 printf(" Nnodes %i\n", kd->nnodes);
55 printf(" Nbottom %i\n", kd->nbottom);
56 printf(" Ninterior %i\n", kd->ninterior);
57 printf(" Nlevels %i\n", kd->nlevels);
58 printf(" has_linear_lr %i\n", (int)kd->has_linear_lr);
59 printf(" name %s\n", kd->name);
60 }
61
kdtree_n(const kdtree_t * kd)62 int kdtree_n(const kdtree_t* kd) {
63 return kd->ndata;
64 }
65
kdtree_nnodes(const kdtree_t * kd)66 int kdtree_nnodes(const kdtree_t* kd) {
67 return kd->nnodes;
68 }
69
kdtree_has_old_bb(const kdtree_t * kd)70 int kdtree_has_old_bb(const kdtree_t* kd) {
71 return kd->n_bb != kd->nnodes;
72 }
73
74 KD_DECLARE(kdtree_update_funcs, void, (kdtree_t*));
75
kdtree_update_funcs(kdtree_t * kd)76 void kdtree_update_funcs(kdtree_t* kd) {
77 KD_DISPATCH(kdtree_update_funcs, kd->treetype,, (kd));
78 }
79
get_tree_size(int treetype)80 static int get_tree_size(int treetype) {
81 switch (treetype & KDT_TREE_MASK) {
82 case KDT_TREE_DOUBLE:
83 return sizeof(double);
84 case KDT_TREE_FLOAT:
85 return sizeof(float);
86 case KDT_TREE_U32:
87 return sizeof(u32);
88 case KDT_TREE_U16:
89 return sizeof(u16);
90 }
91 return -1;
92 }
get_data_size(int treetype)93 static int get_data_size(int treetype) {
94 switch (treetype & KDT_DATA_MASK) {
95 case KDT_DATA_DOUBLE:
96 return sizeof(double);
97 case KDT_DATA_FLOAT:
98 return sizeof(float);
99 case KDT_DATA_U32:
100 return sizeof(u32);
101 case KDT_DATA_U16:
102 return sizeof(u16);
103 }
104 return -1;
105 }
106
kdtree_sizeof_lr(const kdtree_t * kd)107 size_t kdtree_sizeof_lr(const kdtree_t* kd) {
108 return sizeof(int32_t) * kd->nbottom;
109 }
110
kdtree_sizeof_perm(const kdtree_t * kd)111 size_t kdtree_sizeof_perm(const kdtree_t* kd) {
112 return sizeof(u32) * kd->ndata;
113 }
114
kdtree_sizeof_bb(const kdtree_t * kd)115 size_t kdtree_sizeof_bb(const kdtree_t* kd) {
116 return get_tree_size(kd->treetype) * kd->ndim * kd->nnodes;
117 }
118
kdtree_sizeof_split(const kdtree_t * kd)119 size_t kdtree_sizeof_split(const kdtree_t* kd) {
120 return get_tree_size(kd->treetype) * kd->ninterior;
121 }
122
kdtree_sizeof_splitdim(const kdtree_t * kd)123 size_t kdtree_sizeof_splitdim(const kdtree_t* kd) {
124 return sizeof(u8) * kd->ninterior;
125 }
126
kdtree_sizeof_data(const kdtree_t * kd)127 size_t kdtree_sizeof_data(const kdtree_t* kd) {
128 return get_data_size(kd->treetype) * kd->ndim * kd->ndata;
129 }
130
kdtree_memory_report(kdtree_t * kd)131 void kdtree_memory_report(kdtree_t* kd) {
132 int mem;
133 int n, sz;
134 int total = 0;
135
136 int tsz = get_tree_size(kd->treetype);
137 int dsz = get_data_size(kd->treetype);
138
139 char* fmt = "%-10s: %12i %10s * %2i = %12i B (%10.3f MB)\n";
140
141 printf("Memory usage of kdtree (ndata %i, ndim %i, nnodes %i, nleaves %i)\n",
142 kd->ndata, kd->ndim, kd->nnodes, kd->nbottom);
143
144 if (kd->lr) {
145 n = kd->nbottom;
146 sz = sizeof(int32_t);
147 mem = n*sz;
148 printf(fmt, "lr", n, "leaves", sz, mem, 1e-6*mem);
149 total += mem;
150 }
151 if (kd->perm) {
152 n = kd->ndata;
153 sz = sizeof(u32);
154 mem = n*sz;
155 printf(fmt, "perm", n, "points", sz, mem, 1e-6*mem);
156 total += mem;
157 }
158 if (kd->bb.any) {
159 n = kd->nnodes;
160 sz = tsz * 2 * kd->ndim;
161 mem = n*sz;
162 printf(fmt, "bbox", n, "nodes", sz, mem, 1e-6*mem);
163 total += mem;
164 }
165 if (kd->split.any) {
166 n = kd->ninterior;
167 sz = tsz;
168 mem = n*sz;
169 printf(fmt, "split", n, "splits", sz, mem, 1e-6*mem);
170 total += mem;
171 }
172 if (kd->splitdim) {
173 n = kd->ninterior;
174 sz = sizeof(u8);
175 mem = n*sz;
176 printf(fmt, "splitdim", n, "splits", sz, mem, 1e-6*mem);
177 total += mem;
178 }
179
180 printf("Total without data: %12i B (%10.3f MB)\n", total, total*1e-6);
181
182 if (kd->data.any) {
183 n = kd->ndata;
184 sz = dsz * kd->ndim;
185 mem = n*sz;
186 printf(fmt, "data", n, "points", sz, mem, 1e-6*mem);
187 total += mem;
188 }
189 printf("Total including data: %12i B (%10.3f MB)\n", total, total*1e-6);
190
191 }
192
kdtree_level_start(const kdtree_t * kd,int level)193 int kdtree_level_start(const kdtree_t* kd, int level) {
194 return (1 << level) - 1;
195 }
196
kdtree_level_end(const kdtree_t * kd,int level)197 int kdtree_level_end(const kdtree_t* kd, int level) {
198 return (1 << (level+1)) - 2;
199 }
200
node_level(int nodeid)201 static inline u8 node_level(int nodeid) {
202 return an_flsB(nodeid + 1);
203 }
204
kdtree_get_level(const kdtree_t * kd,int nodeid)205 int kdtree_get_level(const kdtree_t* kd, int nodeid) {
206 return node_level(nodeid);
207 }
208
kdtree_get_splitdim(const kdtree_t * kd,int nodeid)209 int kdtree_get_splitdim(const kdtree_t* kd, int nodeid) {
210 u32 tmpsplit;
211 if (kd->splitdim)
212 return kd->splitdim[nodeid];
213
214 switch (kdtree_treetype(kd)) {
215 case KDT_TREE_U32:
216 tmpsplit = kd->split.u[nodeid];
217 break;
218 case KDT_TREE_U16:
219 tmpsplit = kd->split.s[nodeid];
220 break;
221 default:
222 return -1;
223 }
224 return tmpsplit & kd->dimmask;
225 }
226
kdtree_get_splitval(const kdtree_t * kd,int nodeid)227 double kdtree_get_splitval(const kdtree_t* kd, int nodeid) {
228 assert(kd->fun.get_splitval);
229 return kd->fun.get_splitval(kd, nodeid);
230 }
231
kdtree_get_data(const kdtree_t * kd,int i)232 void* kdtree_get_data(const kdtree_t* kd, int i) {
233 switch (kdtree_datatype(kd)) {
234 case KDT_DATA_DOUBLE:
235 return kd->data.d + kd->ndim * i;
236 case KDT_DATA_FLOAT:
237 return kd->data.f + kd->ndim * i;
238 case KDT_DATA_U32:
239 return kd->data.u + kd->ndim * i;
240 case KDT_DATA_U16:
241 return kd->data.s + kd->ndim * i;
242 default:
243 ERROR("kdtree_get_data: invalid data type %i", kdtree_datatype(kd));
244 return NULL;
245 }
246 }
247
kdtree_copy_data_double(const kdtree_t * kd,int start,int N,double * dest)248 void kdtree_copy_data_double(const kdtree_t* kd, int start, int N, double* dest) {
249 int i;
250 int d, D;
251 D = kd->ndim;
252 switch (kdtree_datatype(kd)) {
253 case KDT_DATA_DOUBLE:
254 memcpy(dest, kd->data.d + start*D,
255 N * D * sizeof(double));
256 break;
257 case KDT_DATA_FLOAT:
258 for (i=0; i<(N * D); i++)
259 dest[i] = kd->data.f[start*D + i];
260 break;
261 case KDT_DATA_U32:
262 for (i=0; i<N; i++)
263 for (d=0; d<D; d++)
264 dest[i*D + d] = POINT_INVSCALE(kd, d, kd->data.u[(start + i)*D + d]);
265 break;
266 case KDT_DATA_U16:
267 for (i=0; i<N; i++)
268 for (d=0; d<D; d++)
269 dest[i*D + d] = POINT_INVSCALE(kd, d, kd->data.s[(start + i)*D + d]);
270 break;
271 default:
272 ERROR("kdtree_copy_data_double: invalid data type %i", kdtree_datatype(kd));
273 return;
274 }
275 }
276
kdtree_permute(const kdtree_t * tree,int ind)277 int kdtree_permute(const kdtree_t* tree, int ind) {
278 if (!tree->perm)
279 return ind;
280 return tree->perm[ind];
281 }
282
kdtree_inverse_permutation(const kdtree_t * tree,int * invperm)283 void kdtree_inverse_permutation(const kdtree_t* tree, int* invperm) {
284 int i;
285 if (!tree->perm) {
286 for (i=0; i<tree->ndata; i++)
287 invperm[i] = i;
288 } else {
289 for (i=0; i<tree->ndata; i++) {
290 assert((int)(tree->perm[i]) >= 0);
291 assert((int)(tree->perm[i]) < tree->ndata);
292 invperm[tree->perm[i]] = i;
293 }
294 }
295 }
296
kdtree_build_options_to_string(int opts)297 const char* kdtree_build_options_to_string(int opts) {
298 static char buf[256];
299 sprintf(buf, "%s%s%s%s%s",
300 (opts & KD_BUILD_BBOX) ? "BBOX ":"",
301 (opts & KD_BUILD_SPLIT) ? "SPLIT ":"",
302 (opts & KD_BUILD_SPLITDIM) ? "SPLITDIM ":"",
303 (opts & KD_BUILD_NO_LR) ? "NOLR ":"",
304 (opts & KD_BUILD_LINEAR_LR) ? "LINEARLR ":"");
305 return buf;
306 }
307
kdtree_kdtype_to_string(int kdtype)308 const char* kdtree_kdtype_to_string(int kdtype) {
309 switch (kdtype) {
310 case KDT_DATA_DOUBLE:
311 case KDT_TREE_DOUBLE:
312 case KDT_EXT_DOUBLE:
313 return "double";
314 case KDT_DATA_FLOAT:
315 case KDT_TREE_FLOAT:
316 case KDT_EXT_FLOAT:
317 return "float";
318 case KDT_DATA_U32:
319 case KDT_TREE_U32:
320 return "u32";
321 case KDT_DATA_U16:
322 case KDT_TREE_U16:
323 return "u16";
324 default:
325 return NULL;
326 }
327 }
328
kdtree_kdtype_parse_data_string(const char * str)329 int kdtree_kdtype_parse_data_string(const char* str) {
330 if (!str) return KDT_DATA_NULL;
331 if (!strcmp(str, "double")) {
332 return KDT_DATA_DOUBLE;
333 } else if (!strcmp(str, "float")) {
334 return KDT_DATA_FLOAT;
335 } else if (!strcmp(str, "u32")) {
336 return KDT_DATA_U32;
337 } else if (!strcmp(str, "u16")) {
338 return KDT_DATA_U16;
339 } else
340 return KDT_DATA_NULL;
341 }
342
kdtree_kdtype_parse_tree_string(const char * str)343 int kdtree_kdtype_parse_tree_string(const char* str) {
344 if (!str) return KDT_TREE_NULL;
345 if (!strcmp(str, "double")) {
346 return KDT_TREE_DOUBLE;
347 } else if (!strcmp(str, "float")) {
348 return KDT_TREE_FLOAT;
349 } else if (!strcmp(str, "u32")) {
350 return KDT_TREE_U32;
351 } else if (!strcmp(str, "u16")) {
352 return KDT_TREE_U16;
353 } else
354 return KDT_TREE_NULL;
355 }
356
kdtree_kdtype_parse_ext_string(const char * str)357 int kdtree_kdtype_parse_ext_string(const char* str) {
358 if (!str) return KDT_EXT_NULL;
359 if (!strcmp(str, "double")) {
360 return KDT_EXT_DOUBLE;
361 } else if (!strcmp(str, "float")) {
362 return KDT_EXT_FLOAT;
363 } else
364 return KDT_EXT_NULL;
365 }
366
kdtree_kdtypes_to_treetype(int exttype,int treetype,int datatype)367 int kdtree_kdtypes_to_treetype(int exttype, int treetype, int datatype) {
368 // HACK - asserts here...
369 return exttype | treetype | datatype;
370 }
371
kdtree_new(int N,int D,int Nleaf)372 kdtree_t* kdtree_new(int N, int D, int Nleaf) {
373 kdtree_t* kd;
374 int maxlevel, nnodes;
375 maxlevel = kdtree_compute_levels(N, Nleaf);
376 kd = CALLOC(1, sizeof(kdtree_t));
377 nnodes = (1 << maxlevel) - 1;
378 kd->nlevels = maxlevel;
379 kd->ndata = N;
380 kd->ndim = D;
381 kd->nnodes = nnodes;
382 kd->nbottom = 1 << (maxlevel - 1);
383 kd->ninterior = kd->nbottom - 1;
384 assert(kd->nbottom + kd->ninterior == kd->nnodes);
385 return kd;
386 }
387
kdtree_set_limits(kdtree_t * kd,double * low,double * high)388 void kdtree_set_limits(kdtree_t* kd, double* low, double* high) {
389 int D = kd->ndim;
390 if (!kd->minval) {
391 kd->minval = MALLOC(D * sizeof(double));
392 }
393 if (!kd->maxval) {
394 kd->maxval = MALLOC(D * sizeof(double));
395 }
396 memcpy(kd->minval, low, D * sizeof(double));
397 memcpy(kd->maxval, high, D * sizeof(double));
398 }
399
kdtree_get_conservative_query_radius(const kdtree_t * kd,double radius)400 double kdtree_get_conservative_query_radius(const kdtree_t* kd, double radius) {
401 if (!kd->minval) {
402 return radius;
403 }
404 return sqrt(radius* radius + kd->ndim * 0.25 * kd->invscale*kd->invscale);
405 }
406
kdtree_compute_levels(int N,int Nleaf)407 int kdtree_compute_levels(int N, int Nleaf) {
408 int nnodes = N / Nleaf;
409 int maxlevel = 1;
410 while (nnodes) {
411 nnodes = nnodes >> 1;
412 maxlevel++;
413 }
414 return maxlevel;
415 }
416
kdtree_nnodes_to_nlevels(int Nnodes)417 int kdtree_nnodes_to_nlevels(int Nnodes) {
418 return an_flsB(Nnodes + 1);
419 }
420
421 /* This returns the NODE id (not leaf index) */
kdtree_first_leaf(const kdtree_t * kd,int nodeid)422 int kdtree_first_leaf(const kdtree_t* kd, int nodeid) {
423 int dlevel;
424 dlevel = (kd->nlevels - 1) - node_level(nodeid);
425 return ((nodeid+1) << dlevel) - 1;
426 }
427
428 /* This returns the NODE id (not leaf index) */
kdtree_last_leaf(const kdtree_t * kd,int nodeid)429 int kdtree_last_leaf(const kdtree_t* kd, int nodeid) {
430 int dlevel, twodl, nodeid_twodl;
431 dlevel = (kd->nlevels - 1) - node_level(nodeid);
432 twodl = (1 << dlevel);
433 nodeid_twodl = (nodeid << dlevel);
434 return nodeid_twodl + (twodl - 1)*2;
435 }
436
calculate_R(const kdtree_t * kd,int leafid)437 static int calculate_R(const kdtree_t* kd, int leafid) {
438 int l;
439 unsigned int mask, N, L;
440
441 mask = (1 << (kd->nlevels-1));
442 N = kd->ndata;
443 L = 0;
444 // Compute the L index of the node one to the right of this node.
445 int nextguy = leafid + 1;
446 if (nextguy == kd->nbottom)
447 return kd->ndata-1;
448 for (l=0; l<(kd->nlevels-1); l++) {
449 mask /= 2;
450 if (nextguy & mask) {
451 L += N/2;
452 N = (N+1)/2;
453 } else {
454 N = N/2;
455 }
456 }
457 L--;
458 return L;
459 }
460
linear_lr(const kdtree_t * kd,int leafid)461 static int linear_lr(const kdtree_t* kd, int leafid) {
462 return ((u64)leafid * kd->ndata) / kd->nbottom;
463 }
464
kdtree_leaf_left(const kdtree_t * kd,int nodeid)465 int kdtree_leaf_left(const kdtree_t* kd, int nodeid) {
466 int leafid = nodeid - kd->ninterior;
467 if (!leafid)
468 return 0;
469 if (kd->has_linear_lr)
470 return linear_lr(kd, leafid);
471 if (kd->lr)
472 return kd->lr[leafid-1] + 1;
473 return calculate_R(kd, leafid-1) + 1;
474 }
475
kdtree_leaf_right(const kdtree_t * kd,int nodeid)476 int kdtree_leaf_right(const kdtree_t* kd, int nodeid) {
477 int leafid = nodeid - kd->ninterior;
478 if (kd->has_linear_lr)
479 return linear_lr(kd, leafid+1) - 1;
480 if (kd->lr)
481 return kd->lr[leafid];
482 return calculate_R(kd, leafid);
483 }
484
485
486
kdtree_left(const kdtree_t * kd,int nodeid)487 int kdtree_left(const kdtree_t* kd, int nodeid) {
488 if (KD_IS_LEAF(kd, nodeid)) {
489 return kdtree_leaf_left(kd, nodeid);
490 } else {
491 // leftmost child's L.
492 int leftmost = kdtree_first_leaf(kd, nodeid);
493 return kdtree_leaf_left(kd, leftmost);
494 }
495 }
496
kdtree_right(const kdtree_t * kd,int nodeid)497 int kdtree_right(const kdtree_t* kd, int nodeid) {
498 if (KD_IS_LEAF(kd, nodeid)) {
499 return kdtree_leaf_right(kd, nodeid);
500 } else {
501 // rightmost child's R.
502 int rightmost = kdtree_last_leaf(kd, nodeid);
503 return kdtree_leaf_right(kd, rightmost);
504 }
505 }
506
kdtree_is_leaf_node_empty(const kdtree_t * kd,int nodeid)507 int kdtree_is_leaf_node_empty(const kdtree_t* kd, int nodeid) {
508 int L, R;
509 L = kdtree_leaf_left (kd, nodeid);
510 R = kdtree_leaf_right(kd, nodeid);
511 return (L == R+1);
512 }
513
kdtree_is_node_empty(const kdtree_t * kd,int nodeid)514 int kdtree_is_node_empty(const kdtree_t* kd, int nodeid) {
515 int L, R;
516 L = kdtree_left (kd, nodeid);
517 R = kdtree_right(kd, nodeid);
518 return (L == R+1);
519 }
520
kdtree_npoints(const kdtree_t * kd,int nodeid)521 int kdtree_npoints(const kdtree_t* kd, int nodeid) {
522 return 1 + kdtree_right(kd, nodeid) - kdtree_left(kd, nodeid);
523 }
524
kdtree_free_query(kdtree_qres_t * kq)525 void kdtree_free_query(kdtree_qres_t *kq) {
526 if (!kq) return;
527 FREE(kq->results.any);
528 FREE(kq->sdists);
529 FREE(kq->inds);
530 FREE(kq);
531 }
532
kdtree_free(kdtree_t * kd)533 void kdtree_free(kdtree_t *kd) {
534 if (!kd) return;
535 FREE(kd->name);
536 FREE(kd->lr);
537 FREE(kd->perm);
538 FREE(kd->bb.any);
539 FREE(kd->split.any);
540 FREE(kd->splitdim);
541 if (kd->free_data)
542 FREE(kd->data.any);
543 FREE(kd->minval);
544 FREE(kd->maxval);
545 //FREE(kd->fun);
546 FREE(kd);
547 }
548
kdtree_nearest_neighbour(const kdtree_t * kd,const void * pt,double * p_mindist2)549 int kdtree_nearest_neighbour(const kdtree_t* kd, const void* pt, double* p_mindist2) {
550 return kdtree_nearest_neighbour_within(kd, pt, HUGE_VAL, p_mindist2);
551 }
552
kdtree_check(const kdtree_t * kd)553 int kdtree_check(const kdtree_t* kd) {
554 assert(kd->fun.check);
555 return kd->fun.check(kd);
556 }
557
kdtree_nearest_neighbour_within(const kdtree_t * kd,const void * pt,double maxd2,double * p_mindist2)558 int kdtree_nearest_neighbour_within(const kdtree_t* kd, const void *pt, double maxd2,
559 double* p_mindist2) {
560 double bestd2 = maxd2;
561 int ibest = -1;
562
563 assert(kd->fun.nearest_neighbour_internal);
564 kd->fun.nearest_neighbour_internal(kd, pt, &bestd2, &ibest);
565
566 if (p_mindist2 && (ibest != -1))
567 *p_mindist2 = bestd2;
568 return ibest;
569 }
570
571 KD_DECLARE(kdtree_node_node_mindist2, double, (const kdtree_t* kd1, int node1, const kdtree_t* kd2, int node2));
572
kdtree_node_node_mindist2(const kdtree_t * kd1,int node1,const kdtree_t * kd2,int node2)573 double kdtree_node_node_mindist2(const kdtree_t* kd1, int node1,
574 const kdtree_t* kd2, int node2) {
575 double res = HUGE_VAL;
576 KD_DISPATCH(kdtree_node_node_mindist2, kd1->treetype, res=, (kd1, node1, kd2, node2));
577 return res;
578 }
579
580 KD_DECLARE(kdtree_node_node_maxdist2, double, (const kdtree_t* kd1, int node1, const kdtree_t* kd2, int node2));
581
kdtree_node_node_maxdist2(const kdtree_t * kd1,int node1,const kdtree_t * kd2,int node2)582 double kdtree_node_node_maxdist2(const kdtree_t* kd1, int node1,
583 const kdtree_t* kd2, int node2) {
584 double res = HUGE_VAL;
585 KD_DISPATCH(kdtree_node_node_maxdist2, kd1->treetype, res=, (kd1, node1, kd2, node2));
586 return res;
587 }
588
589 KD_DECLARE(kdtree_node_node_mindist2_exceeds, int, (const kdtree_t* kd1, int node1, const kdtree_t* kd2, int node2, double maxd2));
590
kdtree_node_node_mindist2_exceeds(const kdtree_t * kd1,int node1,const kdtree_t * kd2,int node2,double dist2)591 int kdtree_node_node_mindist2_exceeds(const kdtree_t* kd1, int node1,
592 const kdtree_t* kd2, int node2,
593 double dist2) {
594 int res = FALSE;
595 KD_DISPATCH(kdtree_node_node_mindist2_exceeds, kd1->treetype, res=, (kd1, node1, kd2, node2, dist2));
596 return res;
597 }
598
599 KD_DECLARE(kdtree_node_node_maxdist2_exceeds, int, (const kdtree_t* kd1, int node1, const kdtree_t* kd2, int node2, double maxd2));
600
kdtree_node_node_maxdist2_exceeds(const kdtree_t * kd1,int node1,const kdtree_t * kd2,int node2,double dist2)601 int kdtree_node_node_maxdist2_exceeds(const kdtree_t* kd1, int node1,
602 const kdtree_t* kd2, int node2,
603 double dist2) {
604 int res = FALSE;
605 KD_DISPATCH(kdtree_node_node_maxdist2_exceeds, kd1->treetype, res=, (kd1, node1, kd2, node2, dist2));
606 return res;
607 }
608
609 KD_DECLARE(kdtree_node_point_mindist2, double, (const kdtree_t* kd, int node, const void* query));
610
kdtree_node_point_mindist2(const kdtree_t * kd,int node,const void * pt)611 double kdtree_node_point_mindist2(const kdtree_t* kd, int node, const void* pt) {
612 double res = HUGE_VAL;
613 KD_DISPATCH(kdtree_node_point_mindist2, kd->treetype, res=, (kd, node, pt));
614 return res;
615 }
616
617 KD_DECLARE(kdtree_node_point_maxdist2, double, (const kdtree_t* kd, int node, const void* query));
618
kdtree_node_point_maxdist2(const kdtree_t * kd,int node,const void * pt)619 double kdtree_node_point_maxdist2(const kdtree_t* kd, int node, const void* pt) {
620 double res = HUGE_VAL;
621 KD_DISPATCH(kdtree_node_point_maxdist2, kd->treetype, res=, (kd, node, pt));
622 return res;
623 }
624
625 KD_DECLARE(kdtree_node_point_mindist2_exceeds, int, (const kdtree_t* kd, int node, const void* query, double maxd2));
626
kdtree_node_point_mindist2_exceeds(const kdtree_t * kd,int node,const void * pt,double dist2)627 int kdtree_node_point_mindist2_exceeds(const kdtree_t* kd, int node, const void* pt,
628 double dist2) {
629 int res = FALSE;
630 KD_DISPATCH(kdtree_node_point_mindist2_exceeds, kd->treetype, res=, (kd, node, pt, dist2));
631 return res;
632 }
633
634 KD_DECLARE(kdtree_node_point_maxdist2_exceeds, int, (const kdtree_t* kd, int node, const void* query, double maxd2));
635
kdtree_node_point_maxdist2_exceeds(const kdtree_t * kd,int node,const void * pt,double dist2)636 int kdtree_node_point_maxdist2_exceeds(const kdtree_t* kd, int node, const void* pt,
637 double dist2) {
638 int res = FALSE;
639 KD_DISPATCH(kdtree_node_point_maxdist2_exceeds, kd->treetype, res=, (kd, node, pt, dist2));
640 return res;
641 }
642
kdtree_nodes_contained(const kdtree_t * kd,const void * querylow,const void * queryhi,void (* callback_contained)(const kdtree_t * kd,int node,void * extra),void (* callback_overlap)(const kdtree_t * kd,int node,void * extra),void * cb_extra)643 void kdtree_nodes_contained(const kdtree_t* kd,
644 const void* querylow, const void* queryhi,
645 void (*callback_contained)(const kdtree_t* kd, int node, void* extra),
646 void (*callback_overlap)(const kdtree_t* kd, int node, void* extra),
647 void* cb_extra) {
648 assert(kd->fun.nodes_contained);
649 kd->fun.nodes_contained(kd, querylow, queryhi, callback_contained, callback_overlap, cb_extra);
650 }
651
kdtree_get_bboxes(const kdtree_t * kd,int node,void * bblo,void * bbhi)652 int kdtree_get_bboxes(const kdtree_t* kd, int node, void* bblo, void* bbhi) {
653 assert(kd->fun.get_bboxes);
654 return kd->fun.get_bboxes(kd, node, bblo, bbhi);
655 }
656
kdtree_fix_bounding_boxes(kdtree_t * kd)657 void kdtree_fix_bounding_boxes(kdtree_t* kd) {
658 assert(kd->fun.fix_bounding_boxes);
659 kd->fun.fix_bounding_boxes(kd);
660 }
661
662