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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
#include <vector>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
using namespace std;
#define INF 1000000
#undef NDEBUG
float KDTREE_dist(float *coord1, float *coord2, int dim);
class DataPoint
{
private:
long int _index;
float *_coord;
public:
static int dim;
// needed for vector & sort
// T(); T(const T&); ~T(); T& operator=(const T&);
friend int operator<(const DataPoint &self, const DataPoint &other);
friend int operator==(const DataPoint &self, const DataPoint &other);
// end needed for vector
static int current_dim;
void set_data(long int index, float *coord);
float* get_coord(void);
long int get_index(void);
};
class Node
{
private:
Node *_left;
Node *_right;
float _cut_value;
int _cut_dim;
long int _start, _end;
public:
Node(float cut_value, int cut_dim, long int start, long int end);
~Node();
void set_right_node(Node *node);
void set_left_node(Node *node);
Node *get_right_node(void);
Node *get_left_node(void);
long int get_index(void);
float get_cut_value(void);
int get_cut_dim(void);
int is_leaf(void);
int is_bucket(void);
long int get_start(void);
long int get_end(void);
};
class Region
{
private:
float *_left;
float *_right;
public:
static int dim;
Region(float *left=NULL, float *right=NULL);
~Region();
Region *intersect_right(float split_coord, int current_dim);
Region *intersect_left(float split_coord, int current_dim);
float *get_right(void);
float *get_left(void);
int encloses(float *coord);
int test_intersection(Region *query_region, float radius=0);
void print(void);
};
class KDTree
{
private:
vector<DataPoint> _data_point_list;
vector<long int> _index_list;
vector<float> _radius_list;
vector<long int> _neighbor_index_list;
vector<float> _neighbor_radius_list;
Node *_root;
Region *_query_region;
long int _count;
long int _neighbor_count;
float _radius;
float _radius_sq;
float _neighbor_radius;
float _neighbor_radius_sq;
float *_center_coord;
float *_coords;
int _bucket_size;
// Methods
Node *_build_tree(long int offset_begin=0, long int offset_end=0, int depth=0);
void _report_subtree(Node *node);
void _report_point(long int index, float *coord);
void _test_region(Node *node, Region *region, int depth);
void _set_query_region(float *left, float *right);
void _add_point(long int index, float *coord);
void _search(Region *region=NULL, Node *node=NULL, int depth=0);
void _neighbor_search_pairs(Node *left, Region *left_region, Node *right, Region *right_region, int depth);
void _neighbor_search(Node *root, Region *region, int depth);
void _search_neighbors_between_buckets(Node *node1, Node *node2);
void _search_neighbors_in_bucket(Node *node);
void _test_neighbors(DataPoint &p1, DataPoint &p2);
public:
int dim;
KDTree(int dim, int bucket_size);
~KDTree();
void set_data(float *coords, long int nr_points);
// single neighbor search
void search_center_radius(float *coord, float radius);
long int get_count(void);
void copy_indices(long int *indices);
void copy_radii(float *radii);
// all neighbor search
long int neighbor_get_count(void);
void neighbor_search(float neighbor_radius);
void neighbor_simple_search(float neighbor_radius);
void neighbor_copy_indices(long int *indices);
void neighbor_copy_radii(float *radii);
};
|
