Garfield 0.3
Toolkit for the detailed simulation of particle detectors based on ionization measurement in gases and semiconductors
Loading...
Searching...
No Matches
KDTree.hh
Go to the documentation of this file.
1#ifndef G_KDTREE2_H
2#define G_KDTREE2_H
3
4// (c) Matthew B. Kennel, Institute for Nonlinear Science, UCSD (2004)
5//
6// Licensed under the Academic Free License version 1.1 found in file LICENSE
7// with additional provisions in that same file.
8
9// Implement a kd tree for fast searching of points in a fixed data base
10// in k-dimensional Euclidean space.
11
12#include <array>
13#include <queue>
14#include <vector>
15#include <cstddef>
16
17namespace Garfield {
18
19typedef std::vector<std::vector<double> > KDTreeArray;
20
21class KDTreeNode;
22
24
26 double dis; //< square Euclidean distance
27 std::size_t idx; //< index
28};
29
32
33class KDTree {
34 public:
35 // Reference to the underlying data to be included in the tree.
37
38 std::size_t m_dim = 3;
39 bool sort_results = false;
40
41 public:
42 KDTree() = delete;
47
53 void n_nearest(const std::vector<double>& qv, const unsigned int nn,
54 std::vector<KDTreeResult>& result) const;
55
63 void n_nearest_around_point(const unsigned int idx,
64 const unsigned int ndecorrel,
65 const unsigned int nn,
66 std::vector<KDTreeResult>& result) const;
67
73 void r_nearest(const std::vector<double>& qv, const double r2,
74 std::vector<KDTreeResult>& result) const;
75
78 void r_nearest_around_point(const unsigned int idx,
79 const unsigned int ndecorrel, const double r2,
80 std::vector<KDTreeResult>& result) const;
81
82 friend class KDTreeNode;
83
84 private:
85 KDTreeNode* m_root = nullptr;
86
87 // Index for the tree leaves. Data in a leaf with bounds [l,u] are
88 // in 'data[ind[l],*] to data[ind[u],*]
89 std::vector<std::size_t> m_ind;
90
91 static constexpr int bucketsize = 12; // global constant.
92
93 private:
95 int select_on_coordinate_value(int c, double alpha, int l, int u);
96 std::array<double, 2> spread_in_coordinate(const int c, const int l,
97 const int u) const;
98};
99
101
103 public:
105 KDTreeNode(int dim);
108
109 private:
110 friend class KDTree;
111
112 // Dimension to cut.
113 std::size_t cut_dim = 0;
114 // Cut value.
115 double cut_val = 0.;
116 double cut_val_left = 0.;
117 double cut_val_right = 0.;
118 // Extents in index array for searching
119 int m_l = 0;
120 int m_u = 0;
121 // [min,max] of the box enclosing all points
122 std::vector<std::array<double, 2> > box;
123
124 // Pointers to left and right nodes.
125 KDTreeNode* left = nullptr;
126 KDTreeNode* right = nullptr;
127
128 // Recursive innermost core routines for searching.
129 void search_n(const int idx0, const int nd, const unsigned int nn, double& r2,
130 const std::vector<double>& qv, const KDTree& tree,
131 std::priority_queue<KDTreeResult>& res) const;
132 void search_r(const int idx0, const int nd, const double r2,
133 const std::vector<double>& qv, const KDTree& tree,
134 std::vector<KDTreeResult>& res) const;
135
136 // Return true if the bounding box for this node is within the
137 // search range around a point.
138 bool box_in_search_range(const double r2,
139 const std::vector<double>& qv) const;
140
141 // For processing final buckets.
142 void process_terminal_node_n(const int idx0, const int nd,
143 const unsigned int nn, double& r2,
144 const std::vector<double>& qv,
145 const KDTree& tree,
146 std::priority_queue<KDTreeResult>& res) const;
147 void process_terminal_node_r(const int idx0, const int nd, const double r2,
148 const std::vector<double>& qv,
149 const KDTree& tree,
150 std::vector<KDTreeResult>& res) const;
151};
152
153} // namespace Garfield
154
155#endif
A node in the k-d tree.
Definition KDTree.hh:102
void process_terminal_node_n(const int idx0, const int nd, const unsigned int nn, double &r2, const std::vector< double > &qv, const KDTree &tree, std::priority_queue< KDTreeResult > &res) const
std::vector< std::array< double, 2 > > box
Definition KDTree.hh:122
void search_r(const int idx0, const int nd, const double r2, const std::vector< double > &qv, const KDTree &tree, std::vector< KDTreeResult > &res) const
friend class KDTree
Definition KDTree.hh:110
KDTreeNode(int dim)
Constructor.
~KDTreeNode()
Destructor.
void search_n(const int idx0, const int nd, const unsigned int nn, double &r2, const std::vector< double > &qv, const KDTree &tree, std::priority_queue< KDTreeResult > &res) const
KDTreeNode * left
Definition KDTree.hh:125
bool box_in_search_range(const double r2, const std::vector< double > &qv) const
void process_terminal_node_r(const int idx0, const int nd, const double r2, const std::vector< double > &qv, const KDTree &tree, std::vector< KDTreeResult > &res) const
KDTreeNode * right
Definition KDTree.hh:126
std::size_t cut_dim
Definition KDTree.hh:113
std::size_t m_dim
Definition KDTree.hh:38
bool sort_results
Definition KDTree.hh:39
const KDTreeArray & m_data
Definition KDTree.hh:36
void n_nearest_around_point(const unsigned int idx, const unsigned int ndecorrel, const unsigned int nn, std::vector< KDTreeResult > &result) const
Search for nn nearest neighbours around a node of the input data, excluding neighbors within a decorr...
std::array< double, 2 > spread_in_coordinate(const int c, const int l, const int u) const
friend class KDTreeNode
Definition KDTree.hh:82
static constexpr int bucketsize
Definition KDTree.hh:91
void r_nearest(const std::vector< double > &qv, const double r2, std::vector< KDTreeResult > &result) const
Search for all neighbors in a ball of size r2.
KDTreeNode * build_tree_for_range(int l, int u, KDTreeNode *parent)
~KDTree()
Destructor.
KDTree(KDTreeArray &data_in)
Constructor.
std::vector< std::size_t > m_ind
Definition KDTree.hh:89
void n_nearest(const std::vector< double > &qv, const unsigned int nn, std::vector< KDTreeResult > &result) const
Search for nn nearest neighbours around a point.
KDTreeNode * m_root
Definition KDTree.hh:85
int select_on_coordinate_value(int c, double alpha, int l, int u)
void r_nearest_around_point(const unsigned int idx, const unsigned int ndecorrel, const double r2, std::vector< KDTreeResult > &result) const
Like r_nearest, but around an existing point, with decorrelation interval.
std::vector< std::vector< double > > KDTreeArray
Definition KDTree.hh:19
Search result.
Definition KDTree.hh:25
std::size_t idx
Definition KDTree.hh:27