kdTree.h

Go to the documentation of this file.

#ifndef kdTree_h
#define kdTree_h

// Framework Includes
#include "fhiclcpp/ParameterSet.h"

// Algorithm includes
#include "larreco/RecoAlg/Cluster3DAlgs/Cluster3D.h"

// std includes
#include <vector>
#include <list>
#include <set>
#include <map>
//------------------------------------------------------------------------------------------------------------------------------------------

namespace lar_cluster3d
{
class kdTree
{
public:
    kdTree(fhicl::ParameterSet const &pset);

    virtual ~kdTree();

    void configure(fhicl::ParameterSet const &pset);
    
    class KdTreeNode;
    
    using KdTreeNodeVec  = std::vector<KdTreeNode>;
    using KdTreeNodeList = std::list<KdTreeNode>;
    using Hit3DVec       = std::vector<const reco::ClusterHit3D*>;
    
    KdTreeNode& BuildKdTree(Hit3DVec::iterator, Hit3DVec::iterator, KdTreeNodeList&, int depth=0) const;
    
    using CandPair     = std::pair<double,const reco::ClusterHit3D*>;
    using CandPairList = std::list<CandPair>;
    
    size_t FindNearestNeighbors(const reco::ClusterHit3D*, const KdTreeNode&, CandPairList&, float&) const;
    bool   FindEntry(const reco::ClusterHit3D*, const KdTreeNode&, CandPairList&, float&, bool&, int) const;
    bool   FindEntryBrute(const reco::ClusterHit3D*, const KdTreeNode&, int) const;
    
    KdTreeNode BuildKdTree(const reco::HitPairList&, KdTreeNodeList&) const;
    
    KdTreeNode BuildKdTree(const reco::HitPairListPtr&, KdTreeNodeList&) const;

    float getTimeToExecute() const {return m_timeToBuild;}
    
private:
    
    bool consistentPairs(const reco::ClusterHit3D* pair1, const reco::ClusterHit3D* pair2, float& hitSeparation) const;
    
    float DistanceBetweenNodes(const reco::ClusterHit3D*,const reco::ClusterHit3D*) const;
    
    bool           m_enableMonitoring;      
    mutable float  m_timeToBuild;           
    float          m_pairSigmaPeakTime;     
    float          m_refLeafBestDist;       

};
    
class kdTree::KdTreeNode
{
public:
    enum SplitAxis { xPlane,
        yPlane,
        zPlane,
        leaf,
        null
    };
    
    KdTreeNode(SplitAxis axis, float axisVal, const KdTreeNode& left, const KdTreeNode& right) :
    m_splitAxis(axis),
    m_axisValue(axisVal),
    m_clusterHit3D(0),
    m_leftTree(left),
    m_rightTree(right)
    {}
    
    KdTreeNode(const reco::ClusterHit3D* hit) :
    m_splitAxis(SplitAxis::leaf),
    m_axisValue(0.),
    m_clusterHit3D(hit),
    m_leftTree(*this),
    m_rightTree(*this)
    {}
    
    KdTreeNode() : m_splitAxis(SplitAxis::null),
    m_axisValue(0.),
    m_clusterHit3D(0),
    m_leftTree(*this),
    m_rightTree(*this)
    {}
    
    bool                      isLeafNode()      const {return m_splitAxis == SplitAxis::leaf;}
    bool                      isNullNode()      const {return m_splitAxis == SplitAxis::null;}
    
    SplitAxis                 getSplitAxis()    const {return m_splitAxis;}
    float                     getAxisValue()    const {return m_axisValue;}
    const reco::ClusterHit3D* getClusterHit3D() const {return m_clusterHit3D;}
    const KdTreeNode&         leftTree()        const {return m_leftTree;}
    const KdTreeNode&         rightTree()       const {return m_rightTree;}
    
private:
    
    SplitAxis                 m_splitAxis;
    float                     m_axisValue;
    const reco::ClusterHit3D* m_clusterHit3D;
    const KdTreeNode&         m_leftTree;
    const KdTreeNode&         m_rightTree;
};
    
} // namespace lar_cluster3d
#endif