![]() |
|
|||
File indexing completed on 2025-10-13 08:16:13
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 #pragma once 0010 0011 #include <algorithm> 0012 #include <array> 0013 #include <cassert> 0014 #include <limits> 0015 #include <sstream> 0016 #include <string> 0017 0018 namespace Acts { 0019 /// @brief An orthogonal range in an arbitrary number of dimensions 0020 /// 0021 /// By combining a number one-dimensional ranges we can (under the assumption 0022 /// that our axes are orthogonal) construct an orthogonal range of values. In 0023 /// other words, a hyperrectangular volume in space. 0024 /// 0025 /// @tparam Dims The number of dimensions in our range 0026 /// @tparam Type The scalar type of our ranges 0027 /// @tparam Vector The vector type used to define coordinates 0028 template <std::size_t Dims, typename Type, 0029 template <typename, std::size_t> typename Vector = std::array> 0030 class RangeXD { 0031 private: 0032 // @TODO: Replace with std::span or boost::span once available 0033 template <typename, std::size_t> 0034 struct SingleElementContainer { 0035 Type* element; 0036 0037 Type& operator[](std::size_t i) { 0038 (void)i; 0039 assert(i == 0); 0040 0041 return *element; 0042 } 0043 }; 0044 0045 public: 0046 RangeXD() { 0047 for (std::size_t i = 0; i < Dims; ++i) { 0048 min(i) = std::numeric_limits<Type>::lowest(); 0049 max(i) = std::numeric_limits<Type>::max(); 0050 } 0051 } 0052 0053 /// @brief Construct a range from a pair of minimum and maximum values 0054 /// @param minima The minimum values of the range 0055 /// @param maxima The maximum values of the range 0056 RangeXD(Vector<Type, Dims> minima, Vector<Type, Dims> maxima) 0057 : m_minima(minima), m_maxima(maxima) {} 0058 0059 /// @brief Construct a range from a pair of single minimum and maximum values 0060 /// @note Only available for one-dimensional ranges 0061 /// @param minimum The minimum value of the range 0062 /// @param maximum The maximum value of the range 0063 RangeXD(Type minimum, Type maximum) 0064 requires(Dims == 1) 0065 : m_minima({minimum}), m_maxima({maximum}) {} 0066 0067 /// @brief Construct a range from a pair of minimum and maximum values 0068 /// @note Only available for one-dimensional ranges 0069 /// @param p The pair of minimum and maximum values 0070 explicit RangeXD(const std::pair<Type, Type>& p) 0071 requires(Dims == 1) 0072 : m_minima({p.first}), m_maxima({p.second}) {} 0073 0074 /// @brief Determine whether this range is degenerate 0075 /// 0076 /// A degenerate multi-dimensional range has no volume and cannot contain 0077 /// any values. This is the case if any of its dimensions are degenerate. 0078 /// 0079 /// @return true The range is degenerate 0080 /// @return false The range is not degenerate 0081 bool degenerate() const { 0082 for (std::size_t i = 0; i < Dims; ++i) { 0083 if (min(i) >= max(i)) { 0084 return true; 0085 } 0086 } 0087 return false; 0088 } 0089 0090 /// @brief Determine whether the range contains a certain point 0091 /// 0092 /// This is true if and only if the range contains the point in all of its 0093 /// dimensions. 0094 /// 0095 /// @param v The coordinate to check for membership in the range 0096 /// 0097 /// @return true The coordinate is inside the range 0098 /// @return false The coordinate is outside the range 0099 template <template <typename, std::size_t> typename coordinate_t = std::array> 0100 bool contains(const coordinate_t<Type, Dims>& v) const { 0101 for (std::size_t i = 0; i < Dims; ++i) { 0102 if (!(min(i) <= v[i] && v[i] < max(i))) { 0103 return false; 0104 } 0105 } 0106 0107 return true; 0108 } 0109 0110 /// @brief Access one of the dimensional ranges of the volume 0111 /// 0112 /// @param i The index of the dimension to access 0113 /// @return A reference to the dimension contained in this range 0114 RangeXD<1, Type, SingleElementContainer> operator[](const std::size_t& i) { 0115 return RangeXD<1, Type, SingleElementContainer>{{&min(i)}, {&max(i)}}; 0116 } 0117 0118 /// @brief Access one of the dimensional ranges of the volume 0119 /// 0120 /// @param i The index of the dimension to access 0121 /// @return A reference to the dimension contained in this range 0122 RangeXD<1, Type> operator[](const std::size_t& i) const { 0123 return RangeXD<1, Type>{{min(i)}, {max(i)}}; 0124 } 0125 0126 /// @brief Assignment operator 0127 /// 0128 /// Copy the right-hand range into the left-hand range, which means setting 0129 /// the minimum and maximum to equal the minimum and maximum of the 0130 /// right-hand side. 0131 /// 0132 /// @param o The range of values to copy 0133 /// 0134 /// @return This range 0135 template <template <typename, std::size_t> typename V> 0136 RangeXD& operator=(const RangeXD<Dims, Type, V>& o) { 0137 for (std::size_t i = 0; i < Dims; ++i) { 0138 min(i) = o.min(i); 0139 max(i) = o.max(i); 0140 } 0141 0142 return *this; 0143 } 0144 0145 /// @brief Determine whether two ranges are equal 0146 /// 0147 /// Two n-dimensional ranges are equal if and only if they are equal in each 0148 /// of their n dimensions. 0149 /// 0150 /// @param o The other range to check for equality 0151 /// 0152 /// @return true The ranges are equal 0153 /// @return false The ranges are not equal 0154 bool operator==(const RangeXD<Dims, Type, Vector>& o) const { 0155 for (std::size_t i = 0; i < Dims; ++i) { 0156 if (!(min(i) == o.min(i) && max(i) == o.max(i))) { 0157 return false; 0158 } 0159 } 0160 0161 return true; 0162 } 0163 0164 /// @brief Determine whether one range is a subset of another range 0165 /// 0166 /// One range is a subset of another range if and only if all points 0167 /// contained within the first set are also contained within the second set. 0168 /// Alternatively, this is equivalent to each of the first range's 0169 /// one-dimensional ranges being a subset of the second range's equivalent 0170 /// one-dimensional range. 0171 /// 0172 /// @param o The other range to compare to 0173 /// 0174 /// @return true The first range is a subset of the second range 0175 /// @return false The first range is not a subset of the second range 0176 bool operator<=(const RangeXD<Dims, Type, Vector>& o) const { 0177 for (std::size_t i = 0; i < Dims; ++i) { 0178 if (!(min(i) >= o.min(i) && max(i) <= o.max(i))) { 0179 return false; 0180 } 0181 } 0182 0183 return true; 0184 } 0185 0186 /// @brief Determine whether one range is a superset of another range 0187 /// 0188 /// One range is a superset of another range if and only if all points 0189 /// contained within the second range are also contained within the first 0190 /// range. Alternatively, this is equivalent to each of the one-dimensional 0191 /// ranges in the first range being a superset of the corresponding 0192 /// one-dimensional range in the second range. 0193 /// 0194 /// @param o The other range to compare to 0195 /// 0196 /// @return true The left-hand range is a superset of the right-hand range 0197 /// @return false The left-hand range is not a superset of the right-hand 0198 /// range 0199 bool operator>=(const RangeXD<Dims, Type, Vector>& o) const { 0200 for (std::size_t i = 0; i < Dims; ++i) { 0201 if (!(min(i) <= o.min(i) && max(i) >= o.max(i))) { 0202 return false; 0203 } 0204 } 0205 0206 return true; 0207 } 0208 0209 /// @brief Compute the intersection of this range with another range 0210 /// 0211 /// The intersection of one orthogonal range with another orthogonal range 0212 /// is in itself an orthogonal range. This operation is commutative. This 0213 /// intersection between two n-dimensional ranges is defined simply as the 0214 /// intersection in each dimension of the two ranges. 0215 /// 0216 /// @param o The orthogonal range to compute the intersection with 0217 /// 0218 /// @return The intersection between the ranges 0219 RangeXD<Dims, Type, Vector> operator&( 0220 const RangeXD<Dims, Type, Vector>& o) const { 0221 RangeXD<Dims, Type> res; 0222 0223 for (std::size_t i = 0; i < Dims; ++i) { 0224 res.min(i) = std::max(min(i), o.min(i)); 0225 res.max(i) = std::min(max(i), o.max(i)); 0226 } 0227 0228 return res; 0229 } 0230 0231 /// @brief Update the range to the intersection with another range 0232 /// 0233 /// This is the assignment version of the operator& method, meaning that it 0234 /// updates the object on which it is called rather than producing a new 0235 /// range. 0236 /// 0237 /// @param o The range to compute the intersection with 0238 /// 0239 /// @return This object 0240 RangeXD<Dims, Type, Vector>& operator&=( 0241 const RangeXD<Dims, Type, Vector>& o) { 0242 for (std::size_t i = 0; i < Dims; ++i) { 0243 min(i) = std::max(min(i), o.min(i)); 0244 max(i) = std::min(max(i), o.max(i)); 0245 } 0246 0247 return *this; 0248 } 0249 0250 /// @brief Determine whether this range intersects another 0251 /// 0252 /// Two n-dimensional ranges intersect if and only if they intersect in 0253 /// every one of their n dimensions. Otherwise, they are disjoint. 0254 /// 0255 /// @param r The other range to check 0256 /// 0257 /// @return true The ranges intersect 0258 /// @return false The ranges do not intersect 0259 bool operator&&(const RangeXD<Dims, Type, Vector>& r) const { 0260 for (std::size_t i = 0; i < Dims; ++i) { 0261 if (!(min(i) < r.max(i) && r.min(i) < max(i))) { 0262 return false; 0263 } 0264 } 0265 0266 return true; 0267 } 0268 0269 /// @brief Represent the range as a string 0270 /// 0271 /// This method produces a helpful string that can be used to debug the 0272 /// range if needed. Not really designed to be used in production code. 0273 /// 0274 /// @return A string representing the range 0275 std::string toString(void) const { 0276 std::stringstream s; 0277 0278 for (std::size_t i = 0; i < Dims; ++i) { 0279 s << min(i) << " <= v[" << i << "] <= " << max(i); 0280 if (i != Dims - 1) { 0281 s << ", "; 0282 } 0283 } 0284 0285 return s.str(); 0286 } 0287 0288 /// @brief Shrink a range by increasing the minimum value 0289 /// 0290 /// Shrink the range by increasing the minimum value. If the given value is 0291 /// smaller than the current minimum (in other words, if the proposed new 0292 /// range would be larger than the current range), this is a no-op. 0293 /// 0294 /// @param i The index of the dimension to shrink 0295 /// @param v The proposed new minimum for the range 0296 void shrinkMin(std::size_t i, const Type& v) { min(i) = std::max(min(i), v); } 0297 0298 /// @brief Shrink a range by decreasing the maximum value 0299 /// 0300 /// Shrink the range by decreasing the maximum value. If the given value is 0301 /// larger than the current maximum (in other words, if the proposed new 0302 /// range would be larger than the current range), this is a no-op. 0303 /// 0304 /// @param i The index of the dimension to shrink 0305 /// @param v The proposed new maximum for the range 0306 void shrinkMax(std::size_t i, const Type& v) { max(i) = std::min(max(i), v); } 0307 0308 /// @brief Shrink a range on both ends 0309 /// 0310 /// Shrink a range by increasing the minimum value as well as decreasing the 0311 /// maximum value. If either of the values are already smaller or larger 0312 /// (respectively) than the proposed values, then that particular boundary 0313 /// of the interval is not shrunk. 0314 /// 0315 /// @note After this operation, the range is always equal to or smaller than 0316 /// [min, max]. 0317 /// 0318 /// @param i The index of the dimension to shrink 0319 /// @param min The proposed new minimum for the range 0320 /// @param max The proposed new maximum for the range 0321 void shrink(std::size_t i, const Type& min, const Type& max) { 0322 shrinkMin(i, min); 0323 shrinkMax(i, max); 0324 } 0325 0326 /// @brief Expand a range by decreasing the minimum value 0327 /// 0328 /// Expand the range by decreasing the minimum value. If the given value is 0329 /// larger than the current minimum (in other words, if the proposed new 0330 /// range would be smaller than the current range), this is a no-op. 0331 /// 0332 /// @param i The index of the dimension to expand 0333 /// @param v The proposed new minimum for the range 0334 void expandMin(std::size_t i, const Type& v) { min(i) = std::min(min(i), v); } 0335 0336 /// @brief Expand a range by increasing the maximum value 0337 /// 0338 /// Expand the range by increasing the maximum value. If the given value is 0339 /// smaller than the current maximum (in other words, if the proposed new 0340 /// range would be smaller than the current range), this is a no-op. 0341 /// 0342 /// @param i The index of the dimension to expand 0343 /// @param v The proposed new maximum for the range 0344 void expandMax(std::size_t i, const Type& v) { max(i) = std::max(max(i), v); } 0345 0346 /// @brief Expand a range on both ends 0347 /// 0348 /// Expand a range by decreasing the minimum value as well as increasing the 0349 /// maximum value. If either of the values are already larger or smaller 0350 /// (respectively) than the proposed values, then that particular boundary 0351 /// of the interval is not expanded. 0352 /// 0353 /// @note After this operation, the range is always equal to or larger than 0354 /// [min, max]. 0355 /// 0356 /// @param i The index of the dimension to expand 0357 /// @param min The proposed new minimum for the range 0358 /// @param max The proposed new maximum for the range 0359 void expand(std::size_t i, const Type& min, const Type& max) { 0360 expandMin(i, min); 0361 expandMax(i, max); 0362 } 0363 0364 /// @brief Set the minimum value 0365 /// 0366 /// Override the minimum value of the range, regardless of what was already 0367 /// set. 0368 /// 0369 /// @note If you want to shrink or expand the range, use the shrink and 0370 /// expand methods. 0371 /// 0372 /// @param i The index of the dimension to set 0373 /// @param v The value to use as the new minimum 0374 void setMin(std::size_t i, const Type& v) { min(i) = v; } 0375 0376 /// @brief Set the maximum value 0377 /// 0378 /// Override the maximum value of the range, regardless of what was already 0379 /// set. 0380 /// 0381 /// @note If you want to shrink or expand the range, use the shrink and 0382 /// expand methods. 0383 /// 0384 /// @param i The index of the dimension to set 0385 /// @param v The value to use as the new maximum 0386 void setMax(std::size_t i, const Type& v) { max(i) = v; } 0387 0388 /// @brief Set the minimum and maximum value 0389 /// 0390 /// Override both the minimum and maximum value of the range, regardless of 0391 /// what they were set to. 0392 /// 0393 /// @note If you want to shrink or expand the range, use the shrink and 0394 /// expand methods. 0395 /// 0396 /// @note After this operation, the range should be exactly equal to [min, 0397 /// max] 0398 /// 0399 /// @param i The index of the dimension to set 0400 /// @param min The new minimum value of the range 0401 /// @param max The new maximum value of the range 0402 void set(std::size_t i, const Type& min, const Type& max) { 0403 setMin(i, min); 0404 setMax(i, max); 0405 } 0406 0407 /// @brief Return the minimum value of the range @p i (inclusive) 0408 /// @param i The index of the dimension to access 0409 /// @return Reference to the minimum value for modification 0410 Type& min(std::size_t i) { return m_minima[i]; } 0411 0412 /// @brief Return the maximum value of the range @p i (inclusive) 0413 /// @param i The index of the dimension to access 0414 /// @return Reference to the maximum value for modification 0415 Type& max(std::size_t i) { return m_maxima[i]; } 0416 0417 /// @brief Return the minimum value of the range @p i (inclusive) 0418 /// @param i The index of the dimension to access 0419 /// @return The minimum value of the specified dimension 0420 Type min(std::size_t i) const { return m_minima[i]; } 0421 0422 /// @brief Return the maximum value of the range @p i (inclusive) 0423 /// @param i The index of the dimension to access 0424 /// @return The maximum value of the specified dimension 0425 Type max(std::size_t i) const { return m_maxima[i]; } 0426 0427 /// Methods for manipulating a range of dimension 1 0428 /// @{ 0429 0430 /// @brief Expand a range by decreasing the minimum value 0431 /// 0432 /// Expand the range by decreasing the minimum value. If the given value is 0433 /// larger than the current minimum (in other words, if the proposed new 0434 /// range would be smaller than the current range), this is a no-op. 0435 /// 0436 /// @param v The proposed new minimum for the range 0437 void expandMin(const Type& v) 0438 requires(Dims == 1) 0439 { 0440 min() = std::min(min(), v); 0441 } 0442 0443 /// @brief Expand a range by increasing the maximum value 0444 /// 0445 /// Expand the range by increasing the maximum value. If the given value is 0446 /// smaller than the current maximum (in other words, if the proposed new 0447 /// range would be smaller than the current range), this is a no-op. 0448 /// 0449 /// @param v The proposed new maximum for the range 0450 void expandMax(const Type& v) 0451 requires(Dims == 1) 0452 { 0453 max() = std::max(max(), v); 0454 } 0455 0456 /// @brief Expand a range on both ends 0457 /// 0458 /// Expand a range by decreasing the minimum value as well as increasing the 0459 /// maximum value. If either of the values are already larger or smaller 0460 /// (respectively) than the proposed values, then that particular boundary 0461 /// of the interval is not expanded. 0462 /// 0463 /// @note After this operation, the range is always equal to or larger than 0464 /// [min, max]. 0465 /// 0466 /// @param min The proposed new minimum for the range 0467 /// @param max The proposed new maximum for the range 0468 void expand(const Type& min, const Type& max) 0469 requires(Dims == 1) 0470 { 0471 expandMin(min); 0472 expandMax(max); 0473 } 0474 0475 /// @brief Shrink a range by increasing the minimum value 0476 /// 0477 /// Shrink the range by increasing the minimum value. If the given value is 0478 /// smaller than the current minimum (in other words, if the proposed new 0479 /// range would be larger than the current range), this is a no-op. 0480 /// 0481 /// @param v The proposed new minimum for the range 0482 void shrinkMin(const Type& v) 0483 requires(Dims == 1) 0484 { 0485 min() = std::max(min(), v); 0486 } 0487 0488 /// @brief Shrink a range by decreasing the maximum value 0489 /// 0490 /// Shrink the range by decreasing the maximum value. If the given value is 0491 /// larger than the current maximum (in other words, if the proposed new 0492 /// range would be larger than the current range), this is a no-op. 0493 /// 0494 /// @param v The proposed new maximum for the range 0495 void shrinkMax(const Type& v) 0496 requires(Dims == 1) 0497 { 0498 max() = std::min(max(), v); 0499 } 0500 0501 /// @brief Shrink a range on both ends 0502 /// 0503 /// Shrink a range by increasing the minimum value as well as decreasing the 0504 /// maximum value. If either of the values are already smaller or larger 0505 /// (respectively) than the proposed values, then that particular boundary 0506 /// of the interval is not shrunk. 0507 /// 0508 /// @note After this operation, the range is always equal to or smaller than 0509 /// [min, max]. 0510 /// 0511 /// @param min The proposed new minimum for the range 0512 /// @param max The proposed new maximum for the range 0513 void shrink(const Type& min, const Type& max) 0514 requires(Dims == 1) 0515 { 0516 shrinkMin(min); 0517 shrinkMax(max); 0518 } 0519 0520 /// @brief Set the minimum value 0521 /// 0522 /// Override the minimum value of the range, regardless of what was already 0523 /// set. 0524 /// 0525 /// @note If you want to shrink or expand the range, use the shrink and 0526 /// expand methods. 0527 /// 0528 /// @param v The value to use as the new minimum 0529 void setMin(const Type& v) 0530 requires(Dims == 1) 0531 { 0532 min() = v; 0533 } 0534 0535 /// @brief Set the maximum value 0536 /// 0537 /// Override the maximum value of the range, regardless of what was already 0538 /// set. 0539 /// 0540 /// @note If you want to shrink or expand the range, use the shrink and 0541 /// expand methods. 0542 /// 0543 /// @param v The value to use as the new maximum 0544 void setMax(const Type& v) 0545 requires(Dims == 1) 0546 { 0547 max() = v; 0548 } 0549 0550 /// @brief Set the minimum and maximum value 0551 /// 0552 /// Override both the minimum and maximum value of the range, regardless of 0553 /// what they were set to. 0554 /// 0555 /// @note If you want to shrink or expand the range, use the shrink and 0556 /// expand methods. 0557 /// 0558 /// @note After this operation, the range should be exactly equal to [min, 0559 /// max] 0560 /// 0561 /// @param min The new minimum value of the range 0562 /// @param max The new maximum value of the range 0563 void set(const Type& min, const Type& max) 0564 requires(Dims == 1) 0565 { 0566 setMin(min); 0567 setMax(max); 0568 } 0569 0570 /// @brief Return the minimum value of the range (inclusive) 0571 /// @return The minimum value of the one-dimensional range 0572 Type min() const 0573 requires(Dims == 1) 0574 { 0575 return min(0); 0576 } 0577 0578 /// @brief Return the minimum value of the range (inclusive) 0579 /// @return Reference to the minimum value for modification 0580 Type& min() 0581 requires(Dims == 1) 0582 { 0583 return min(0); 0584 } 0585 0586 /// @brief Return the maximum value of the range (inclusive) 0587 /// @return The maximum value of the one-dimensional range 0588 Type max() const 0589 requires(Dims == 1) 0590 { 0591 return max(0); 0592 } 0593 0594 /// @brief Return the maximum value of the range (inclusive) 0595 /// @return Reference to the maximum value for modification 0596 Type& max() 0597 requires(Dims == 1) 0598 { 0599 return max(0); 0600 } 0601 0602 /// @brief Compute the size of the range 0603 /// 0604 /// The size of a range is defined as the difference between the minimum and 0605 /// the maximum. For degenerate ranges, this is zero. 0606 /// 0607 /// @warning Due to the nature of numbers, the result of this function can be 0608 /// somewhat ambiguous. For natural numbers, you could argue that the range 0609 /// [n, n] has size 0 or size 1. In this case we say it has size 0. The 0610 /// uncountable nature of the reals means this doesn't matter for them, but 0611 /// this can be awkward when working with integers. 0612 /// 0613 /// @return The size of the range 0614 Type size() const 0615 requires(Dims == 1) 0616 { 0617 return std::max(static_cast<Type>(0), max() - min()); 0618 } 0619 0620 /// @brief Determine if the range contains a given value 0621 /// 0622 /// A value is inside a range if and only if it is greater than the minimum 0623 /// and smaller than the maximum. 0624 /// 0625 /// @param v The value to check 0626 /// 0627 /// @return true The value is inside the range 0628 /// @return false The value is not inside the range 0629 bool contains(const Type& v) const 0630 requires(Dims == 1) 0631 { 0632 return min() <= v && v < max(); 0633 } 0634 0635 /// @} 0636 0637 private: 0638 Vector<Type, Dims> m_minima{}; 0639 Vector<Type, Dims> m_maxima{}; 0640 }; 0641 0642 /// @brief Type alias for a one-dimensional range 0643 /// @details Specialization of RangeXD for one-dimensional ranges 0644 /// @tparam Type The value type of the range 0645 /// @tparam Vector The container type template used to store the range bounds 0646 template <typename Type, 0647 template <typename, std::size_t> typename Vector = std::array> 0648 using Range1D = RangeXD<1, Type, Vector>; 0649 0650 } // namespace Acts
[ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
![]() ![]() |