00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039 #ifndef G4KDTREE_HH
00040 #define G4KDTREE_HH
00041
00042 #include <vector>
00043 #include "G4KDTreeResult.hh"
00044
00045
00046
00047
00048 void InactiveNode(G4KDNode*);
00049 void Free(G4KDNode*&);
00050 void* GetData(G4KDNode*);
00051 const double* GetNodePosition(G4KDNode*);
00052
00053
00060 class G4KDTree
00061 {
00062 friend class G4KDNode ;
00063 int fDim;
00064 struct HyperRect *fRect;
00065 void (*fDestr)(void*);
00066 int fNbNodes;
00067
00068 protected :
00069 G4KDNode *fRoot;
00070
00071 public :
00072 G4KDTree(int dim = 3);
00073 virtual ~G4KDTree();
00074
00075 void Clear();
00076
00077 inline int GetDim();
00078 inline void SetDataDestructor(void (*fDestr)(void*));
00079
00080 int GetNbNodes() { return fNbNodes; }
00081 G4KDNode* GetRoot() { return fRoot ; }
00082
00083
00084
00085 G4KDNode* Insert(const double *pos, void *data);
00086 G4KDNode* Insert(const double& x, const double& y, const double& z, void *data);
00087
00088
00089
00090
00091
00092 G4KDTreeResultHandle Nearest( const double *pos);
00093 G4KDTreeResultHandle Nearest( const double& x, const double& y, const double& z);
00094 G4KDTreeResultHandle Nearest( G4KDNode* node);
00095
00096
00097
00098
00099
00100
00101
00102
00103 G4KDTreeResultHandle NearestInRange( const double *pos, const double& range);
00104 G4KDTreeResultHandle NearestInRange( const double& x,
00105 const double& y,
00106 const double& z,
00107 const double& range);
00108 G4KDTreeResultHandle NearestInRange( G4KDNode* node, const double& range);
00109
00110 protected :
00111 void __Clear_Rec(G4KDNode *node) ;
00112
00113 int __NearestInRange(G4KDNode *node,
00114 const double *pos,
00115 const double& range_sq,
00116 const double& range,
00117 G4KDTreeResult& list,
00118 int ordered,
00119 G4KDNode *source_node = 0);
00120
00121 void __NearestToPosition(G4KDNode *node,
00122 const double *pos,
00123 G4KDNode *&result,
00124 double *result_dist_sq,
00125 struct HyperRect* fRect);
00126
00127 void __NearestToNode(G4KDNode *source_node,
00128 G4KDNode *node,
00129 const double *pos,
00130 std::vector<G4KDNode*>& result,
00131 double *result_dist_sq,
00132 struct HyperRect* fRect,
00133 int& nbresult) ;
00134 };
00135
00136 inline int G4KDTree::GetDim()
00137 {
00138 return fDim ;
00139 }
00140
00141 void G4KDTree::SetDataDestructor(void (*fct)(void*))
00142 {
00143 fDestr = fct;
00144 }
00145
00146 #endif // G4KDTREE_HH