src/Seeding2/CylindricalSpacePointKDTree.cpp

0001 // This file is part of the ACTS project.
0002 //
0003 // Copyright (C) 2016 CERN for the benefit of the ACTS project
0004 //
0005 // This Source Code Form is subject to the terms of the Mozilla Public
0006 // License, v. 2.0. If a copy of the MPL was not distributed with this
0007 // file, You can obtain one at https://mozilla.org/MPL/2.0/.
0008
0009 #include "Acts/Seeding2/CylindricalSpacePointKDTree.hpp"
0010
0011 namespace Acts::Experimental {
0012
0013 CylindricalSpacePointKDTree::CylindricalSpacePointKDTree(
0014     Tree tree, std::unique_ptr<const Logger> logger)
0015     : m_tree(std::move(tree)), m_logger(std::move(logger)) {}
0016
0017 CylindricalSpacePointKDTree::Tree::range_t
0018 CylindricalSpacePointKDTree::validTupleOrthoRangeLH(
0019     const Options &options, const ConstSpacePointProxy2 &low) const {
0020   float colMin = options.collisionRegionMin;
0021   float colMax = options.collisionRegionMax;
0022   float pL = low.phi();
0023   float rL = low.zr()[1];
0024   float zL = low.zr()[0];
0025
0026   Tree::range_t res;
0027
0028   /*
0029    * Cut: Ensure that we search only in φ_min ≤ φ ≤ φ_max, as defined by the
0030    * seeding configuration.
0031    */
0032   res[DimPhi].shrinkMin(options.phiMin);
0033   res[DimPhi].shrinkMax(options.phiMax);
0034
0035   /*
0036    * Cut: Ensure that we search only in r ≤ r_max, as defined by the seeding
0037    * configuration.
0038    */
0039   res[DimR].shrinkMax(options.rMax);
0040
0041   /*
0042    * Cut: Ensure that we search only in z_min ≤ z ≤ z_max, as defined by the
0043    * seeding configuration.
0044    */
0045   res[DimZ].shrinkMin(options.zMin);
0046   res[DimZ].shrinkMax(options.zMax);
0047
0048   /*
0049    * Cut: Ensure that we search only in Δr_min ≤ r - r_L ≤ Δr_max, as defined
0050    * by the seeding configuration and the given lower spacepoint.
0051    */
0052   res[DimR].shrinkMin(rL + options.deltaRMin);
0053   res[DimR].shrinkMax(rL + options.deltaRMax);
0054
0055   /*
0056    * Cut: Now that we have constrained r, we can use that new r range to
0057    * further constrain z.
0058    */
0059   float zMax = (res[DimR].max() / rL) * (zL - colMin) + colMin;
0060   float zMin = colMax - (res[DimR].max() / rL) * (colMax - zL);
0061
0062   /*
0063    * This cut only works if z_low is outside the collision region for z.
0064    */
0065   if (zL > colMin) {
0066     res[DimZ].shrinkMax(zMax);
0067   } else if (zL < colMax) {
0068     res[DimZ].shrinkMin(zMin);
0069   }
0070
0071   /*
0072    * Cut: Shrink the z-range using the maximum cot(θ).
0073    */
0074   res[DimZ].shrinkMin(zL - options.cotThetaMax * (res[DimR].max() - rL));
0075   res[DimZ].shrinkMax(zL + options.cotThetaMax * (res[DimR].max() - rL));
0076
0077   /*
0078    * Cut: Shrink the φ range, such that Δφ_min ≤ φ - φ_L ≤ Δφ_max
0079    */
0080   res[DimPhi].shrinkMin(pL - options.deltaPhiMax);
0081   res[DimPhi].shrinkMax(pL + options.deltaPhiMax);
0082
0083   // Cut: Ensure that z-distance between SPs is within max and min values.
0084   res[DimZ].shrinkMin(zL - options.deltaZMax);
0085   res[DimZ].shrinkMax(zL + options.deltaZMax);
0086
0087   return res;
0088 }
0089
0090 CylindricalSpacePointKDTree::Tree::range_t
0091 CylindricalSpacePointKDTree::validTupleOrthoRangeHL(
0092     const Options &options, const ConstSpacePointProxy2 &high) const {
0093   float pM = high.phi();
0094   float rM = high.zr()[1];
0095   float zM = high.zr()[0];
0096
0097   Tree::range_t res;
0098
0099   /*
0100    * Cut: Ensure that we search only in φ_min ≤ φ ≤ φ_max, as defined by the
0101    * seeding configuration.
0102    */
0103   res[DimPhi].shrinkMin(options.phiMin);
0104   res[DimPhi].shrinkMax(options.phiMax);
0105
0106   /*
0107    * Cut: Ensure that we search only in r ≤ r_max, as defined by the seeding
0108    * configuration.
0109    */
0110   res[DimR].shrinkMax(options.rMax);
0111
0112   /*
0113    * Cut: Ensure that we search only in z_min ≤ z ≤ z_max, as defined by the
0114    * seeding configuration.
0115    */
0116   res[DimZ].shrinkMin(options.zMin);
0117   res[DimZ].shrinkMax(options.zMax);
0118
0119   /*
0120    * Cut: Ensure that we search only in Δr_min ≤ r_H - r ≤ Δr_max, as defined
0121    * by the seeding configuration and the given higher spacepoint.
0122    */
0123   res[DimR].shrinkMin(rM - options.deltaRMax);
0124   res[DimR].shrinkMax(rM - options.deltaRMin);
0125
0126   /*
0127    * Cut: Now that we have constrained r, we can use that new r range to
0128    * further constrain z.
0129    */
0130   float fracR = res[DimR].min() / rM;
0131
0132   float zMin =
0133       (zM - options.collisionRegionMin) * fracR + options.collisionRegionMin;
0134   float zMax =
0135       (zM - options.collisionRegionMax) * fracR + options.collisionRegionMax;
0136
0137   res[DimZ].shrinkMin(std::min(zMin, zM));
0138   res[DimZ].shrinkMax(std::max(zMax, zM));
0139
0140   /*
0141    * Cut: Shrink the φ range, such that Δφ_min ≤ φ - φ_H ≤ Δφ_max
0142    */
0143   res[DimPhi].shrinkMin(pM - options.deltaPhiMax);
0144   res[DimPhi].shrinkMax(pM + options.deltaPhiMax);
0145
0146   // Cut: Ensure that z-distance between SPs is within max and min values.
0147   res[DimZ].shrinkMin(zM - options.deltaZMax);
0148   res[DimZ].shrinkMax(zM + options.deltaZMax);
0149
0150   return res;
0151 }
0152
0153 void CylindricalSpacePointKDTree::validTuples(const Options &lhOptions,
0154                                               const Options &hlOptions,
0155                                               const ConstSpacePointProxy2 &spM,
0156                                               std::size_t nTopSeedConf,
0157                                               Candidates &candidates) const {
0158   using range_t = Tree::range_t;
0159
0160   /*
0161    * Calculate the search ranges for bottom and top candidates for this middle
0162    * space point.
0163    */
0164   range_t bottom_r = validTupleOrthoRangeHL(hlOptions, spM);
0165   range_t top_r = validTupleOrthoRangeLH(lhOptions, spM);
0166
0167   /*
0168    * Calculate the value of cot(θ) for this middle spacepoint.
0169    */
0170   float cotTheta =
0171       std::max(std::abs(spM.zr()[0] / spM.zr()[1]), lhOptions.cotThetaMax);
0172
0173   /*
0174    * Calculate the maximum Δr, given that we have already constrained our
0175    * search space.
0176    */
0177   float deltaRMaxTop = top_r[DimR].max() - spM.zr()[1];
0178   float deltaRMaxBottom = spM.zr()[1] - bottom_r[DimR].min();
0179
0180   /*
0181    * Create the search range for the bottom spacepoint assuming a
0182    * monotonically increasing z track, by calculating the minimum z value from
0183    * the cot(θ), and by setting the maximum to the z position of the middle
0184    * spacepoint - if the z position is higher than the middle point, then it
0185    * would be a decreasing z track!
0186    */
0187   range_t bottom_lh_r = bottom_r;
0188   bottom_lh_r[DimZ].shrink(spM.zr()[0] - cotTheta * deltaRMaxBottom,
0189                            spM.zr()[0]);
0190
0191   /*
0192    * Calculate the search ranges for the other four sets of points in a
0193    * similar fashion.
0194    */
0195   range_t top_lh_r = top_r;
0196   top_lh_r[DimZ].shrink(spM.zr()[0], spM.zr()[0] + cotTheta * deltaRMaxTop);
0197
0198   range_t bottom_hl_r = bottom_r;
0199   bottom_hl_r[DimZ].shrink(spM.zr()[0],
0200                            spM.zr()[0] + cotTheta * deltaRMaxBottom);
0201   range_t top_hl_r = top_r;
0202   top_hl_r[DimZ].shrink(spM.zr()[0] - cotTheta * deltaRMaxTop, spM.zr()[0]);
0203
0204   /*
0205    * Now, we will actually search for the spaces. Remembering that we combine
0206    * bottom and top candidates for increasing and decreasing tracks
0207    * separately, we will first check whether both the search ranges for
0208    * increasing tracks are not degenerate - if they are, we will never find
0209    * any seeds and we do not need to bother doing the search.
0210    */
0211   if (!bottom_lh_r.degenerate() && !top_lh_r.degenerate()) {
0212     /*
0213      * Search the trees for points that lie in the given search range.
0214      */
0215     m_tree.rangeSearchMapDiscard(
0216         top_lh_r,
0217         [&candidates](const Tree::coordinate_t &, const Tree::value_t &top) {
0218           candidates.top_lh_v.push_back(top);
0219         });
0220   }
0221
0222   /*
0223    * Perform the same search for candidate bottom spacepoints, but for
0224    * monotonically decreasing z tracks.
0225    */
0226   if (!bottom_hl_r.degenerate() && !top_hl_r.degenerate()) {
0227     m_tree.rangeSearchMapDiscard(
0228         top_hl_r,
0229         [&candidates](const Tree::coordinate_t &, const Tree::value_t &top) {
0230           candidates.top_hl_v.push_back(top);
0231         });
0232   }
0233
0234   // apply cut on the number of top SP if seedConfirmation is true
0235   bool search_bot_lh = candidates.top_lh_v.size() >= nTopSeedConf;
0236   bool search_bot_hl = candidates.top_hl_v.size() >= nTopSeedConf;
0237
0238   /*
0239    * Next, we perform a search for bottom candidates in increasing z tracks,
0240    * which only makes sense if we found any bottom candidates.
0241    */
0242   if (!candidates.top_lh_v.empty() && search_bot_lh) {
0243     m_tree.rangeSearchMapDiscard(
0244         bottom_lh_r,
0245         [&candidates](const Tree::coordinate_t &, const Tree::value_t &bottom) {
0246           candidates.bottom_lh_v.push_back(bottom);
0247         });
0248   }
0249
0250   /*
0251    * And repeat for the top spacepoints for decreasing z tracks!
0252    */
0253   if (!candidates.top_hl_v.empty() && search_bot_hl) {
0254     m_tree.rangeSearchMapDiscard(
0255         bottom_hl_r,
0256         [&candidates](const Tree::coordinate_t &, const Tree::value_t &bottom) {
0257           candidates.bottom_hl_v.push_back(bottom);
0258         });
0259   }
0260 }
0261
0262 CylindricalSpacePointKDTreeBuilder::CylindricalSpacePointKDTreeBuilder(
0263     std::unique_ptr<const Logger> _logger)
0264     : m_logger(std::move(_logger)) {}
0265
0266 void CylindricalSpacePointKDTreeBuilder::insert(SpacePointIndex index,
0267                                                 float phi, float r, float z) {
0268   Tree::coordinate_t point{phi, r, z};
0269   m_points.emplace_back(point, index);
0270 }
0271
0272 void CylindricalSpacePointKDTreeBuilder::extend(
0273     const SpacePointContainer2::ConstRange &spacePoints) {
0274   for (const auto &sp : spacePoints) {
0275     insert(sp);
0276   }
0277 }
0278
0279 CylindricalSpacePointKDTree CylindricalSpacePointKDTreeBuilder::build() {
0280   CylindricalSpacePointKDTree result(Tree(std::move(m_points)),
0281                                      m_logger->clone());
0282   clear();
0283   return result;
0284 }
0285
0286 }  // namespace Acts::Experimental