kdTree.h
Go to the documentation of this file.
1 /**
2  * @file kdTree.h
3  *
4  * @brief Implements a kdTree for use in clustering
5  *
6  * @author usher@slac.stanford.edu
7  *
8  */
9 #ifndef kdTree_h
10 #define kdTree_h
11 
12 // Framework Includes
13 #include "fhiclcpp/fwd.h"
14 
15 // Algorithm includes
17 
18 // std includes
19 #include <list>
20 #include <vector>
21 #include <utility>
22 
23 //------------------------------------------------------------------------------------------------------------------------------------------
24 
25 namespace lar_cluster3d
26 {
27 /**
28  * @brief kdTree class definiton
29  */
30 class kdTree
31 {
32 public:
33  /**
34  * @brief Default Constructor
35  */
37  fTimeToBuild(0.),
39  fRefLeafBestDist(0.),
40  fMaxWireDeltas(0) {}
41 
42  /**
43  * @brief Constructor
44  *
45  * @param pset
46  */
47  kdTree(fhicl::ParameterSet const &pset);
48 
49  /**
50  * @brief Destructor
51  */
52  ~kdTree();
53 
54  /**
55  * @brief Configure our kdTree...
56  *
57  * @param ParameterSet The input set of parameters for configuration
58  */
59  void configure(fhicl::ParameterSet const &pset);
60 
61  /**
62  * @brief Define some data structures useful for the kd tree
63  */
64  class KdTreeNode;
65 
66  using KdTreeNodeVec = std::vector<KdTreeNode>;
67  using KdTreeNodeList = std::list<KdTreeNode>;
68  using Hit3DVec = std::vector<const reco::ClusterHit3D*>;
69 
70  /**
71  * @brief Given an input set of ClusterHit3D objects, build a kd tree structure
72  *
73  * @param hitPairList The input list of 3D hits to run clustering on
74  * @param kdTreeVec Container for the nodes
75  */
77 
78  using CandPair = std::pair<double,const reco::ClusterHit3D*>;
79  using CandPairList = std::list<CandPair>;
80 
81  size_t FindNearestNeighbors(const reco::ClusterHit3D*, const KdTreeNode&, CandPairList&, float&) const;
82  bool FindEntry(const reco::ClusterHit3D*, const KdTreeNode&, CandPairList&, float&, bool&, int) const;
83  bool FindEntryBrute(const reco::ClusterHit3D*, const KdTreeNode&, int) const;
84 
85  /**
86  * @brief Given an input HitPairList, build out the map of nearest neighbors
87  */
89 
90  /**
91  * @brief Given an input HitPairListPtr, build out the map of nearest neighbors
92  */
94 
95  float getTimeToExecute() const {return fTimeToBuild;}
96 
97 private:
98 
99  /**
100  * @brief The bigger question: are two pairs of hits consistent?
101  */
102  bool consistentPairs(const reco::ClusterHit3D* pair1, const reco::ClusterHit3D* pair2, float& hitSeparation) const;
103 
104  float DistanceBetweenNodes (const reco::ClusterHit3D*,const reco::ClusterHit3D*) const;
106 
107  bool fEnableMonitoring; ///<
108  mutable float fTimeToBuild; ///<
109  float fPairSigmaPeakTime; ///< Consider hits consistent if "significance" less than this
110  float fRefLeafBestDist; ///< Set neighborhood distance to this when ref leaf found
111  int fMaxWireDeltas; ///< Maximum total number of delta wires
112 
113 };
114 
115 /**
116  * @brief define a kd tree node
117  */
119 {
120 public:
126  };
127 
128  KdTreeNode(SplitAxis axis, float axisVal, const KdTreeNode& left, const KdTreeNode& right) :
129  m_splitAxis(axis),
130  m_axisValue(axisVal),
131  m_clusterHit3D(0),
132  m_leftTree(left),
133  m_rightTree(right)
134  {}
135 
137  m_splitAxis(SplitAxis::leaf),
138  m_axisValue(0.),
139  m_clusterHit3D(hit),
140  m_leftTree(*this),
141  m_rightTree(*this)
142  {}
143 
144  KdTreeNode() : m_splitAxis(SplitAxis::null),
145  m_axisValue(0.),
146  m_clusterHit3D(0),
147  m_leftTree(*this),
148  m_rightTree(*this)
149  {}
150 
151  bool isLeafNode() const {return m_splitAxis == SplitAxis::leaf;}
152  bool isNullNode() const {return m_splitAxis == SplitAxis::null;}
153 
154  SplitAxis getSplitAxis() const {return m_splitAxis;}
155  float getAxisValue() const {return m_axisValue;}
156  const reco::ClusterHit3D* getClusterHit3D() const {return m_clusterHit3D;}
157  const KdTreeNode& leftTree() const {return m_leftTree;}
158  const KdTreeNode& rightTree() const {return m_rightTree;}
159 
160 private:
161 
163  float m_axisValue;
167 };
168 
169 } // namespace lar_cluster3d
170 #endif
intermediate_table::iterator iterator
float fRefLeafBestDist
Set neighborhood distance to this when ref leaf found.
Definition: kdTree.h:110
std::list< reco::ClusterHit3D > HitPairList
Definition: Cluster3D.h:339
kdTree class definiton
Definition: kdTree.h:30
const KdTreeNode & m_leftTree
Definition: kdTree.h:165
void configure(fhicl::ParameterSet const &pset)
Configure our kdTree...
Definition: kdTree.cxx:37
std::list< KdTreeNode > KdTreeNodeList
Definition: kdTree.h:67
size_t FindNearestNeighbors(const reco::ClusterHit3D *, const KdTreeNode &, CandPairList &, float &) const
Definition: kdTree.cxx:170
std::vector< const reco::ClusterHit3D * > Hit3DVec
Definition: kdTree.h:68
kdTree()
Default Constructor.
Definition: kdTree.h:36
float DistanceBetweenNodes(const reco::ClusterHit3D *, const reco::ClusterHit3D *) const
Definition: kdTree.cxx:327
const KdTreeNode & m_rightTree
Definition: kdTree.h:166
define a kd tree node
Definition: kdTree.h:118
std::pair< double, const reco::ClusterHit3D * > CandPair
Definition: kdTree.h:78
KdTreeNode(const reco::ClusterHit3D *hit)
Definition: kdTree.h:136
~kdTree()
Destructor.
Definition: kdTree.cxx:31
std::list< const reco::ClusterHit3D * > HitPairListPtr
Definition: Cluster3D.h:335
bool consistentPairs(const reco::ClusterHit3D *pair1, const reco::ClusterHit3D *pair2, float &hitSeparation) const
The bigger question: are two pairs of hits consistent?
Definition: kdTree.cxx:272
Detector simulation of raw signals on wires.
null
Definition: demo.py:50
std::list< CandPair > CandPairList
Definition: kdTree.h:79
float DistanceBetweenNodesYZ(const reco::ClusterHit3D *, const reco::ClusterHit3D *) const
Definition: kdTree.cxx:316
bool FindEntry(const reco::ClusterHit3D *, const KdTreeNode &, CandPairList &, float &, bool &, int) const
Definition: kdTree.cxx:207
bool FindEntryBrute(const reco::ClusterHit3D *, const KdTreeNode &, int) const
Definition: kdTree.cxx:252
KdTreeNode(SplitAxis axis, float axisVal, const KdTreeNode &left, const KdTreeNode &right)
Definition: kdTree.h:128
float fPairSigmaPeakTime
Consider hits consistent if "significance" less than this.
Definition: kdTree.h:109
const KdTreeNode & rightTree() const
Definition: kdTree.h:158
int fMaxWireDeltas
Maximum total number of delta wires.
Definition: kdTree.h:111
const reco::ClusterHit3D * getClusterHit3D() const
Definition: kdTree.h:156
std::vector< KdTreeNode > KdTreeNodeVec
Definition: kdTree.h:66
float getTimeToExecute() const
Definition: kdTree.h:95
KdTreeNode & BuildKdTree(Hit3DVec::iterator, Hit3DVec::iterator, KdTreeNodeList &, int depth=0) const
Given an input set of ClusterHit3D objects, build a kd tree structure.
Definition: kdTree.cxx:112
const KdTreeNode & leftTree() const
Definition: kdTree.h:157
SplitAxis getSplitAxis() const
Definition: kdTree.h:154
const reco::ClusterHit3D * m_clusterHit3D
Definition: kdTree.h:164