Belle II Software  release-05-02-19
BoxDivisionHoughTree.h
1 /**************************************************************************
2  * BASF2 (Belle Analysis Framework 2) *
3  * Copyright(C) 2015 - Belle II Collaboration *
4  * *
5  * Author: The Belle II Collaboration *
6  * Contributors: Oliver Frost *
7  * *
8  * This software is provided "as is" without any warranty. *
9  **************************************************************************/
10 #pragma once
11 #include <tracking/trackFindingCDC/hough/trees/WeightedFastHoughTree.h>
12 #include <tracking/trackFindingCDC/hough/baseelements/SectoredLinearDivision.h>
13 
14 #include <tracking/trackFindingCDC/numerics/LookupTable.h>
15 
16 #include <tracking/trackFindingCDC/utilities/TupleGenerate.h>
17 
18 #include <type_traits>
19 #include <utility>
20 #include <tuple>
21 #include <array>
22 #include <memory>
23 
24 namespace Belle2 {
29  namespace TrackFindingCDC {
30 
35  template <class AItemPtr, class AHoughBox, size_t ... divisions>
36  class BoxDivisionHoughTree {
37 
38  public:
40  using HoughBox = AHoughBox;
41 
43  using BoxDivision = SectoredLinearDivision<HoughBox, divisions...>;
44 
47 
49  template <size_t I>
50  using Type = typename HoughBox::template Type<I>;
51 
53  template <class T>
54  using HasType = typename HoughBox::template HasType<T>;
55 
57  template <class T>
58  using TypeIndex = typename HoughBox::template TypeIndex<T>;
59 
61  template <size_t I>
62  using Width = typename HoughBox::template Width<I>;
63 
65  using Node = typename HoughTree::Node;
66 
67  public:
69  explicit BoxDivisionHoughTree(int maxLevel, int sectorLevelSkip = 0)
70  : m_maxLevel(maxLevel)
71  , m_sectorLevelSkip(sectorLevelSkip)
72  , m_overlaps((divisions * 0)...)
73  {
74  }
75 
76  private:
78  template <size_t I>
79  using Array = typename Type<I>::Array;
80 
82  using Arrays = TupleGenerateN<Array, sizeof...(divisions)>;
83 
84  public:
86  size_t getDivision(size_t i) const
87  {
88  return m_divisions[i];
89  }
90 
105  template <size_t I>
106  void constructArray(double lowerBound,
107  double upperBound,
108  Width<I> nBinOverlap = 0,
109  Width<I> nBinWidth = 0)
110  {
111  static_assert(std::is_integral<Width<I> >::value, "Method only applicable to discrete axes");
112  const size_t division = getDivision(I);
113  const int granularityLevel = m_maxLevel + m_sectorLevelSkip;
114  const size_t nBins = std::pow(division, granularityLevel);
115 
116  if (nBinWidth == 0) {
117  nBinWidth = nBinOverlap + 1;
118  }
119 
120  B2ASSERT("Width " << nBinWidth << "is not bigger than overlap " << nBinOverlap,
121  nBinOverlap < nBinWidth);
122 
123  const auto nPositions = (nBinWidth - nBinOverlap) * nBins + nBinOverlap + 1;
124  std::get<I>(m_arrays) = linspace<float>(lowerBound, upperBound, nPositions);
125  std::get<I>(m_overlaps) = nBinOverlap;
126  }
127 
129  template <size_t I>
130  void assignArray(Array<I> array, Width<I> overlap = 0)
131  {
132  std::get<I>(m_arrays) = std::move(array);
133  std::get<I>(m_overlaps) = overlap;
134 
135  // In case of a discrete axes, check whether the size of the array is sensible
136  // such that the bin width at the highest granularity level is a whole number given the overlap.
137  if (std::is_integral<Width<I> >::value) {
138  const int division = getDivision(I);
139  const int granularityLevel = m_maxLevel + m_sectorLevelSkip;
140  const long int nBins = std::pow(division, granularityLevel);
141  const long int nPositions = std::get<I>(m_arrays).size();
142  const long int nWidthTimeNBins = nPositions - 1 + (nBins - 1) * overlap;
143 
144  B2ASSERT("Not enough positions in array to cover all bins.\n"
145  "Expected: positions = " << nBins - (nBins - 1) * overlap + 1 << " at least.\n"
146  "Actual: positions = " << nPositions << " (overlap = " << overlap << ", bins = " << nBins << ")\n",
147  nWidthTimeNBins >= nBins);
148 
149  B2ASSERT("Number of positions in array introduces inhomogeneous width at the highest granularity level.\n"
150  "Expected: positions = 'width * bins - (bins - 1) * overlap + 1'\n"
151  "Actual: positions = " << nPositions << " (overlap = " << overlap << ", bins = " << nBins << ")\n",
152  nWidthTimeNBins % nBins == 0);
153  }
154  }
155 
157  template <class T>
158  std::enable_if_t< HasType<T>::value, void>
159  assignArray(Array<TypeIndex<T>::value > array, Width<TypeIndex<T>::value > overlap = 0)
160  {
161  assignArray<TypeIndex<T>::value>(std::move(array), overlap);
162  }
163 
164  public:
166  void initialize()
167  {
168  // Compose the hough space
169  HoughBox houghPlane = constructHoughPlane();
171  m_houghTree.reset(new HoughTree(std::move(houghPlane), std::move(boxDivision)));
172  }
173 
175  template <class AItemPtrs>
176  void seed(const AItemPtrs& items)
177  {
178  if (not m_houghTree) initialize();
179  m_houghTree->seed(items);
180  }
181 
183  void fell()
184  {
185  m_houghTree->fell();
186  }
187 
189  void raze()
190  {
191  m_houghTree->raze();
192  }
193 
194  public:
196  HoughTree* getTree() const
197  {
198  return m_houghTree.get();
199  }
200 
202  int getMaxLevel() const
203  {
204  return m_maxLevel;
205  }
206 
208  void setMaxLevel(int maxLevel)
209  {
210  m_maxLevel = maxLevel;
211  }
212 
214  int getSectorLevelSkip() const
215  {
217  }
218 
220  void setSectorLevelSkip(int sectorLevelSkip)
221  {
222  m_sectorLevelSkip = sectorLevelSkip;
223  }
224 
226  template <size_t I>
227  const Array<I>& getArray() const
228  {
229  return std::get<I>(m_arrays);
230  }
231 
232  private:
234  template <size_t... Is>
235  HoughBox constructHoughPlaneImpl(const std::index_sequence<Is...>& is __attribute__((unused)))
236  {
237  return HoughBox(Type<Is>::getRange(std::get<Is>(m_arrays))...);
238  }
239 
242  {
243  return constructHoughPlaneImpl(std::make_index_sequence<sizeof...(divisions)>());
244  }
245 
246  private:
248  int m_maxLevel;
249 
251  int m_sectorLevelSkip;
252 
254  const std::array<size_t, sizeof ...(divisions)> m_divisions = {{divisions ...}};
255 
257  typename HoughBox::Delta m_overlaps;
258 
261 
263  std::unique_ptr<HoughTree> m_houghTree = nullptr;
264  };
265  }
267 }
Belle2::TrackFindingCDC::BoxDivisionHoughTree< AHitPtr, AInBoxAlgorithm::HoughBox, divisionX, divisionY >::Width
typename HoughBox::template Width< I > Width
Type of the width in coordinate I.
Definition: BoxDivisionHoughTree.h:70
Belle2::TrackFindingCDC::BoxDivisionHoughTree::BoxDivision
SectoredLinearDivision< HoughBox, divisions... > BoxDivision
Type of the box division strategy.
Definition: BoxDivisionHoughTree.h:51
Belle2::TrackFindingCDC::BoxDivisionHoughTree::m_arrays
Arrays m_arrays
A tuple of value arrays providing the memory for the discrete bin bounds.
Definition: BoxDivisionHoughTree.h:268
Belle2::TrackFindingCDC::BoxDivisionHoughTree::getTree
HoughTree * getTree() const
Getter for the tree used in the search in the hough plane.
Definition: BoxDivisionHoughTree.h:204
Belle2::TrackFindingCDC::BoxDivisionHoughTree::m_houghTree
std::unique_ptr< HoughTree > m_houghTree
Dynamic hough tree structure traversed in the leaf search.
Definition: BoxDivisionHoughTree.h:271
Belle2::TrackFindingCDC::BoxDivisionHoughTree< AHitPtr, AInBoxAlgorithm::HoughBox, divisionX, divisionY >::TypeIndex
typename HoughBox::template TypeIndex< T > TypeIndex
Function to get the coordinate index from its type.
Definition: BoxDivisionHoughTree.h:66
Belle2::TrackFindingCDC::BoxDivisionHoughTree::m_overlaps
HoughBox::Delta m_overlaps
An tuple of division overlaps in each coordinate.
Definition: BoxDivisionHoughTree.h:265
Belle2::TrackFindingCDC::BoxDivisionHoughTree< AHitPtr, AInBoxAlgorithm::HoughBox, divisionX, divisionY >::Node
typename HoughTree::Node Node
Type of the nodes used in the tree for the search.
Definition: BoxDivisionHoughTree.h:73
Belle2::TrackFindingCDC::BoxDivisionHoughTree::getArray
const Array< I > & getArray() const
Getter for the array of discrete value for coordinate I.
Definition: BoxDivisionHoughTree.h:235
Belle2::TrackFindingCDC::BoxDivisionHoughTree::fell
void fell()
Terminates the processing by striping all hit information from the tree.
Definition: BoxDivisionHoughTree.h:191
Belle2::TrackFindingCDC::BoxDivisionHoughTree::Arrays
TupleGenerateN< Array, sizeof...(divisions)> Arrays
Tuple type of the discrete value arrays.
Definition: BoxDivisionHoughTree.h:90
Belle2::TrackFindingCDC::BoxDivisionHoughTree::getDivision
size_t getDivision(size_t i) const
Getter the number of divisions at each level for coordinate index I.
Definition: BoxDivisionHoughTree.h:94
Belle2
Abstract base class for different kinds of events.
Definition: MillepedeAlgorithm.h:19
Belle2::TrackFindingCDC::BoxDivisionHoughTree::initialize
void initialize()
Initialise the algorithm by constructing the hough tree from the parameters.
Definition: BoxDivisionHoughTree.h:174
Belle2::TrackFindingCDC::BoxDivisionHoughTree::getMaxLevel
int getMaxLevel() const
Getter for the currently set maximal level.
Definition: BoxDivisionHoughTree.h:210
Belle2::TrackFindingCDC::BoxDivisionHoughTree::BoxDivisionHoughTree
BoxDivisionHoughTree(int maxLevel, int sectorLevelSkip=0)
Constructor using the given maximal level.
Definition: BoxDivisionHoughTree.h:77
Belle2::TrackFindingCDC::BoxDivisionHoughTree::Array
typename Type< I >::Array Array
Type of the discrete value array to coordinate index I.
Definition: BoxDivisionHoughTree.h:87
Belle2::TrackFindingCDC::BoxDivisionHoughTree::seed
void seed(const AItemPtrs &items)
Prepare the leave finding by filling the top node with given hits.
Definition: BoxDivisionHoughTree.h:184
Belle2::TrackFindingCDC::BoxDivisionHoughTree::constructHoughPlane
HoughBox constructHoughPlane()
Construct the box of the top node of the tree.
Definition: BoxDivisionHoughTree.h:249
Belle2::TrackFindingCDC::BoxDivisionHoughTree::raze
void raze()
Release all memory that the tree aquired during the runs.
Definition: BoxDivisionHoughTree.h:197
Belle2::TrackFindingCDC::BoxDivisionHoughTree::getSectorLevelSkip
int getSectorLevelSkip() const
Getter for number of levels to skip in first level to form a finer sectored hough space.
Definition: BoxDivisionHoughTree.h:222
Belle2::TrackFindingCDC::BoxDivisionHoughTree::setMaxLevel
void setMaxLevel(int maxLevel)
Setter maximal level of the hough tree.
Definition: BoxDivisionHoughTree.h:216
Belle2::TrackFindingCDC::BoxDivisionHoughTree::setSectorLevelSkip
void setSectorLevelSkip(int sectorLevelSkip)
Setter for number of levels to skip in first level to form a finer sectored hough space.
Definition: BoxDivisionHoughTree.h:228
Belle2::TrackFindingCDC::BoxDivisionHoughTree::m_divisions
const std::array< size_t, sizeof ...(divisions)> m_divisions
Array of the number of divisions at each level.
Definition: BoxDivisionHoughTree.h:262
Belle2::TrackFindingCDC::WeightedFastHoughTree
Dynamic tree structure with weighted items in each node which are markable through out the tree.
Definition: WeightedFastHoughTree.h:59
Belle2::TrackFindingCDC::BoxDivisionHoughTree::HoughBox
AHoughBox HoughBox
Type of the box in the hough space.
Definition: BoxDivisionHoughTree.h:48
Belle2::TrackFindingCDC::BoxDivisionHoughTree::HoughTree
WeightedFastHoughTree< AItemPtr, HoughBox, BoxDivision > HoughTree
Type of the fast hough tree structure.
Definition: BoxDivisionHoughTree.h:54
Belle2::TrackFindingCDC::BoxDivisionHoughTree::constructHoughPlaneImpl
HoughBox constructHoughPlaneImpl(const std::index_sequence< Is... > &is __attribute__((unused)))
Construct the box of the top node of the tree. Implementation unroling the indices.
Definition: BoxDivisionHoughTree.h:243
Belle2::TrackFindingCDC::BoxDivisionHoughTree::assignArray
void assignArray(Array< I > array, Width< I > overlap=0)
Provide an externally constructed array by coordinate index.
Definition: BoxDivisionHoughTree.h:138
Belle2::TrackFindingCDC::BoxDivisionHoughTree< AHitPtr, AInBoxAlgorithm::HoughBox, divisionX, divisionY >::HasType
typename HoughBox::template HasType< T > HasType
Predicate that the given type is indeed a coordinate of the hough space.
Definition: BoxDivisionHoughTree.h:62
Belle2::TrackFindingCDC::SectoredLinearDivision
Factory object that constructs sub boxes from a given box with optional overlaps.
Definition: SectoredLinearDivision.h:56
Belle2::TrackFindingCDC::BoxDivisionHoughTree::constructArray
void constructArray(double lowerBound, double upperBound, Width< I > nBinOverlap=0, Width< I > nBinWidth=0)
Construct the discrete value array at coordinate index I.
Definition: BoxDivisionHoughTree.h:114
Belle2::TrackFindingCDC::WeightedFastHoughTree::Node
typename Super::Node Node
Type of the node in the tree.
Definition: WeightedFastHoughTree.h:71
Belle2::TrackFindingCDC::BoxDivisionHoughTree::Type
typename HoughBox::template Type< I > Type
Type of the coordinate I.
Definition: BoxDivisionHoughTree.h:58
Belle2::TrackFindingCDC::BoxDivisionHoughTree::m_maxLevel
int m_maxLevel
Number of the maximum tree level.
Definition: BoxDivisionHoughTree.h:256
Belle2::TrackFindingCDC::BoxDivisionHoughTree::m_sectorLevelSkip
int m_sectorLevelSkip
Number of levels to skip in first level to form a finer sectored hough space.
Definition: BoxDivisionHoughTree.h:259