Acts/Clusterization/Clusterization.hpp

0001 // This file is part of the Acts project.
0002 //
0003 // Copyright (C) 2022 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 http://mozilla.org/MPL/2.0/.
0008
0009 #pragma once
0010
0011 #include <memory>
0012 #include <vector>
0013
0014 namespace Acts::Ccl {
0015
0016 using Label = int;
0017 constexpr Label NO_LABEL = 0;
0018
0019 // When looking for a cell connected to a reference cluster, the code
0020 // always loops backward, starting from the reference cell. Since
0021 // the cells are globally sorted column-wise, the connection function
0022 // can therefore tell when the search should be stopped.
0023 enum class ConnectResult {
0024   eNoConn,      // No connections, keep looking
0025   eNoConnStop,  // No connections, stop looking
0026   eConn         // Found connection
0027 };
0028
0029 // Default connection type for 2-D grids: 4- or 8-cell connectivity
0030 template <typename Cell>
0031 struct Connect2D {
0032   bool conn8;
0033   Connect2D() : conn8{true} {}
0034   explicit Connect2D(bool commonCorner) : conn8{commonCorner} {}
0035   ConnectResult operator()(const Cell& ref, const Cell& iter) const;
0036 };
0037
0038 // Default connection type for 1-D grids: 2-cell connectivity
0039 template <typename Cell>
0040 struct Connect1D {
0041   ConnectResult operator()(const Cell& ref, const Cell& iter) const;
0042 };
0043
0044 // Default connection type based on GridDim
0045 template <typename Cell, std::size_t GridDim = 2>
0046 struct DefaultConnect {
0047   static_assert(GridDim != 1 && GridDim != 2,
0048                 "Only grid dimensions of 1 or 2 are supported");
0049 };
0050
0051 template <typename Cell>
0052 struct DefaultConnect<Cell, 2> : public Connect2D<Cell> {
0053   explicit DefaultConnect(bool commonCorner) : Connect2D<Cell>(commonCorner) {}
0054   DefaultConnect() : DefaultConnect(true) {}
0055 };
0056
0057 template <typename Cell>
0058 struct DefaultConnect<Cell, 1> : public Connect1D<Cell> {};
0059
0060 /// @brief labelClusters
0061 ///
0062 /// In-place connected component labelling using the Hoshen-Kopelman algorithm.
0063 /// The `Cell` type must have the following functions defined:
0064 ///   int  getCellRow(const Cell&),
0065 ///   int  getCellColumn(const Cell&)
0066 ///   int& getCellLabel(Cell&)
0067 ///
0068 /// @param [in] cells the cell collection to be labeled
0069 /// @param [in] connect the connection type (see DefaultConnect)
0070 template <typename CellCollection, std::size_t GridDim = 2,
0071           typename Connect =
0072               DefaultConnect<typename CellCollection::value_type, GridDim>>
0073 void labelClusters(CellCollection& cells, Connect connect = Connect());
0074
0075 /// @brief mergeClusters
0076 ///
0077 /// Merge a set of cells previously labeled (for instance with `labelClusters`)
0078 /// into actual clusters. The Cluster type must have the following function
0079 /// defined:
0080 ///   void clusterAddCell(Cluster&, const Cell&)
0081 ///
0082 /// @return nothing
0083 template <typename CellCollection, typename ClusterCollection,
0084           std::size_t GridDim>
0085 ClusterCollection mergeClusters(CellCollection& /*cells*/);
0086
0087 /// @brief createClusters
0088 /// Convenience function which runs both labelClusters and createClusters.
0089 template <typename CellCollection, typename ClusterCollection,
0090           std::size_t GridDim = 2,
0091           typename Connect =
0092               DefaultConnect<typename CellCollection::value_type, GridDim>>
0093 ClusterCollection createClusters(CellCollection& cells,
0094                                  Connect connect = Connect());
0095
0096 }  // namespace Acts::Ccl
0097
0098 #include "Acts/Clusterization/Clusterization.ipp"