lar_content::KDTreeLinkerAlgo< DATA, DIM > Class Template Reference

Class that implements the KDTree partition of 2D space and a closest point search algorithm. More...

#include "PreProcessingAlgorithm.h"

Public Member Functions
	KDTreeLinkerAlgo ()
	Default constructor. More...
	~KDTreeLinkerAlgo ()
	Destructor calls clear. More...
void	build (std::vector< KDTreeNodeInfoT< DATA, DIM >> &eltList, const KDTreeBoxT< DIM > &region)
	Build the KD tree from the "eltList" in the space define by "region". More...
void	search (const KDTreeBoxT< DIM > &searchBox, std::vector< KDTreeNodeInfoT< DATA, DIM >> &resRecHitList)
	Search in the KDTree for all points that would be contained in the given searchbox The founded points are stored in resRecHitList. More...
void	findNearestNeighbour (const KDTreeNodeInfoT< DATA, DIM > &point, const KDTreeNodeInfoT< DATA, DIM > *&result, float &distance)
	findNearestNeighbour More...
bool	empty ()
	Whether the tree is empty. More...
int	size ()
	Return the number of nodes + leaves in the tree (nElements should be (size() +1) / 2) More...
void	clear ()
	Clear all allocated structures. More...

Private Member Functions
KDTreeNodeT< DATA, DIM > *	getNextNode ()
	Get the next node from the node pool. More...
int	medianSearch (int low, int high, int treeDepth)
	Fast median search with Wirth algorithm in eltList between low and high indexes. More...
KDTreeNodeT< DATA, DIM > *	recBuild (int low, int high, int depth, const KDTreeBoxT< DIM > &region)
	Recursive kdtree builder. Is called by build() More...
void	recSearch (const KDTreeNodeT< DATA, DIM > *current, const KDTreeBoxT< DIM > &trackBox)
	Recursive kdtree search. Is called by search() More...
void	recNearestNeighbour (unsigned depth, const KDTreeNodeT< DATA, DIM > *current, const KDTreeNodeInfoT< DATA, DIM > &point, const KDTreeNodeT< DATA, DIM > *&best_match, float &best_dist)
	Recursive nearest neighbour search. Is called by findNearestNeighbour() More...
void	addSubtree (const KDTreeNodeT< DATA, DIM > *current)
	Add all elements of an subtree to the closest elements. Used during the recSearch(). More...
float	dist2 (const KDTreeNodeInfoT< DATA, DIM > &a, const KDTreeNodeInfoT< DATA, DIM > &b) const
	dist2 More...
void	clearTree ()
	Frees the KDTree. More...

Private Attributes
KDTreeNodeT< DATA, DIM > *	root_
	The KDTree root. More...
KDTreeNodeT< DATA, DIM > *	nodePool_
	Node pool allows us to do just 1 call to new for each tree building. More...
int	nodePoolSize_
	The node pool size. More...
int	nodePoolPos_
	The node pool position. More...
std::vector< KDTreeNodeInfoT< DATA, DIM > > *	closestNeighbour
	The closest neighbour. More...
std::vector< KDTreeNodeInfoT< DATA, DIM > > *	initialEltList
	The initial element list. More...

Detailed Description

template<typename DATA, unsigned DIM = 2>
class lar_content::KDTreeLinkerAlgo< DATA, DIM >

Class that implements the KDTree partition of 2D space and a closest point search algorithm.

Definition at line 17 of file PreProcessingAlgorithm.h.

Constructor & Destructor Documentation

template<typename DATA , unsigned DIM>

lar_content::KDTreeLinkerAlgo< DATA, DIM >::KDTreeLinkerAlgo ( )

inline

Default constructor.

Definition at line 162 of file KDTreeLinkerAlgoT.h.

                                                     :
    root_(nullptr),
    nodePool_(nullptr),
    nodePoolSize_(-1),
    nodePoolPos_(-1),
    closestNeighbour(nullptr),
    initialEltList(nullptr)
{
}

template<typename DATA , unsigned DIM>

lar_content::KDTreeLinkerAlgo< DATA, DIM >::~KDTreeLinkerAlgo ( )

inline

Destructor calls clear.

Definition at line 175 of file KDTreeLinkerAlgoT.h.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::clear().

{
    this->clear();
}

Member Function Documentation

template<typename DATA, unsigned DIM>

void lar_content::KDTreeLinkerAlgo< DATA, DIM >::addSubtree ( const KDTreeNodeT< DATA, DIM > *  current )

inlineprivate

Add all elements of an subtree to the closest elements. Used during the recSearch().

Parameters

current

Definition at line 421 of file KDTreeLinkerAlgoT.h.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::closestNeighbour, lar_content::KDTreeNodeT< DATA, DIM >::info, lar_content::KDTreeNodeT< DATA, DIM >::left, and lar_content::KDTreeNodeT< DATA, DIM >::right.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::recSearch().

{
    // By construction, current can't be null
    //assert(current != 0);

    if ((current->left == nullptr) && (current->right == nullptr))
    {
        // Leaf case
        closestNeighbour->push_back(current->info);
    }
    else
    {
        // Node case
        this->addSubtree(current->left);
        this->addSubtree(current->right);
    }
}

template<typename DATA, unsigned DIM>

void lar_content::KDTreeLinkerAlgo< DATA, DIM >::build ( std::vector< KDTreeNodeInfoT< DATA, DIM >> &  eltList, const KDTreeBoxT< DIM > &  region  )

inline

Build the KD tree from the "eltList" in the space define by "region".

Parameters

eltList
region

Definition at line 183 of file KDTreeLinkerAlgoT.h.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::initialEltList, lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePool_, lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePoolSize_, lar_content::KDTreeLinkerAlgo< DATA, DIM >::recBuild(), and lar_content::KDTreeLinkerAlgo< DATA, DIM >::root_.

Referenced by lar_content::EventSlicingTool::AssignRemainingHitsToSlices(), lar_content::DeltaRayMatchingContainers::BuildKDTree(), lar_content::IsolatedClusterMopUpAlgorithm::GetCaloHitToClusterMap(), lar_content::PreProcessingAlgorithm::GetFilteredCaloHitList(), lar_content::TransverseAssociationAlgorithm::GetNearbyClusterMap(), lar_content::VertexSelectionBaseAlgorithm::InitializeKDTrees(), lar_content::DeltaRayMatchingAlgorithm::InitializeNearbyClusterMap(), lar_content::TrainedVertexSelectionAlgorithm::PopulateKdTree(), and lar_content::CrossedTrackSplittingAlgorithm::PreparationStep().

{
    if (eltList.size())
    {
        initialEltList = &eltList;
        const size_t mysize = initialEltList->size();

        nodePoolSize_ = mysize * 2 - 1;
        nodePool_ = new KDTreeNodeT<DATA, DIM>[nodePoolSize_];

        // Here we build the KDTree
        root_ = this->recBuild(0, mysize, 0, region);
        initialEltList = nullptr;
    }
}

template<typename DATA , unsigned DIM>

void lar_content::KDTreeLinkerAlgo< DATA, DIM >::clear ( )

inline

Clear all allocated structures.

Definition at line 486 of file KDTreeLinkerAlgoT.h.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::clearTree(), and lar_content::KDTreeLinkerAlgo< DATA, DIM >::root_.

Referenced by lar_content::DeltaRayMatchingContainers::ClearContainers(), and lar_content::KDTreeLinkerAlgo< DATA, DIM >::~KDTreeLinkerAlgo().

{
    if (root_)
        this->clearTree();
}

template<typename DATA , unsigned DIM>

void lar_content::KDTreeLinkerAlgo< DATA, DIM >::clearTree ( )

inlineprivate

Frees the KDTree.

Definition at line 458 of file KDTreeLinkerAlgoT.h.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePool_, lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePoolPos_, lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePoolSize_, and lar_content::KDTreeLinkerAlgo< DATA, DIM >::root_.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::clear().

{
    delete[] nodePool_;
    nodePool_ = nullptr;
    root_ = nullptr;
    nodePoolSize_ = -1;
    nodePoolPos_ = -1;
}

template<typename DATA, unsigned DIM>

float lar_content::KDTreeLinkerAlgo< DATA, DIM >::dist2 ( const KDTreeNodeInfoT< DATA, DIM > &  a, const KDTreeNodeInfoT< DATA, DIM > &  b  ) const

inlineprivate

dist2

Parameters

a
b

Returns

dist2

Definition at line 442 of file KDTreeLinkerAlgoT.h.

References d, and lar_content::KDTreeNodeInfoT< DATA, DIM >::dims.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::recNearestNeighbour().

{
    double d = 0.;

    for (unsigned i = 0; i < DIM; ++i)
    {
        const double diff = a.dims[i] - b.dims[i];
        d += diff * diff;
    }

    return (float)d;
}

template<typename DATA , unsigned DIM>

bool lar_content::KDTreeLinkerAlgo< DATA, DIM >::empty ( )

inline

Whether the tree is empty.

Returns

boolean

Definition at line 470 of file KDTreeLinkerAlgoT.h.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePoolPos_.

Referenced by lar_content::VertexSelectionBaseAlgorithm::FilterVertexList(), and lar_content::VertexSelectionBaseAlgorithm::InitializeKDTrees().

{
    return (nodePoolPos_ == -1);
}

template<typename DATA, unsigned DIM>

void lar_content::KDTreeLinkerAlgo< DATA, DIM >::findNearestNeighbour ( const KDTreeNodeInfoT< DATA, DIM > &  point, const KDTreeNodeInfoT< DATA, DIM > *&  result, float &  distance  )

inline

findNearestNeighbour

Parameters

point
result
distance

Definition at line 334 of file KDTreeLinkerAlgoT.h.

References lar_content::KDTreeNodeT< DATA, DIM >::info, lar_content::KDTreeLinkerAlgo< DATA, DIM >::recNearestNeighbour(), and lar_content::KDTreeLinkerAlgo< DATA, DIM >::root_.

Referenced by lar_content::IsolatedClusterMopUpAlgorithm::GetCaloHitToClusterMap(), and lar_content::EventSlicingTool::MatchClusterToSlice().

{
    if (nullptr != result || distance != std::numeric_limits<float>::max())
    {
        result = nullptr;
        distance = std::numeric_limits<float>::max();
    }

    if (root_)
    {
        const KDTreeNodeT<DATA, DIM> *best_match = nullptr;
        this->recNearestNeighbour(0, root_, point, best_match, distance);

        if (distance != std::numeric_limits<float>::max())
        {
            result = &(best_match->info);
            distance = std::sqrt(distance);
        }
    }
}

template<typename DATA , unsigned DIM>

KDTreeNodeT< DATA, DIM > * lar_content::KDTreeLinkerAlgo< DATA, DIM >::getNextNode ( )

inlineprivate

Get the next node from the node pool.

Returns

the next node from the node pool

Definition at line 495 of file KDTreeLinkerAlgoT.h.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePool_, and lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePoolPos_.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::recBuild().

{
    ++nodePoolPos_;

    // The tree size is exactly 2 * nbrElts - 1 and this is the total allocated memory.
    // If we have used more than that....there is a big problem.
    //assert(nodePoolPos_ < nodePoolSize_);

    return &(nodePool_[nodePoolPos_]);
}

template<typename DATA , unsigned DIM>

int lar_content::KDTreeLinkerAlgo< DATA, DIM >::medianSearch ( int  low, int  high, int  treeDepth  )

inlineprivate

Fast median search with Wirth algorithm in eltList between low and high indexes.

Parameters

low
high
treeDepth

Definition at line 202 of file KDTreeLinkerAlgoT.h.

References lar_content::KDTreeNodeInfoT< DATA, DIM >::dims, and lar_content::KDTreeLinkerAlgo< DATA, DIM >::initialEltList.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::recBuild().

{
    // We should have at least 1 element to calculate the median...
    //assert(low < high);

    const int nbrElts = high - low;
    int median = nbrElts / 2 - (1 - 1 * (nbrElts & 1));
    median += low;

    int l = low;
    int m = high - 1;

    while (l < m)
    {
        KDTreeNodeInfoT<DATA, DIM> elt = (*initialEltList)[median];
        int i = l;
        int j = m;

        do
        {
            // The even depth is associated to dim1 dimension, the odd one to dim2 dimension
            const unsigned thedim = treeDepth % DIM;
            while ((*initialEltList)[i].dims[thedim] < elt.dims[thedim])
                ++i;
            while ((*initialEltList)[j].dims[thedim] > elt.dims[thedim])
                --j;

            if (i <= j)
            {
                std::swap((*initialEltList)[i], (*initialEltList)[j]);
                i++;
                j--;
            }
        } while (i <= j);

        if (j < median)
            l = i;
        if (i > median)
            m = j;
    }

    return median;
}

template<typename DATA , unsigned DIM>

KDTreeNodeT< DATA, DIM > * lar_content::KDTreeLinkerAlgo< DATA, DIM >::recBuild ( int  low, int  high, int  depth, const KDTreeBoxT< DIM > &  region  )

inlineprivate

Recursive kdtree builder. Is called by build()

Parameters

low
high
depth
region

Definition at line 509 of file KDTreeLinkerAlgoT.h.

References lar_content::KDTreeBoxT< DIM >::dimmax, lar_content::KDTreeBoxT< DIM >::dimmin, lar_content::KDTreeLinkerAlgo< DATA, DIM >::getNextNode(), lar_content::KDTreeNodeT< DATA, DIM >::info, lar_content::KDTreeLinkerAlgo< DATA, DIM >::initialEltList, lar_content::KDTreeNodeT< DATA, DIM >::left, lar_content::KDTreeLinkerAlgo< DATA, DIM >::medianSearch(), lar_content::KDTreeNodeT< DATA, DIM >::right, and lar_content::KDTreeNodeT< DATA, DIM >::setAttributs().

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::build().

{
    const int portionSize = high - low;

    // By construction, portionSize > 0 can't happen.
    //assert(portionSize > 0);

    if (portionSize == 1)
    {
        // Leaf case
        KDTreeNodeT<DATA, DIM> *leaf = this->getNextNode();
        leaf->setAttributs(region, (*initialEltList)[low]);
        return leaf;
    }
    else
    {
        // The even depth is associated to dim1 dimension, the odd one to dim2 dimension
        int medianId = this->medianSearch(low, high, depth);

        // We create the node
        KDTreeNodeT<DATA, DIM> *node = this->getNextNode();
        node->setAttributs(region);
        node->info = (*initialEltList)[medianId];

        // Here we split into 2 halfplanes the current plane
        KDTreeBoxT<DIM> leftRegion = region;
        KDTreeBoxT<DIM> rightRegion = region;

        const unsigned thedim = depth % DIM;
        auto medianVal = (*initialEltList)[medianId].dims[thedim];
        leftRegion.dimmax[thedim] = medianVal;
        rightRegion.dimmin[thedim] = medianVal;

        ++depth;
        ++medianId;

        // We recursively build the son nodes
        node->left = this->recBuild(low, medianId, depth, leftRegion);
        node->right = this->recBuild(medianId, high, depth, rightRegion);
        return node;
    }
}

template<typename DATA, unsigned DIM = 2>

void lar_content::KDTreeLinkerAlgo< DATA, DIM >::recNearestNeighbour ( unsigned  depth, const KDTreeNodeT< DATA, DIM > *  current, const KDTreeNodeInfoT< DATA, DIM > &  point, const KDTreeNodeT< DATA, DIM > *&  best_match, float &  best_dist  )

inlineprivate

Recursive nearest neighbour search. Is called by findNearestNeighbour()

Parameters

depth
current
point
best_match
best_dist

Definition at line 359 of file KDTreeLinkerAlgoT.h.

References lar_content::KDTreeNodeInfoT< DATA, DIM >::dims, lar_content::KDTreeLinkerAlgo< DATA, DIM >::dist2(), f, lar_content::KDTreeNodeT< DATA, DIM >::info, lar_content::KDTreeNodeT< DATA, DIM >::left, and lar_content::KDTreeNodeT< DATA, DIM >::right.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::findNearestNeighbour().

{
    const unsigned int current_dim = depth % DIM;

    if (current->left == nullptr && current->right == nullptr)
    {
        best_match = current;
        best_dist = this->dist2(point, best_match->info);
        return;
    }
    else
    {
        const float dist_to_axis = point.dims[current_dim] - current->info.dims[current_dim];

        if (dist_to_axis < 0.f)
        {
            this->recNearestNeighbour(depth + 1, current->left, point, best_match, best_dist);
        }
        else
        {
            this->recNearestNeighbour(depth + 1, current->right, point, best_match, best_dist);
        }

        // If we're here we're returned so best_dist is filled. Compare to this node and see if it's a better match. If it is, update result
        const float dist_current = this->dist2(point, current->info);

        if (dist_current < best_dist)
        {
            best_dist = dist_current;
            best_match = current;
        }

        // Now we see if the radius to best crosses the splitting axis
        if (best_dist > dist_to_axis * dist_to_axis)
        {
            // if it does we traverse the other side of the axis to check for a new best
            const KDTreeNodeT<DATA, DIM> *check_best = best_match;
            float check_dist = best_dist;

            if (dist_to_axis < 0.f)
            {
                this->recNearestNeighbour(depth + 1, current->right, point, check_best, check_dist);
            }
            else
            {
                this->recNearestNeighbour(depth + 1, current->left, point, check_best, check_dist);
            }

            if (check_dist < best_dist)
            {
                best_dist = check_dist;
                best_match = check_best;
            }
        }
        return;
    }
}

template<typename DATA, unsigned DIM>

void lar_content::KDTreeLinkerAlgo< DATA, DIM >::recSearch ( const KDTreeNodeT< DATA, DIM > *  current, const KDTreeBoxT< DIM > &  trackBox  )

inlineprivate

Recursive kdtree search. Is called by search()

Parameters

current
trackBox

Definition at line 262 of file KDTreeLinkerAlgoT.h.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::addSubtree(), lar_content::KDTreeLinkerAlgo< DATA, DIM >::closestNeighbour, lar_content::KDTreeBoxT< DIM >::dimmax, lar_content::KDTreeBoxT< DIM >::dimmin, lar_content::KDTreeNodeT< DATA, DIM >::info, lar_content::KDTreeNodeT< DATA, DIM >::left, and lar_content::KDTreeNodeT< DATA, DIM >::right.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::search().

{
    // By construction, current can't be null
    //assert(current != 0);
    // By Construction, a node can't have just 1 son.
    //assert (!(((current->left == 0) && (current->right != 0)) || ((current->left != 0) && (current->right == 0))));

    if ((current->left == nullptr) && (current->right == nullptr))
    {
        // Leaf case
        // If point inside the rectangle/area
        bool isInside = true;

        for (unsigned i = 0; i < DIM; ++i)
        {
            const auto thedim = current->info.dims[i];
            isInside = isInside && thedim >= trackBox.dimmin[i] && thedim <= trackBox.dimmax[i];
        }

        if (isInside)
            closestNeighbour->push_back(current->info);
    }
    else
    {
        // Node case
        // If region( v->left ) is fully contained in the rectangle
        bool isFullyContained = true;
        bool hasIntersection = true;

        for (unsigned i = 0; i < DIM; ++i)
        {
            const auto regionmin = current->left->region.dimmin[i];
            const auto regionmax = current->left->region.dimmax[i];
            isFullyContained = isFullyContained && (regionmin >= trackBox.dimmin[i] && regionmax <= trackBox.dimmax[i]);
            hasIntersection = hasIntersection && (regionmin < trackBox.dimmax[i] && regionmax > trackBox.dimmin[i]);
        }

        if (isFullyContained)
        {
            this->addSubtree(current->left);
        }
        else if (hasIntersection)
        {
            this->recSearch(current->left, trackBox);
        }

        //if region( v->right ) is fully contained in the rectangle
        isFullyContained = true;
        hasIntersection = true;

        for (unsigned i = 0; i < DIM; ++i)
        {
            const auto regionmin = current->right->region.dimmin[i];
            const auto regionmax = current->right->region.dimmax[i];
            isFullyContained = isFullyContained && (regionmin >= trackBox.dimmin[i] && regionmax <= trackBox.dimmax[i]);
            hasIntersection = hasIntersection && (regionmin < trackBox.dimmax[i] && regionmax > trackBox.dimmin[i]);
        }

        if (isFullyContained)
        {
            this->addSubtree(current->right);
        }
        else if (hasIntersection)
        {
            this->recSearch(current->right, trackBox);
        }
    }
}

template<typename DATA, unsigned DIM>

void lar_content::KDTreeLinkerAlgo< DATA, DIM >::search ( const KDTreeBoxT< DIM > &  searchBox, std::vector< KDTreeNodeInfoT< DATA, DIM >> &  resRecHitList  )

inline

Search in the KDTree for all points that would be contained in the given searchbox The founded points are stored in resRecHitList.

Parameters

searchBox
resRecHitList

Definition at line 249 of file KDTreeLinkerAlgoT.h.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::closestNeighbour, lar_content::KDTreeLinkerAlgo< DATA, DIM >::recSearch(), and lar_content::KDTreeLinkerAlgo< DATA, DIM >::root_.

Referenced by lar_content::DeltaRayMatchingContainers::AddToClusterProximityMap(), lar_content::RPhiFeatureTool::FillKernelEstimate(), lar_content::PreProcessingAlgorithm::GetFilteredCaloHitList(), lar_content::TransverseAssociationAlgorithm::GetNearbyClusterMap(), lar_content::TrainedVertexSelectionAlgorithm::IncrementSharedAxisValues(), lar_content::DeltaRayMatchingAlgorithm::InitializeNearbyClusterMap(), lar_content::VertexSelectionBaseAlgorithm::IsVertexOnHit(), lar_content::TrainedVertexSelectionAlgorithm::PopulateKdTree(), lar_content::CrossedTrackSplittingAlgorithm::PreparationStep(), and lar_content::VertexSelectionBaseAlgorithm::VertexHitEnergy().

{
    if (root_)
    {
        closestNeighbour = &recHits;
        this->recSearch(root_, trackBox);
        closestNeighbour = nullptr;
    }
}

template<typename DATA , unsigned DIM>

int lar_content::KDTreeLinkerAlgo< DATA, DIM >::size ( )

inline

Return the number of nodes + leaves in the tree (nElements should be (size() +1) / 2)

Returns

the number of nodes + leaves in the tree

Definition at line 478 of file KDTreeLinkerAlgoT.h.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePoolPos_.

{
    return (nodePoolPos_ + 1);
}

Member Data Documentation

template<typename DATA, unsigned DIM = 2>

std::vector<KDTreeNodeInfoT<DATA, DIM> >* lar_content::KDTreeLinkerAlgo< DATA, DIM >::closestNeighbour

private

The closest neighbour.

Definition at line 154 of file KDTreeLinkerAlgoT.h.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::addSubtree(), lar_content::KDTreeLinkerAlgo< DATA, DIM >::recSearch(), and lar_content::KDTreeLinkerAlgo< DATA, DIM >::search().

template<typename DATA, unsigned DIM = 2>

std::vector<KDTreeNodeInfoT<DATA, DIM> >* lar_content::KDTreeLinkerAlgo< DATA, DIM >::initialEltList

private

The initial element list.

Definition at line 155 of file KDTreeLinkerAlgoT.h.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::build(), lar_content::KDTreeLinkerAlgo< DATA, DIM >::medianSearch(), and lar_content::KDTreeLinkerAlgo< DATA, DIM >::recBuild().

template<typename DATA, unsigned DIM = 2>

KDTreeNodeT<DATA, DIM>* lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePool_

private

Node pool allows us to do just 1 call to new for each tree building.

Definition at line 150 of file KDTreeLinkerAlgoT.h.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::build(), lar_content::KDTreeLinkerAlgo< DATA, DIM >::clearTree(), and lar_content::KDTreeLinkerAlgo< DATA, DIM >::getNextNode().

template<typename DATA, unsigned DIM = 2>

int lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePoolPos_

private

The node pool position.

Definition at line 152 of file KDTreeLinkerAlgoT.h.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::clearTree(), lar_content::KDTreeLinkerAlgo< DATA, DIM >::empty(), lar_content::KDTreeLinkerAlgo< DATA, DIM >::getNextNode(), and lar_content::KDTreeLinkerAlgo< DATA, DIM >::size().

template<typename DATA, unsigned DIM = 2>

int lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePoolSize_

private

The node pool size.

Definition at line 151 of file KDTreeLinkerAlgoT.h.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::build(), and lar_content::KDTreeLinkerAlgo< DATA, DIM >::clearTree().

template<typename DATA, unsigned DIM = 2>

KDTreeNodeT<DATA, DIM>* lar_content::KDTreeLinkerAlgo< DATA, DIM >::root_

private

The KDTree root.

Definition at line 149 of file KDTreeLinkerAlgoT.h.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::build(), lar_content::KDTreeLinkerAlgo< DATA, DIM >::clear(), lar_content::KDTreeLinkerAlgo< DATA, DIM >::clearTree(), lar_content::KDTreeLinkerAlgo< DATA, DIM >::findNearestNeighbour(), and lar_content::KDTreeLinkerAlgo< DATA, DIM >::search().

---

The documentation for this class was generated from the following files:

• larpandoracontent/v04_08_01/source/larpandoracontent/LArControlFlow/PreProcessingAlgorithm.h
• larpandoracontent/v04_08_01/source/larpandoracontent/LArUtility/KDTreeLinkerAlgoT.h