Acts/Clusterization/Clusterization.hpp

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 <memory>
0012 #include <vector>
0013
0014 namespace Acts::Ccl {
0015
0016 template <typename Cell>
0017 concept HasRetrievableColumnInfo = requires(Cell cell) {
0018   { getCellColumn(cell) } -> std::same_as<int>;
0019 };
0020
0021 template <typename Cell>
0022 concept HasRetrievableRowInfo = requires(Cell cell) {
0023   { getCellRow(cell) } -> std::same_as<int>;
0024 };
0025
0026 template <typename Cell>
0027 concept HasRetrievableLabelInfo = requires(Cell cell) {
0028   { getCellLabel(cell) } -> std::same_as<int&>;
0029 };
0030
0031 template <typename Cell, typename Cluster>
0032 concept CanAcceptCell = requires(Cell cell, Cluster cluster) {
0033   { clusterAddCell(cluster, cell) } -> std::same_as<void>;
0034 };
0035
0036 using Label = int;
0037 constexpr Label NO_LABEL = 0;
0038
0039 // When looking for a cell connected to a reference cluster, the code
0040 // always loops backward, starting from the reference cell. Since
0041 // the cells are globally sorted column-wise, the connection function
0042 // can therefore tell when the search should be stopped.
0043 enum class ConnectResult {
0044   eNoConn,      // No connections, keep looking
0045   eNoConnStop,  // No connections, stop looking
0046   eConn         // Found connection
0047 };
0048
0049 // Default connection type for 2-D grids: 4- or 8-cell connectivity
0050 template <typename Cell>
0051   requires(Acts::Ccl::HasRetrievableColumnInfo<Cell> &&
0052            Acts::Ccl::HasRetrievableRowInfo<Cell>)
0053 struct Connect2D {
0054   bool conn8{true};
0055   Connect2D() = default;
0056   explicit Connect2D(bool commonCorner) : conn8{commonCorner} {}
0057   virtual ConnectResult operator()(const Cell& ref, const Cell& iter) const;
0058   virtual ~Connect2D() = default;
0059 };
0060
0061 // Default connection type for 1-D grids: 2-cell connectivity
0062 template <Acts::Ccl::HasRetrievableColumnInfo Cell>
0063 struct Connect1D {
0064   virtual ConnectResult operator()(const Cell& ref, const Cell& iter) const;
0065   virtual ~Connect1D() = default;
0066 };
0067
0068 // Default connection type based on GridDim
0069 template <typename Cell, std::size_t GridDim = 2>
0070 struct DefaultConnect {
0071   static_assert(GridDim != 1 && GridDim != 2,
0072                 "Only grid dimensions of 1 or 2 are supported");
0073 };
0074
0075 template <typename Cell>
0076 struct DefaultConnect<Cell, 1> : public Connect1D<Cell> {
0077   ~DefaultConnect() override = default;
0078 };
0079
0080 template <typename Cell>
0081 struct DefaultConnect<Cell, 2> : public Connect2D<Cell> {
0082   explicit DefaultConnect(bool commonCorner) : Connect2D<Cell>(commonCorner) {}
0083   DefaultConnect() = default;
0084   ~DefaultConnect() override = default;
0085 };
0086
0087 /// @brief labelClusters
0088 ///
0089 /// In-place connected component labelling using the Hoshen-Kopelman algorithm.
0090 /// The `Cell` type must have the following functions defined:
0091 ///   int  getCellRow(const Cell&),
0092 ///   int  getCellColumn(const Cell&)
0093 ///   int& getCellLabel(Cell&)
0094 ///
0095 /// @param [in] cells the cell collection to be labeled
0096 /// @param [in] connect the connection type (see DefaultConnect)
0097 template <typename CellCollection, std::size_t GridDim = 2,
0098           typename Connect =
0099               DefaultConnect<typename CellCollection::value_type, GridDim>>
0100   requires(
0101       Acts::Ccl::HasRetrievableLabelInfo<typename CellCollection::value_type>)
0102 void labelClusters(CellCollection& cells, Connect connect = Connect());
0103
0104 /// @brief mergeClusters
0105 ///
0106 /// Merge a set of cells previously labeled (for instance with `labelClusters`)
0107 /// into actual clusters. The Cluster type must have the following function
0108 /// defined:
0109 ///   void clusterAddCell(Cluster&, const Cell&)
0110 ///
0111 /// @return nothing
0112 template <typename CellCollection, typename ClusterCollection,
0113           std::size_t GridDim>
0114   requires(GridDim == 1 || GridDim == 2) &&
0115           Acts::Ccl::HasRetrievableLabelInfo<
0116               typename CellCollection::value_type>
0117 ClusterCollection mergeClusters(CellCollection& /*cells*/);
0118
0119 /// @brief createClusters
0120 /// Convenience function which runs both labelClusters and createClusters.
0121 template <typename CellCollection, typename ClusterCollection,
0122           std::size_t GridDim = 2,
0123           typename Connect =
0124               DefaultConnect<typename CellCollection::value_type, GridDim>>
0125 ClusterCollection createClusters(CellCollection& cells,
0126                                  Connect connect = Connect());
0127
0128 }  // namespace Acts::Ccl
0129
0130 #include "Acts/Clusterization/Clusterization.ipp"