-
Notifications
You must be signed in to change notification settings - Fork 0
/
bktree.h
51 lines (39 loc) · 1.19 KB
/
bktree.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#ifndef BKTREE_H
#define BKTREE_H
#include "limits.h"
#define BKTREE_SCALAR_MAX USHRT_MAX
#define BKTREE_VALUE_MAX USHRT_MAX
#define BKTREE_DISTANCE_MAX UINT_MAX
#define BKTREE_SIZE_MAX INT_MAX
typedef unsigned long BKValue;
typedef unsigned int BKSize;
typedef unsigned int BKDistance;
typedef unsigned int BKScalar;
typedef unsigned char BKBool;
typedef struct {
BKBool leaf;
BKScalar x;
BKScalar y;
BKValue value;
} BKNode;
typedef struct {
BKNode * nodes;
BKSize depth;
BKSize count;
BKSize capacity;
} BKTree;
typedef struct {
BKValue value;
BKDistance distance_sq;
} BKResult;
void bktree_initialize(BKTree * tree);
// increases or decreases the capacity to be able to store at least `n` nodes
// the new capacity will be greater or equal to `n`
void bktree_build(BKTree * tree, BKNode * nodes, BKSize n);
// find up to `n` closest nodes within `max_distance` of point `x`,`y`. The amount of nodes found is
// returned.
BKSize bktree_find(BKTree * tree, BKScalar x, BKScalar y, BKResult * results, BKSize n, BKDistance max_distance_sq);
// find the closest node for `p`
BKResult bktree_first(BKTree * tree, BKScalar x, BKScalar y);
void bktree_deinitialize(BKTree * tree);
#endif