Geant4  v4-10.4-release
 모두 클래스 네임스페이스들 파일들 함수 변수 타입정의 열거형 타입 열거형 멤버 Friends 매크로 그룹들 페이지들
G4KDTree.cc
이 파일의 문서화 페이지로 가기
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  * G4KDTree.cc
28  *
29  * Created on: 22 oct. 2013
30  * Author: kara
31  */
32 
33 #include "globals.hh"
34 #include <stdio.h>
35 #include <stdlib.h>
36 #include <cmath>
37 #include "G4KDTree.hh"
38 #include "G4KDMap.hh"
39 #include "G4KDNode.hh"
40 #include "G4KDTreeResult.hh"
41 #include <list>
42 #include <iostream>
43 
44 using namespace std;
45 
47 {
48  G4ThreadLocalStatic G4Allocator<G4KDTree>* _instance = nullptr;
49  return _instance;
50 }
51 
52 //______________________________________________________________________
53 // KDTree methods
54 G4KDTree::G4KDTree(size_t k) :
55  fKDMap(new G4KDMap(k))
56 {
57  fDim = k;
58  fRoot = 0;
59  fRect = 0;
60  fNbNodes = 0;
61  fNbActiveNodes = 0;
62 }
63 
65 {
66  if (fRoot) __Clear_Rec(fRoot);
67  fRoot = 0;
68 
69  if (fRect)
70  {
71  delete fRect;
72  fRect = 0;
73  }
74 
75  if (fKDMap) delete fKDMap;
76 }
77 
78 void* G4KDTree::operator new(size_t)
79 {
80  if (!fgAllocator()) fgAllocator() = new G4Allocator<G4KDTree>;
81  return (void *) fgAllocator()->MallocSingle();
82 }
83 
84 void G4KDTree::operator delete(void *aNode)
85 {
86  fgAllocator()->FreeSingle((G4KDTree*) aNode);
87 }
88 
89 void G4KDTree::Print(std::ostream& out) const
90 {
91  if (fRoot) fRoot->Print(out);
92 }
93 
95 {
97  fRoot = 0;
98  fNbNodes = 0;
99 
100  if (fRect)
101  {
102  delete fRect;
103  fRect = 0;
104  }
105 }
106 
108 {
109  if (!node) return;
110 
111  if (node->GetLeft()) __Clear_Rec(node->GetLeft());
112  if (node->GetRight()) __Clear_Rec(node->GetRight());
113 
114  delete node;
115 }
116 
118 {
119  fKDMap->Insert(node);
120 }
121 
123 {
124  size_t Nnodes = fKDMap->GetSize();
125 
126  G4cout << "********************" << G4endl;
127  G4cout << "template<typename PointT> G4KDTree<PointT>::Build" << G4endl;
128  G4cout << "Map size = " << Nnodes << G4endl;
129 
130  G4KDNode_Base* root = fKDMap->PopOutMiddle(0);
131 
132  if(root == 0) return;
133 
134  fRoot = root;
135  fNbActiveNodes++;
136  fRect = new HyperRect(fDim);
137  fRect->SetMinMax(*fRoot, *fRoot);
138 
139  Nnodes--;
140 
141  G4KDNode_Base* parent = fRoot;
142 
143  for (size_t n = 0; n < Nnodes; n += fDim)
144  {
145  for (size_t dim = 0; dim < fDim; dim++)
146  {
147  G4KDNode_Base* node = fKDMap->PopOutMiddle(dim);
148  if (node)
149  {
150  parent->Insert(node);
151  fNbActiveNodes++;
152  fRect->Extend(*node);
153  parent = node;
154  }
155  }
156  }
157 }
158 
160 {
161  // G4cout << "Nearest(node)" << G4endl ;
162  if (!fRect)
163  {
164  G4cout << "Tree empty" << G4endl;
165  return 0;
166  }
167 
168  std::vector<G4KDNode_Base* > result;
169  double dist_sq = DBL_MAX;
170 
171  /* Duplicate the bounding hyperrectangle, we will work on the copy */
172  HyperRect *newrect = new HyperRect(*fRect);
173 
174  /* Search for the nearest neighbour recursively */
175  int nbresult = 0;
176 
177  __NearestToNode(node, fRoot, *node, result, &dist_sq, newrect, nbresult);
178 
179  /* Free the copy of the hyperrect */
180  delete newrect;
181 
182  /* Store the result */
183  if (!result.empty())
184  {
185  G4KDTreeResultHandle rset(new G4KDTreeResult(this));
186  int j = 0;
187  while (j<nbresult)
188  {
189  rset->Insert(dist_sq, result[j]);
190  j++;
191  }
192  rset->Rewind();
193 
194  return rset;
195  }
196  else
197  {
198  return 0;
199  }
200 }
201 
203  const double& range)
204 {
205  if (!node) return 0;
206  int ret(-1);
207 
208  G4KDTreeResult *rset = new G4KDTreeResult(this);
209 
210  const double range_sq = sqr(range);
211 
212  if ((ret = __NearestInRange(fRoot, *node, range_sq, range, *rset, 0, node)) == -1)
213  {
214  delete rset;
215  return 0;
216  }
217  rset->Sort();
218  rset->Rewind();
219  return rset;
220 }
~G4KDTree()
Definition: G4KDTree.cc:64
static G4Allocator< G4KDTree > *& fgAllocator()
Definition: G4KDTree.cc:46
G4KDNode_Base * Insert(PointT *point)
HyperRect * fRect
Definition: G4KDTree.hh:267
G4KDTree(size_t dim=3)
Definition: G4KDTree.cc:54
G4KDNode_Base * fRoot
Definition: G4KDTree.hh:268
G4KDTreeResultHandle NearestInRange(const Position &pos, const double &range)
int __NearestInRange(G4KDNode_Base *node, const Position &pos, const double &range_sq, const double &range, G4KDTreeResult &list, int ordered, G4KDNode_Base *source_node=0)
#define G4endl
Definition: G4ios.hh:61
G4KDNode_Base * PopOutMiddle(size_t dimension)
Definition: G4KDMap.cc:137
Type * MallocSingle()
Definition: G4Allocator.hh:202
G4KDMap * fKDMap
Definition: G4KDTree.hh:272
void Print(std::ostream &out=G4cout) const
Definition: G4KDTree.cc:89
#define G4ThreadLocalStatic
Definition: tls.hh:68
void __InsertMap(G4KDNode_Base *node)
Definition: G4KDTree.cc:117
void Print(std::ostream &out, int level=0) const
Definition: G4KDNode.cc:178
int fNbNodes
Definition: G4KDTree.hh:270
const G4ParticleDefinition const G4Material *G4double range
G4KDTreeResultHandle Nearest(const Position &pos)
void SetMinMax(const Position &min, const Position &max)
Definition: G4KDTree.hh:145
void Extend(const Position &pos)
Definition: G4KDTree.hh:174
G4double G4ParticleHPJENDLHEData::G4double result
G4KDNode_Base * GetRight()
Definition: G4KDNode.hh:83
void Build()
Definition: G4KDTree.cc:122
G4KDNode_Base * GetLeft()
Definition: G4KDNode.hh:82
void __NearestToNode(G4KDNode_Base *source_node, G4KDNode_Base *node, const Position &pos, std::vector< G4KDNode_Base * > &result, double *result_dist_sq, HyperRect *fRect, int &nbresult)
G4GLOB_DLL std::ostream G4cout
Char_t n[5]
void Insert(G4KDNode_Base *pos)
Definition: G4KDMap.cc:90
T sqr(const T &x)
Definition: templates.hh:145
size_t fDim
Definition: G4KDTree.hh:269
void Clear()
Definition: G4KDTree.cc:94
#define DBL_MAX
Definition: templates.hh:83
size_t GetSize()
Definition: G4KDMap.hh:110
int fNbActiveNodes
Definition: G4KDTree.hh:271
void __Clear_Rec(G4KDNode_Base *node)
Definition: G4KDTree.cc:107