A fast hough algorithm with rectangular boxes, which are split linearly by a fixed number of divisions in each coordinate up to a maximal level. More...

#include <BoxDivisionHoughTree.h>

Inheritance diagram for BoxDivisionHoughTree< AItemPtr, AHoughBox, divisions >:

Public Types
using	HoughBox = AHoughBox
	Type of the box in the hough space.

using	BoxDivision = SectoredLinearDivision<HoughBox, divisions...>
	Type of the box division strategy.

using	HoughTree = WeightedFastHoughTree<AItemPtr, HoughBox, BoxDivision>
	Type of the fast hough tree structure.

template<size_t I>
using	Type = typename HoughBox::template Type<I>
	Type of the coordinate I.

template<class T>
using	HasType = typename HoughBox::template HasType<T>
	Predicate that the given type is indeed a coordinate of the hough space.

template<class T>
using	TypeIndex = typename HoughBox::template TypeIndex<T>
	Function to get the coordinate index from its type.

template<size_t I>
using	Width = typename HoughBox::template Width<I>
	Type of the width in coordinate I.

using	Node = typename HoughTree::Node
	Type of the nodes used in the tree for the search.

Public Member Functions
	BoxDivisionHoughTree (int maxLevel, int sectorLevelSkip=0)
	Constructor using the given maximal level.

size_t	getDivision (size_t i) const
	Getter the number of divisions at each level for coordinate index I.

template<size_t I>
void	constructArray (double lowerBound, double upperBound, Width< I > nBinOverlap=0, Width< I > nBinWidth=0)
	Construct the discrete value array at coordinate index I.

template<size_t I>
void	assignArray (Array< I > array, Width< I > overlap=0)
	Provide an externally constructed array by coordinate index.

template<class T>
std::enable_if_t< HasType< T >::value, void >	assignArray (Array< TypeIndex< T >::value > array, Width< TypeIndex< T >::value > overlap=0)
	Provide an externally constructed array by coordinate type.

void	initialize ()
	Initialise the algorithm by constructing the hough tree from the parameters.

template<class AItemPtrs>
void	seed (const AItemPtrs &items)
	Prepare the leave finding by filling the top node with given hits.

void	fell ()
	Terminates the processing by striping all hit information from the tree.

void	raze ()
	Release all memory that the tree acquired during the runs.

HoughTree *	getTree () const
	Getter for the tree used in the search in the hough plane.

int	getMaxLevel () const
	Getter for the currently set maximal level.

void	setMaxLevel (int maxLevel)
	Setter maximal level of the hough tree.

int	getSectorLevelSkip () const
	Getter for number of levels to skip in first level to form a finer sectored hough space.

void	setSectorLevelSkip (int sectorLevelSkip)
	Setter for number of levels to skip in first level to form a finer sectored hough space.

template<size_t I>
const Array< I > &	getArray () const
	Getter for the array of discrete value for coordinate I.

Private Types
template<size_t I>
using	Array = typename Type<I>::Array
	Type of the discrete value array to coordinate index I.

using	Arrays = TrackingUtilities::TupleGenerateN<Array, sizeof...(divisions)>
	Tuple type of the discrete value arrays.

Private Member Functions
template<size_t... Is>
HoughBox	constructHoughPlaneImpl (const std::index_sequence< Is... > &is)
	Construct the box of the top node of the tree. Implementation unroling the indices.

HoughBox	constructHoughPlane ()
	Construct the box of the top node of the tree.

Private Attributes
const std::array< size_t, sizeof ...(divisions)>	m_divisions = {{divisions ...}}
	Array of the number of divisions at each level.

std::unique_ptr< HoughTree >	m_houghTree = nullptr
	Dynamic hough tree structure traversed in the leaf search.

int	m_maxLevel
	Number of the maximum tree level.

int	m_sectorLevelSkip
	Number of levels to skip in first level to form a finer sectored hough space.

HoughBox::Delta	m_overlaps
	An tuple of division overlaps in each coordinate.

Arrays	m_arrays
	A tuple of value arrays providing the memory for the discrete bin bounds.

Detailed Description

template<class AItemPtr, class AHoughBox, size_t ... divisions>
class Belle2::TrackFindingCDC::BoxDivisionHoughTree< AItemPtr, AHoughBox, divisions >

A fast hough algorithm with rectangular boxes, which are split linearly by a fixed number of divisions in each coordinate up to a maximal level.

Definition at line 34 of file BoxDivisionHoughTree.h.

Member Typedef Documentation

◆ Array

template<class AItemPtr, class AHoughBox, size_t ... divisions>

template<size_t I>

using Array = typename Type<I>::Array

private

Type of the discrete value array to coordinate index I.

Definition at line 78 of file BoxDivisionHoughTree.h.

◆ Arrays

template<class AItemPtr, class AHoughBox, size_t ... divisions>

using Arrays = TrackingUtilities::TupleGenerateN<Array, sizeof...(divisions)>

private

Tuple type of the discrete value arrays.

Definition at line 81 of file BoxDivisionHoughTree.h.

◆ BoxDivision

template<class AItemPtr, class AHoughBox, size_t ... divisions>

using BoxDivision = SectoredLinearDivision<HoughBox, divisions...>

Type of the box division strategy.

Definition at line 41 of file BoxDivisionHoughTree.h.

◆ HasType

template<class AItemPtr, class AHoughBox, size_t ... divisions>

template<class T>

using HasType = typename HoughBox::template HasType<T>

Predicate that the given type is indeed a coordinate of the hough space.

Definition at line 52 of file BoxDivisionHoughTree.h.

◆ HoughBox

template<class AItemPtr, class AHoughBox, size_t ... divisions>

using HoughBox = AHoughBox

Type of the box in the hough space.

Definition at line 38 of file BoxDivisionHoughTree.h.

◆ HoughTree

template<class AItemPtr, class AHoughBox, size_t ... divisions>

using HoughTree = WeightedFastHoughTree<AItemPtr, HoughBox, BoxDivision>

Type of the fast hough tree structure.

Definition at line 44 of file BoxDivisionHoughTree.h.

◆ Node

template<class AItemPtr, class AHoughBox, size_t ... divisions>

using Node = typename HoughTree::Node

Type of the nodes used in the tree for the search.

Definition at line 63 of file BoxDivisionHoughTree.h.

◆ Type

template<class AItemPtr, class AHoughBox, size_t ... divisions>

template<size_t I>

using Type = typename HoughBox::template Type<I>

Type of the coordinate I.

Definition at line 48 of file BoxDivisionHoughTree.h.

◆ TypeIndex

template<class AItemPtr, class AHoughBox, size_t ... divisions>

template<class T>

using TypeIndex = typename HoughBox::template TypeIndex<T>

Function to get the coordinate index from its type.

Definition at line 56 of file BoxDivisionHoughTree.h.

◆ Width

template<class AItemPtr, class AHoughBox, size_t ... divisions>

template<size_t I>

using Width = typename HoughBox::template Width<I>

Type of the width in coordinate I.

Definition at line 60 of file BoxDivisionHoughTree.h.

Constructor & Destructor Documentation

◆ BoxDivisionHoughTree()

template<class AItemPtr, class AHoughBox, size_t ... divisions>

BoxDivisionHoughTree	(	int	maxLevel,
		int	sectorLevelSkip = 0 )

inlineexplicit

Constructor using the given maximal level.

Definition at line 67 of file BoxDivisionHoughTree.h.

        : m_maxLevel(maxLevel)
        , m_sectorLevelSkip(sectorLevelSkip)
          // cppcheck-suppress nullPointer ; false positive on the variadic pack expansion
        , m_overlaps((divisions * 0)...)
      {
      }

Member Function Documentation

◆ assignArray() [1/2]

template<class AItemPtr, class AHoughBox, size_t ... divisions>

template<size_t I>

void assignArray	(	Array< I >	array,
		Width< I >	overlap = 0 )

inline

Provide an externally constructed array by coordinate index.

Definition at line 129 of file BoxDivisionHoughTree.h.

      {
        std::get<I>(m_arrays) = std::move(array);
        std::get<I>(m_overlaps) = overlap;
 
        // In case of a discrete axes, check whether the size of the array is sensible
        // such that the bin width at the highest granularity level is a whole number given the overlap.
        if (std::is_integral<Width<I> >::value) {
          const int division = getDivision(I);
          const int granularityLevel = m_maxLevel + m_sectorLevelSkip;
          const long int nBins = std::pow(division, granularityLevel);
          const long int nPositions = std::get<I>(m_arrays).size();
          const long int nWidthTimeNBins = nPositions - 1 + (nBins - 1) * overlap;
 
          B2ASSERT("Not enough positions in array to cover all bins.\n"
                   "Expected: positions = " << nBins - (nBins - 1) * overlap + 1 << " at least.\n"
                   "Actual:   positions = " << nPositions << " (overlap = " << overlap << ", bins = " << nBins << ")\n",
                   nWidthTimeNBins >= nBins);
 
          B2ASSERT("Number of positions in array introduces inhomogeneous width at the highest granularity level.\n"
                   "Expected: positions = 'width * bins - (bins - 1) * overlap + 1'\n"
                   "Actual:   positions = " << nPositions << " (overlap = " << overlap << ", bins = " << nBins << ")\n",
                   nWidthTimeNBins % nBins == 0);
        }
      }

◆ assignArray() [2/2]

template<class AItemPtr, class AHoughBox, size_t ... divisions>

template<class T>

std::enable_if_t< HasType< T >::value, void > assignArray	(	Array< TypeIndex< T >::value >	array,
		Width< TypeIndex< T >::value >	overlap = 0 )

inline

Provide an externally constructed array by coordinate type.

Definition at line 158 of file BoxDivisionHoughTree.h.

      {
        assignArray<TypeIndex<T>::value>(std::move(array), overlap);
      }

◆ constructArray()

template<class AItemPtr, class AHoughBox, size_t ... divisions>

template<size_t I>

void constructArray	(	double	lowerBound,
		double	upperBound,
		Width< I >	nBinOverlap = 0,
		Width< I >	nBinWidth = 0 )

inline

Construct the discrete value array at coordinate index I.

This function is only applicable for discrete axes. For continuous axes assignArray should be call with an array containing only the lower and upper bound of the axes range and an optional overlap.

Parameters

lowerBound	Lower bound of the value range
upperBound	Upper bound of the value range
nBinOverlap	Overlap of neighboring bins. Default is no overlap. Usually this is counted in number of discrete values
nBinWidth	Width of the bins at lowest level. Default is width of 1. Usually this is counted in numbers of discrete values

Definition at line 105 of file BoxDivisionHoughTree.h.

      {
        static_assert(std::is_integral<Width<I> >::value, "Method only applicable to discrete axes");
        const size_t division = getDivision(I);
        const int granularityLevel = m_maxLevel + m_sectorLevelSkip;
        const size_t nBins = std::pow(division, granularityLevel);
 
        if (nBinWidth == 0) {
          nBinWidth = nBinOverlap + 1;
        }
 
        B2ASSERT("Width " << nBinWidth << "is not bigger than overlap " << nBinOverlap,
                 nBinOverlap < nBinWidth);
 
        const auto nPositions = (nBinWidth - nBinOverlap) * nBins + nBinOverlap + 1;
        std::get<I>(m_arrays) = TrackingUtilities::linspace<float>(lowerBound, upperBound, nPositions);
        std::get<I>(m_overlaps) = nBinOverlap;
      }

◆ constructHoughPlane()

template<class AItemPtr, class AHoughBox, size_t ... divisions>

HoughBox constructHoughPlane ( )

inlineprivate

Construct the box of the top node of the tree.

Definition at line 246 of file BoxDivisionHoughTree.h.

      {
        return constructHoughPlaneImpl(std::make_index_sequence<sizeof...(divisions)>());
      }

◆ constructHoughPlaneImpl()

template<class AItemPtr, class AHoughBox, size_t ... divisions>

template<size_t... Is>

HoughBox constructHoughPlaneImpl ( const std::index_sequence< Is... > & is )

inlineprivate

Construct the box of the top node of the tree. Implementation unroling the indices.

Definition at line 240 of file BoxDivisionHoughTree.h.

      {
        return HoughBox(Type<Is>::getRange(std::get<Is>(m_arrays))...);
      }

◆ fell()

template<class AItemPtr, class AHoughBox, size_t ... divisions>

void fell ( )

inline

Terminates the processing by striping all hit information from the tree.

Definition at line 182 of file BoxDivisionHoughTree.h.

      {
        HoughTree* const tree = this->m_houghTree.get();
        if (tree != nullptr) {
          tree->fell();
        }
      }

◆ getArray()

template<class AItemPtr, class AHoughBox, size_t ... divisions>

template<size_t I>

const Array< I > & getArray ( ) const

inline

Getter for the array of discrete value for coordinate I.

Definition at line 232 of file BoxDivisionHoughTree.h.

      {
        return std::get<I>(m_arrays);
      }

◆ getDivision()

template<class AItemPtr, class AHoughBox, size_t ... divisions>

size_t getDivision ( size_t i ) const

inline

Getter the number of divisions at each level for coordinate index I.

Definition at line 85 of file BoxDivisionHoughTree.h.

      {
        return m_divisions[i];
      }

◆ getMaxLevel()

template<class AItemPtr, class AHoughBox, size_t ... divisions>

int getMaxLevel ( ) const

inline

Getter for the currently set maximal level.

Definition at line 207 of file BoxDivisionHoughTree.h.

      {
        return m_maxLevel;
      }

◆ getSectorLevelSkip()

template<class AItemPtr, class AHoughBox, size_t ... divisions>

int getSectorLevelSkip ( ) const

inline

Getter for number of levels to skip in first level to form a finer sectored hough space.

Definition at line 219 of file BoxDivisionHoughTree.h.

      {
        return m_sectorLevelSkip;
      }

◆ getTree()

template<class AItemPtr, class AHoughBox, size_t ... divisions>

HoughTree * getTree ( ) const

inline

Getter for the tree used in the search in the hough plane.

Definition at line 201 of file BoxDivisionHoughTree.h.

      {
        return m_houghTree.get();
      }

◆ initialize()

template<class AItemPtr, class AHoughBox, size_t ... divisions>

void initialize ( )

inline

Initialise the algorithm by constructing the hough tree from the parameters.

Definition at line 165 of file BoxDivisionHoughTree.h.

      {
        // Compose the hough space
        HoughBox houghPlane = constructHoughPlane();
        BoxDivision boxDivision(m_overlaps, m_sectorLevelSkip);
        m_houghTree.reset(new HoughTree(std::move(houghPlane), std::move(boxDivision)));
      }

◆ raze()

template<class AItemPtr, class AHoughBox, size_t ... divisions>

void raze ( )

inline

Release all memory that the tree acquired during the runs.

Definition at line 191 of file BoxDivisionHoughTree.h.

      {
        HoughTree* const tree = this->m_houghTree.get();
        if (tree != nullptr) {
          tree->raze();
        }
      }

◆ seed()

template<class AItemPtr, class AHoughBox, size_t ... divisions>

template<class AItemPtrs>

void seed ( const AItemPtrs & items )

inline

Prepare the leave finding by filling the top node with given hits.

Definition at line 175 of file BoxDivisionHoughTree.h.

      {
        if (not m_houghTree) initialize();
        m_houghTree->seed(items);
      }

◆ setMaxLevel()

template<class AItemPtr, class AHoughBox, size_t ... divisions>

void setMaxLevel ( int maxLevel )

inline

Setter maximal level of the hough tree.

Definition at line 213 of file BoxDivisionHoughTree.h.

      {
        m_maxLevel = maxLevel;
      }

◆ setSectorLevelSkip()

template<class AItemPtr, class AHoughBox, size_t ... divisions>

void setSectorLevelSkip ( int sectorLevelSkip )

inline

Setter for number of levels to skip in first level to form a finer sectored hough space.

Definition at line 225 of file BoxDivisionHoughTree.h.

      {
        m_sectorLevelSkip = sectorLevelSkip;
      }

Member Data Documentation

◆ m_arrays

template<class AItemPtr, class AHoughBox, size_t ... divisions>

Arrays m_arrays

private

A tuple of value arrays providing the memory for the discrete bin bounds.

Definition at line 268 of file BoxDivisionHoughTree.h.

◆ m_divisions

template<class AItemPtr, class AHoughBox, size_t ... divisions>

const std::array<size_t, sizeof ...(divisions)> m_divisions = {{divisions ...}}

private

Array of the number of divisions at each level.

Definition at line 253 of file BoxDivisionHoughTree.h.

253{{divisions ...}};

◆ m_houghTree

template<class AItemPtr, class AHoughBox, size_t ... divisions>

std::unique_ptr<HoughTree> m_houghTree = nullptr

private

Dynamic hough tree structure traversed in the leaf search.

Definition at line 256 of file BoxDivisionHoughTree.h.

◆ m_maxLevel

template<class AItemPtr, class AHoughBox, size_t ... divisions>

int m_maxLevel

private

Number of the maximum tree level.

Definition at line 259 of file BoxDivisionHoughTree.h.

◆ m_overlaps

template<class AItemPtr, class AHoughBox, size_t ... divisions>

HoughBox::Delta m_overlaps

private

An tuple of division overlaps in each coordinate.

Definition at line 265 of file BoxDivisionHoughTree.h.

◆ m_sectorLevelSkip

template<class AItemPtr, class AHoughBox, size_t ... divisions>

int m_sectorLevelSkip

private

Number of levels to skip in first level to form a finer sectored hough space.

Definition at line 262 of file BoxDivisionHoughTree.h.

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

tracking/trackFindingCDC/hough/trees/include/BoxDivisionHoughTree.h

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Array

◆ Arrays

◆ BoxDivision

◆ HasType

◆ HoughBox

◆ HoughTree

◆ Node

◆ Type

◆ TypeIndex

◆ Width

Constructor & Destructor Documentation

◆ BoxDivisionHoughTree()

Member Function Documentation

◆ assignArray() [1/2]

◆ assignArray() [2/2]

◆ constructArray()

◆ constructHoughPlane()

◆ constructHoughPlaneImpl()

◆ fell()

◆ getArray()

◆ getDivision()

◆ getMaxLevel()

◆ getSectorLevelSkip()

◆ getTree()

◆ initialize()

◆ raze()

◆ seed()

◆ setMaxLevel()

◆ setSectorLevelSkip()

Member Data Documentation

◆ m_arrays

◆ m_divisions

◆ m_houghTree

◆ m_maxLevel

◆ m_overlaps

◆ m_sectorLevelSkip