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
126
127
128
129
130
131
132
133
134
135
136
137
|
#ifndef KD_Tree_H__
#define KD_Tree_H__
#include <list>
#include <vector>
#include <cstdlib>
#include <queue>
#include <utility.h>
namespace meow{
template<class Vector, class Scalar>
class KD_Tree{
private:
struct Node{
Vector _vector;
ssize_t _lChild;
ssize_t _rChild;
//
Node(Vector __vector, ssize_t __lChild, ssize_t __rChild);
};
typedef std::vector<Node> Nodes;
//
class Sorter{
private:
Nodes const* _nodes;
size_t _cmp;
public:
Sorter(Nodes const* __nodes, size_t __cmp);
bool operator()(size_t const& __a, size_t const& __b) const;
};
struct Answer{
ssize_t _index;
Scalar _dist2;
//
Answer(ssize_t __index, Scalar __dist2);
Answer(Answer const& __answer2);
};
class AnswerCompare{
private:
Nodes const* _nodes;
bool _cmpValue;
public:
AnswerCompare(Nodes const* __nodes, bool __cmpValue);
bool operator()(Answer const& __a, Answer const& __b) const;
};
typedef std::vector<Answer> AnswerV;
typedef std::priority_queue<Answer, AnswerV, AnswerCompare> Answers;
//
const ssize_t _NIL;
//
Nodes _nodes;
size_t _root;
bool _needRebuild;
size_t _dimension;
//
Scalar distance2(Vector const& __v1, Vector const& __v2) const;
//
void query(Vector const& __vector,
size_t __nearestNumber,
AnswerCompare const& __answerCompare,
size_t __index,
int __depth,
std::vector<Scalar>& __dist2Vector,
Scalar __dist2Minimum,
Answers *__out) const;
ssize_t build(ssize_t __beg,
ssize_t __end,
std::vector<size_t>* __orders,
int __depth);
public:
typedef typename std::vector<Vector> Vectors;
//
KD_Tree();
KD_Tree(size_t __dimension);
~KD_Tree();
//
void insert(Vector const& __vector);
bool erase (Vector const& __vector);
void build();
void forceBuild();
//
Vectors query(Vector const& __vector,
size_t __nearestNumber,
bool __compareWholeVector) const;
//
void clear();
void reset(size_t __dimension);
};
/*********************************************************
@asciidoc
=== meow:: *KD_Tree<Vector, Scalar>* (C++ class)
.Description
`KD_Tree` is *K-dimension tree*, which is a multiple set contain lots of
vector with K dimension.
.Template Request
* `Vector` should has `operator[]` to allow the KD_Tree, `operator<` to
compare when two vector are point to the same place, `operator==`
access the k-dimensions
* `Scalar` should has `operator*`, `operator+`, `operator<`
.Support Methods
* N <- numbers of element in the kd-tree
* K <- dimensions
* `Vector` is the tyepname of the vector
* `Vectors` is the typename of the std::vector<Vector>
[options="header",width="100%",cols="1>,1<s,5<,1<,2<,10<",grid="rows"]
|=======================================================================
|Const?|Name| Parameters| Return Type| Time Complexity| Description
|const|root|(size_t number)|size_t|very fast|
||insert|(Vector const& v)|void|O(1)|Insert a vector
||erase |(Vector const& v)|bool|O(N*x)| Find a vector which is the same
as `v` and remove it from the KD_Tree, `x` in the Big-O time complex
is cost by `Vector::operator==`.
|| build|()|void|O(KN logN) if need | Build the data structure if need.
|| forceBuild|()|void|O(KN logN) | Build the data structure(the `insert()`
method will not build the data structure immediately)
|const|query|(Vector const& v, int k)|Vectors|O(kN ^1-1/k^ ) |
Using Euclidean-Distance to find the 1st to k-th nearest neighbor from `v` .
And return;
||clear|()|O(1)|Clear all data
||reset|(size_t dimension)|O(1)|Clear all data and then
set the this->dimension be `dimension`
|=======================================================================
NOTE: O(kN ^1-1/k^ ) is reference from wiki. +
`query()` and `rangeQuery()` will run `build()` first if you called `insert()`
before call them. And `build()` is very slow, so you should not use this class
as a dynamic tree
'''
@asciidoc-
*********************************************************/
}
#include "KD_Tree.hpp"
#endif // KD_Tree_H__
|
