ECCE @ EIC Software
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
G4KDTree.hh
Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file G4KDTree.hh
1 //
2 // ********************************************************************
3 // * License and Disclaimer *
4 // * *
5 // * The Geant4 software is copyright of the Copyright Holders of *
6 // * the Geant4 Collaboration. It is provided under the terms and *
7 // * conditions of the Geant4 Software License, included in the file *
8 // * LICENSE and available at http://cern.ch/geant4/license . These *
9 // * include a list of copyright holders. *
10 // * *
11 // * Neither the authors of this software system, nor their employing *
12 // * institutes,nor the agencies providing financial support for this *
13 // * work make any representation or warranty, express or implied, *
14 // * regarding this software system or assume any liability for its *
15 // * use. Please see the license in the file LICENSE and URL above *
16 // * for the full disclaimer and the limitation of liability. *
17 // * *
18 // * This code implementation is the result of the scientific and *
19 // * technical work of the GEANT4 collaboration. *
20 // * By using, copying, modifying or distributing the software (or *
21 // * any work based on the software) you agree to acknowledge its *
22 // * use in resulting scientific publications, and indicate your *
23 // * acceptance of all terms of the Geant4 Software license. *
24 // ********************************************************************
25 //
26 //
27 // Author: Mathieu Karamitros
28 
29 // The code is developed in the framework of the ESA AO7146
30 //
31 // We would be very happy hearing from you, send us your feedback! :)
32 //
33 // In order for Geant4-DNA to be maintained and still open-source,
34 // article citations are crucial.
35 // If you use Geant4-DNA chemistry and you publish papers about your software,
36 // in addition to the general paper on Geant4-DNA:
37 //
38 // Int. J. Model. Simul. Sci. Comput. 1 (2010) 157–178
39 //
40 // we would be very happy if you could please also cite the following
41 // reference papers on chemistry:
42 //
43 // J. Comput. Phys. 274 (2014) 841-882
44 // Prog. Nucl. Sci. Tec. 2 (2011) 503-508
45 
46 #ifndef G4KDTREE_HH
47 #define G4KDTREE_HH 1
48 
49 #include <vector>
50 #include "G4KDNode.hh"
51 #include "G4KDTreeResult.hh"
52 
53 class G4KDMap;
54 template<typename PointT> class G4KDNode;
55 
56 //__________________________________
57 // Methods to act on kdnode
58 // Methods defined in G4KDNode.cc :
60 void Free(G4KDNode_Base*&);
61 //void* GetData(G4KDNode*);
62 //const double* GetNodePosition(G4KDNode_Base*);
63 //__________________________________
64 
70 class G4KDTree
71 {
72  friend class G4KDNode_Base;
73 public:
74  G4KDTree(size_t dim = 3);
75  ~G4KDTree();
76  void Clear();
77 
78  void Print(std::ostream& out = G4cout) const;
79  void Build();
81  {
83  if (fNbActiveNodes <= 0) Clear();
84  }
85 
86  size_t GetDim() const
87  {
88  return fDim;
89  }
90  int GetNbNodes() const
91  {
92  return fNbNodes;
93  }
95  {
96  return fRoot;
97  }
98 
99  template<typename PointT>
100  G4KDNode_Base* InsertMap(PointT* pos);
101 
102  // Insert and attache the data to a node at the specified position
103  // In return, it gives you the corresponding node
104  template<typename PointT> G4KDNode_Base* Insert(PointT* pos); // 3D
105 
106  template<typename PointT> G4KDNode_Base* Insert(const PointT& pos); // 3D
107 
108  /* Find one of the nearest nodes from the specified point.
109  *
110  * This function returns a pointer to a result set with at most one element.
111  */
112  template<typename Position> G4KDTreeResultHandle Nearest(const Position& pos);
114 
115  /* Find any nearest nodes from the specified point within a range.
116  *
117  * This function returns a pointer to a result set, which can be manipulated
118  * by the G4KDTreeResult.
119  * The returned pointer can be null as an indication of an error. Otherwise
120  * a valid result set is always returned which may contain 0 or more elements.
121  */
122  template<typename Position>
123  G4KDTreeResultHandle NearestInRange(const Position& pos,
124  const double& range);
125  G4KDTreeResultHandle NearestInRange(G4KDNode_Base* node, const double& range);
126 
127  void *operator new(size_t);
128  void operator delete(void *);
129 
130 protected:
131 
132  //______________________________________________________________________
133  class HyperRect
134  {
135  public:
136  HyperRect(size_t dim)
137  {
138  fDim = dim;
139  fMin = new double[fDim];
140  fMax = new double[fDim];
141  }
142 
143  template<typename Position>
144  void SetMinMax(const Position& min, const Position& max)
145  {
146  for (size_t i = 0; i < fDim; i++)
147  {
148  fMin[i] = min[i];
149  fMax[i] = max[i];
150  }
151  }
152 
154  {
155  delete[] fMin;
156  delete[] fMax;
157  }
158 
159  HyperRect(const HyperRect& rect)
160  {
161  fDim = rect.fDim;
162  fMin = new double[fDim];
163  fMax = new double[fDim];
164 
165  for (size_t i = 0; i < fDim; i++)
166  {
167  fMin[i] = rect.fMin[i];
168  fMax[i] = rect.fMax[i];
169  }
170  }
171 
172  template<typename Position>
173  void Extend(const Position& pos)
174  {
175  for (size_t i = 0; i < fDim; i++)
176  {
177  if (pos[i] < fMin[i])
178  {
179  fMin[i] = pos[i];
180  }
181  if (pos[i] > fMax[i])
182  {
183  fMax[i] = pos[i];
184  }
185  }
186  }
187 
188  template<typename Position>
189  bool CompareDistSqr(const Position& pos, const double* bestmatch)
190  {
191  double result = 0;
192 
193  for (size_t i = 0; i < fDim; i++)
194  {
195  if (pos[i] < fMin[i])
196  {
197  result += sqr(fMin[i] - pos[i]);
198  }
199  else if (pos[i] > fMax[i])
200  {
201  result += sqr(fMax[i] - pos[i]);
202  }
203 
204  if (result >= *bestmatch) return false;
205  }
206 
207  return true;
208  }
209 
210  size_t GetDim()
211  {
212  return fDim;
213  }
214  double* GetMin()
215  {
216  return fMin;
217  }
218  double* GetMax()
219  {
220  return fMax;
221  }
222 
223  protected:
224  size_t fDim;
225  double *fMin, *fMax; /* minimum/maximum coords */
226 
227  private:
228  // should not be used
230  {
231  if (this == &rhs) return *this;
232  return *this;
233  }
234  };
235 
236 protected:
237  void __InsertMap(G4KDNode_Base *node);
238  void __Clear_Rec(G4KDNode_Base *node);
239 
240  template<typename Position>
242  const Position& pos,
243  const double& range_sq,
244  const double& range,
245  G4KDTreeResult& list,
246  int ordered,
247  G4KDNode_Base *source_node = 0);
248 
249  template<typename Position>
251  const Position& pos,
252  G4KDNode_Base *&result,
253  double *result_dist_sq,
254  HyperRect* fRect);
255 
256  template<typename Position>
257  void __NearestToNode(G4KDNode_Base *source_node,
258  G4KDNode_Base *node,
259  const Position& pos,
260  std::vector<G4KDNode_Base*>& result,
261  double *result_dist_sq,
262  HyperRect* fRect,
263  int& nbresult);
264 
265 protected:
268  size_t fDim;
269  int fNbNodes;
272 
274 };
275 
276 #include "G4KDTree.icc"
277 
278 #endif // G4KDTREE_HH