include/LCUtility/KDTreeLinkerToolsT.h

0001 /**
0002  *  @file   LCContent/include/LCUtility/KDTreeLinkerToolsT.h
0003  *
0004  *  @brief  Header file for the kd tree linker tools template class
0005  *
0006  *  $Log: $
0007  */
0008 #ifndef LC_KD_TREE_LINKER_TOOLS_TEMPLATED_H
0009 #define LC_KD_TREE_LINKER_TOOLS_TEMPLATED_H 1
0010
0011 #include "Api/PandoraContentApi.h"
0012
0013 #include "Objects/CaloHit.h"
0014 #include "Objects/CartesianVector.h"
0015 #include "Objects/Track.h"
0016
0017 #include "Pandora/PandoraInternal.h"
0018
0019 #include <array>
0020
0021 namespace pandora {
0022 class Algorithm;
0023 }
0024
0025 //------------------------------------------------------------------------------------------------------------------------------------------
0026
0027 namespace lc_content {
0028
0029 /**
0030  *  @brief  Box structure used to define 2D field. It's used in KDTree building step to divide the detector space (ECAL,
0031  * HCAL...) and in searching step to create a bounding box around the demanded point (Track collision point, PS
0032  * projection...).
0033  */
0034 template <unsigned DIM>
0035 class KDTreeBoxT {
0036 public:
0037   /**
0038    *  @brief  Default constructor
0039    */
0040   KDTreeBoxT();
0041
0042   /**
0043    *  @brief  Constructor
0044    *
0045    *  @param  dimargs
0046    */
0047   template <typename... Ts>
0048   KDTreeBoxT(Ts... dimargs);
0049
0050   std::array<float, DIM> dimmin; ///<
0051   std::array<float, DIM> dimmax; ///<
0052 };
0053
0054 typedef KDTreeBoxT<2> KDTreeBox;
0055 typedef KDTreeBoxT<3> KDTreeCube;
0056 typedef KDTreeBoxT<4> KDTreeTesseract;
0057
0058 //------------------------------------------------------------------------------------------------------------------------------------------
0059
0060 /**
0061  *  @brief  Data stored in each KDTree node. The dim1/dim2 fields are usually the duplication of some PFRecHit values
0062  *          (eta/phi or x/y). But in some situations, phi field is shifted by +-2.Pi
0063  */
0064 template <typename DATA, unsigned DIM>
0065 class KDTreeNodeInfoT {
0066 public:
0067   /**
0068    *  @brief  Default constructor
0069    */
0070   KDTreeNodeInfoT();
0071
0072   /**
0073    *  @brief  Constructor
0074    *
0075    *  @param  d
0076    *  @param  dimargs
0077    */
0078   template <typename... Ts>
0079   KDTreeNodeInfoT(const DATA& d, Ts... dimargs);
0080
0081   DATA data;                   ///<
0082   std::array<float, DIM> dims; ///<
0083 };
0084
0085 //------------------------------------------------------------------------------------------------------------------------------------------
0086
0087 /**
0088  *  @brief  KDTree node
0089  */
0090 template <typename DATA, unsigned DIM>
0091 class KDTreeNodeT {
0092 public:
0093   /**
0094    *  @brief  Default constructor
0095    */
0096   KDTreeNodeT();
0097
0098   /**
0099    *  @brief  setAttributs
0100    *
0101    *  @param  regionBox
0102    *  @param  infoToStore
0103    */
0104   void setAttributs(const KDTreeBoxT<DIM>& regionBox, const KDTreeNodeInfoT<DATA, DIM>& infoToStore);
0105
0106   /**
0107    *  @brief  setAttributs
0108    *
0109    *  @param  regionBox
0110    */
0111   void setAttributs(const KDTreeBoxT<DIM>& regionBox);
0112
0113   KDTreeNodeInfoT<DATA, DIM> info; ///< Data
0114   KDTreeNodeT<DATA, DIM>* left;    ///< Left son
0115   KDTreeNodeT<DATA, DIM>* right;   ///< Right son
0116   KDTreeBoxT<DIM> region;          ///< Region bounding box.
0117 };
0118
0119 //------------------------------------------------------------------------------------------------------------------------------------------
0120
0121 /**
0122  *  @brief  kdtree_type_adaptor
0123  */
0124 template <typename T>
0125 class kdtree_type_adaptor {
0126 public:
0127   /**
0128    *  @brief  position
0129    *
0130    *  @param  t
0131    *
0132    *  @return position
0133    */
0134   static const pandora::CartesianVector& position(const T* const t);
0135 };
0136
0137 //------------------------------------------------------------------------------------------------------------------------------------------
0138
0139 /**
0140  *  @brief  minmax
0141  *
0142  *  @param  a
0143  *  @param  b
0144  *
0145  *  @return minmax
0146  */
0147 std::pair<float, float> minmax(const float a, const float b);
0148
0149 /**
0150  *  @brief  fill_and_bound_3d_kd_tree
0151  *
0152  *  @param  points
0153  *  @param  nodes
0154  *
0155  *  @return KDTreeCube
0156  */
0157 template <typename T>
0158 KDTreeCube fill_and_bound_3d_kd_tree(const MANAGED_CONTAINER<const T*>& points,
0159                                      std::vector<KDTreeNodeInfoT<const T*, 3>>& nodes);
0160
0161 /**
0162  *  @brief  fill_and_bound_3d_kd_tree_by_index
0163  *
0164  *  @param  points
0165  *  @param  nodes
0166  *
0167  *  @return KDTreeCube
0168  */
0169 template <typename T>
0170 KDTreeCube fill_and_bound_3d_kd_tree_by_index(const std::vector<const T*>& points,
0171                                               std::vector<KDTreeNodeInfoT<unsigned, 3>>& nodes);
0172
0173 /**
0174  *  @brief  fill_and_bound_3d_kd_tree
0175  *
0176  *  @param  caller
0177  *  @param  points
0178  *  @param  nodes
0179  *  @param  passthru
0180  *
0181  *  @return KDTreeCube
0182  */
0183 template <typename T>
0184 KDTreeCube fill_and_bound_3d_kd_tree(const pandora::Algorithm* const caller, const MANAGED_CONTAINER<const T*>& points,
0185                                      std::vector<KDTreeNodeInfoT<const T*, 3>>& nodes, bool passthru = false);
0186
0187 /**
0188  *  @brief  fill_and_bound_4d_kd_tree
0189  *
0190  *  @param  caller
0191  *  @param  points
0192  *  @param  nodes
0193  *  @param  passthru
0194  *
0195  *  @return KDTreeTesseract
0196  */
0197 KDTreeTesseract fill_and_bound_4d_kd_tree(const pandora::Algorithm* const caller,
0198                                           const MANAGED_CONTAINER<const pandora::CaloHit*>& points,
0199                                           std::vector<KDTreeNodeInfoT<const pandora::CaloHit*, 4>>& nodes,
0200                                           bool passthru = false);
0201
0202 /**
0203  *  @brief  build_3d_kd_search_region
0204  *
0205  *  @param  point
0206  *  @param  x_span
0207  *  @param  y_span
0208  *  @param  z_span
0209  *
0210  *  @return KDTreeCube
0211  */
0212 KDTreeCube build_3d_kd_search_region(const pandora::CaloHit* const point, const float x_span, const float y_span,
0213                                      const float z_span);
0214
0215 /**
0216  *  @brief  build_4d_kd_search_region
0217  *
0218  *  @param  point
0219  *  @param  x_span
0220  *  @param  y_span
0221  *  @param  z_span
0222  *  @param  search_layer
0223  *
0224  *  @return KDTreeTesseract
0225  */
0226 KDTreeTesseract build_4d_kd_search_region(const pandora::CaloHit* const point, const float x_span, const float y_span,
0227                                           const float z_span, const float search_layer);
0228
0229 /**
0230  *  @brief  build_4d_kd_search_region
0231  *
0232  *  @param  pos
0233  *  @param  x_span
0234  *  @param  y_span
0235  *  @param  z_span
0236  *  @param  search_layer
0237  *
0238  *  @return KDTreeTesseract
0239  */
0240 KDTreeTesseract build_4d_kd_search_region(const pandora::CartesianVector& pos, const float x_span, const float y_span,
0241                                           const float z_span, const float search_layer);
0242
0243 //------------------------------------------------------------------------------------------------------------------------------------------
0244 //------------------------------------------------------------------------------------------------------------------------------------------
0245
0246 template <unsigned DIM>
0247 inline KDTreeBoxT<DIM>::KDTreeBoxT() {}
0248
0249 //------------------------------------------------------------------------------------------------------------------------------------------
0250
0251 template <unsigned DIM>
0252 template <typename... Ts>
0253 inline KDTreeBoxT<DIM>::KDTreeBoxT(Ts... dimargs) {
0254   static_assert(sizeof...(dimargs) == 2 * DIM, "Constructor requires 2*DIM args");
0255   std::vector<float> dims = {dimargs...};
0256
0257   for (unsigned i = 0; i < DIM; ++i) {
0258     dimmin[i] = dims[2 * i];
0259     dimmax[i] = dims[2 * i + 1];
0260   }
0261 }
0262
0263 //------------------------------------------------------------------------------------------------------------------------------------------
0264 //------------------------------------------------------------------------------------------------------------------------------------------
0265
0266 template <typename DATA, unsigned DIM>
0267 inline KDTreeNodeInfoT<DATA, DIM>::KDTreeNodeInfoT() : data() {}
0268
0269 //------------------------------------------------------------------------------------------------------------------------------------------
0270
0271 template <typename DATA, unsigned DIM>
0272 template <typename... Ts>
0273 inline KDTreeNodeInfoT<DATA, DIM>::KDTreeNodeInfoT(const DATA& d, Ts... dimargs) : data(d), dims{{dimargs...}} {}
0274
0275 //------------------------------------------------------------------------------------------------------------------------------------------
0276 //------------------------------------------------------------------------------------------------------------------------------------------
0277
0278 template <typename DATA, unsigned DIM>
0279 inline KDTreeNodeT<DATA, DIM>::KDTreeNodeT() : left(nullptr), right(nullptr) {}
0280
0281 //------------------------------------------------------------------------------------------------------------------------------------------
0282
0283 template <typename DATA, unsigned DIM>
0284 inline void KDTreeNodeT<DATA, DIM>::setAttributs(const KDTreeBoxT<DIM>& regionBox,
0285                                                  const KDTreeNodeInfoT<DATA, DIM>& infoToStore) {
0286   info = infoToStore;
0287   region = regionBox;
0288 }
0289
0290 //------------------------------------------------------------------------------------------------------------------------------------------
0291
0292 template <typename DATA, unsigned DIM>
0293 inline void KDTreeNodeT<DATA, DIM>::setAttributs(const KDTreeBoxT<DIM>& regionBox) {
0294   region = regionBox;
0295 }
0296
0297 //------------------------------------------------------------------------------------------------------------------------------------------
0298
0299 template <>
0300 inline const pandora::CartesianVector&
0301 kdtree_type_adaptor<const pandora::Track>::position(const pandora::Track* const t) {
0302   return t->GetTrackStateAtCalorimeter().GetPosition();
0303 }
0304
0305 template <>
0306 inline const pandora::CartesianVector&
0307 kdtree_type_adaptor<const pandora::CaloHit>::position(const pandora::CaloHit* const t) {
0308   return t->GetPositionVector();
0309 }
0310
0311 template <>
0312 inline const pandora::CartesianVector&
0313 kdtree_type_adaptor<const pandora::CartesianVector>::position(const pandora::CartesianVector* const t) {
0314   return *t;
0315 }
0316
0317 //------------------------------------------------------------------------------------------------------------------------------------------
0318
0319 template <typename T>
0320 KDTreeCube fill_and_bound_3d_kd_tree(const MANAGED_CONTAINER<const T*>& points,
0321                                      std::vector<KDTreeNodeInfoT<const T*, 3>>& nodes) {
0322   std::array<float, 3> minpos{{0.f, 0.f, 0.f}}, maxpos{{0.f, 0.f, 0.f}};
0323
0324   unsigned i = 0;
0325
0326   for (const T* const point : points) {
0327     const pandora::CartesianVector& pos = kdtree_type_adaptor<const T>::position(point);
0328     nodes.emplace_back(point, pos.GetX(), pos.GetY(), pos.GetZ());
0329
0330     if (0 == i) {
0331       minpos[0] = pos.GetX();
0332       minpos[1] = pos.GetY();
0333       minpos[2] = pos.GetZ();
0334       maxpos[0] = pos.GetX();
0335       maxpos[1] = pos.GetY();
0336       maxpos[2] = pos.GetZ();
0337     } else {
0338       minpos[0] = std::min(pos.GetX(), minpos[0]);
0339       minpos[1] = std::min(pos.GetY(), minpos[1]);
0340       minpos[2] = std::min(pos.GetZ(), minpos[2]);
0341       maxpos[0] = std::max(pos.GetX(), maxpos[0]);
0342       maxpos[1] = std::max(pos.GetY(), maxpos[1]);
0343       maxpos[2] = std::max(pos.GetZ(), maxpos[2]);
0344     }
0345
0346     ++i;
0347   }
0348
0349   return KDTreeCube(minpos[0], maxpos[0], minpos[1], maxpos[1], minpos[2], maxpos[2]);
0350 }
0351
0352 //------------------------------------------------------------------------------------------------------------------------------------------
0353
0354 template <typename T>
0355 KDTreeCube fill_and_bound_3d_kd_tree_by_index(const std::vector<const T*>& points,
0356                                               std::vector<KDTreeNodeInfoT<unsigned, 3>>& nodes) {
0357   std::array<float, 3> minpos{{0.f, 0.f, 0.f}}, maxpos{{0.f, 0.f, 0.f}};
0358
0359   unsigned i = 0;
0360
0361   for (const T* const point : points) {
0362     const pandora::CartesianVector& pos = kdtree_type_adaptor<const T>::position(point);
0363     nodes.emplace_back(i, pos.GetX(), pos.GetY(), pos.GetZ());
0364
0365     if (0 == i) {
0366       minpos[0] = pos.GetX();
0367       minpos[1] = pos.GetY();
0368       minpos[2] = pos.GetZ();
0369       maxpos[0] = pos.GetX();
0370       maxpos[1] = pos.GetY();
0371       maxpos[2] = pos.GetZ();
0372     } else {
0373       minpos[0] = std::min(pos.GetX(), minpos[0]);
0374       minpos[1] = std::min(pos.GetY(), minpos[1]);
0375       minpos[2] = std::min(pos.GetZ(), minpos[2]);
0376       maxpos[0] = std::max(pos.GetX(), maxpos[0]);
0377       maxpos[1] = std::max(pos.GetY(), maxpos[1]);
0378       maxpos[2] = std::max(pos.GetZ(), maxpos[2]);
0379     }
0380
0381     ++i;
0382   }
0383
0384   return KDTreeCube(minpos[0], maxpos[0], minpos[1], maxpos[1], minpos[2], maxpos[2]);
0385 }
0386
0387 //------------------------------------------------------------------------------------------------------------------------------------------
0388
0389 template <typename T>
0390 KDTreeCube fill_and_bound_3d_kd_tree(const pandora::Algorithm* const caller, const MANAGED_CONTAINER<const T*>& points,
0391                                      std::vector<KDTreeNodeInfoT<const T*, 3>>& nodes, bool passthru) {
0392   std::array<float, 3> minpos{{0.f, 0.f, 0.f}}, maxpos{{0.f, 0.f, 0.f}};
0393
0394   unsigned i = 0;
0395
0396   for (const T* const point : points) {
0397     if (!passthru && !PandoraContentApi::IsAvailable(*caller, point))
0398       continue;
0399
0400     const pandora::CartesianVector& pos = kdtree_type_adaptor<const T>::position(point);
0401     nodes.emplace_back(point, pos.GetX(), pos.GetY(), pos.GetZ());
0402
0403     if (0 == i) {
0404       minpos[0] = pos.GetX();
0405       minpos[1] = pos.GetY();
0406       minpos[2] = pos.GetZ();
0407       maxpos[0] = pos.GetX();
0408       maxpos[1] = pos.GetY();
0409       maxpos[2] = pos.GetZ();
0410     } else {
0411       minpos[0] = std::min(pos.GetX(), minpos[0]);
0412       minpos[1] = std::min(pos.GetY(), minpos[1]);
0413       minpos[2] = std::min(pos.GetZ(), minpos[2]);
0414       maxpos[0] = std::max(pos.GetX(), maxpos[0]);
0415       maxpos[1] = std::max(pos.GetY(), maxpos[1]);
0416       maxpos[2] = std::max(pos.GetZ(), maxpos[2]);
0417     }
0418
0419     ++i;
0420   }
0421
0422   return KDTreeCube(minpos[0], maxpos[0], minpos[1], maxpos[1], minpos[2], maxpos[2]);
0423 }
0424
0425 } // namespace lc_content
0426
0427 #endif // LC_KD_TREE_LINKER_TOOLS_TEMPLATED_H