Acts::InPlaceClusterization Namespace Reference

Namespaces
namespace	traits

Classes
struct	Cell
	A possible Cell type, that can be clustered. More...
struct	ConnectionHelper
	default connection helper which should work for arbitrary cells which fulfil the CellWithLabelConcept More...

Concepts
concept	CellWithLabel
	concept of a call object that can be clustered.
concept	SequenceContainer
	base concept for the container that can be used for a cell collection
concept	CellCollection
	concept of a cell container that can be clustered

Enumerations
enum class	EConnectionType { CommonEdgeOrCorner , CommonEdge }

Functions
template<typename coordinates_t>
bool	isConnectedCommonEdgeOrCorner (const coordinates_t &coordinates_diff)
	test whether cells are connected considering common corners and edges.
template<typename coordinates_t>
bool	isConnectedCommonEdge (const coordinates_t &coordinates_diff)
	test whether cells are connected considering common edges only.
template<EConnectionType connection_type = EConnectionType::CommonEdgeOrCorner, CellCollection cell_container_t = std::span<Cell<int, 2, unsigned int> >>
auto	defaultConnectionHelper (const cell_container_t &cells)
template<typename coordinate_t>
auto	absDifference (coordinate_t a, coordinate_t b)
	compute the absolute difference of two coordinates
template<unsigned int SORT_AXIS, CellCollection cell_collection_t, std::unsigned_integral index_t = unsigned int, typename connection_helper_t>
void	labelSortedCells (cell_collection_t &cells, connection_helper_t &&connection_helper)
	Label cells which are in ascending order of the coordinate of the given axis.
template<unsigned int AXIS, CellCollection cell_collection_t, std::size_t NDim = 2, std::unsigned_integral index_t = unsigned int>
void	sortCellsByCoordinate (cell_collection_t &cells)
	Sort the cells in ascending order of the coordinate of the specified axis.
template<CellCollection cell_collection_t>
void	groupCellsByLabel (cell_collection_t &cells)
	Sort the cells in ascending order of the asscoiated label.
template<unsigned int SORT_AXIS, std::unsigned_integral index_t = unsigned int, CellCollection cell_collection_t = std::span<Cell<int, 2, unsigned int> >, typename connection_helper_t = ConnectionHelper<Cell<int, 2, unsigned int> >>
void	clusterize (cell_collection_t &cells, connection_helper_t &&connection_helper=ConnectionHelper< typename cell_collection_t::value_type, EConnectionType::CommonEdgeOrCorner >{})
	Sort the cell collection in such a way that cells of a cluster are adjacent.
template<CellCollection cell_collection_t, std::unsigned_integral index_t = unsigned int>
std::size_t	countLabels (const cell_collection_t &cells)
	determine the number of clusters.
template<CellCollection cell_collection_t, typename func_t>
void	for_each_cluster (cell_collection_t &cells, func_t func)
	call the given function for each cluster of a label sorted cell collection.
template<CellCollection cell_collection_t, typename range_collection_t>
void	addCellRanges (const cell_collection_t &cells, range_collection_t &ranges)
	Add element ranges for each cluster in the cell collection to the given range container.
template<unsigned int AXIS, CellCollection cell_collection_t, typename range_collection_t>
void	addCellRangesAndSort (cell_collection_t &cells, range_collection_t &ranges)
	Sort the cells of each cluster by one coordinate and add cell ranges to the given range container.

Enumeration Type Documentation

EConnectionType

enum class Acts::InPlaceClusterization::EConnectionType

strong

Enumerator
CommonEdgeOrCorner
CommonEdge

Definition at line 127 of file InPlaceClusterization.h.

{ CommonEdgeOrCorner, CommonEdge };

Function Documentation

absDifference()

template<typename coordinate_t>

auto Acts::InPlaceClusterization::absDifference	(	coordinate_t	a,
		coordinate_t	b )

compute the absolute difference of two coordinates

Definition at line 176 of file InPlaceClusterization.h.

                                                   {
  if constexpr (std::is_signed_v<coordinate_t>) {
    // @TODO check overflow with C++26, or change return type to
    //       an unsigned integer of same size.
    return static_cast<coordinate_t>(std::abs(a - b));
  } else {
    return static_cast<coordinate_t>((a > b ? a - b : b - a));
  }
}

addCellRanges()

template<CellCollection cell_collection_t, typename range_collection_t>

void Acts::InPlaceClusterization::addCellRanges	(	const cell_collection_t &	cells,
		range_collection_t &	ranges )

Add element ranges for each cluster in the cell collection to the given range container.

Parameters

cells	labeled and label sorted cell collection
ranges	a range container It is assumed that clusterize was called previously for the given cell collection i.e. the cells are labeled and sorted by label. Will add one cell range per cluster to the given range container. The value type of the range container has to be constructible by two indices the index of the first cell in a cluster and the index of the cell after the last cell of the cluster.

Definition at line 354 of file InPlaceClusterization.h.

                                                                               {
  for_each_cluster(
      cells, [&ranges]([[maybe_unused]] const cell_collection_t &all_cells,
                       unsigned int idx_begin, unsigned int idx_end) {
        ranges.emplace_back(idx_begin, idx_end);
      });
}

addCellRangesAndSort()

template<unsigned int AXIS, CellCollection cell_collection_t, typename range_collection_t>

void Acts::InPlaceClusterization::addCellRangesAndSort	(	cell_collection_t &	cells,
		range_collection_t &	ranges )

Sort the cells of each cluster by one coordinate and add cell ranges to the given range container.

Parameters

cells

labeled and label sorted cell collection

ranges

a range container It is assumed that clusterize was called previously for the given cell collection i.e. the cells are labeled and sorted by label. Will first sort the cells of each cluster by the coordinate of the specified axis and add one cell range per cluster to the given range container. The value type of the range container has to be constructible by two indices the index of the first cell in a cluster and the index of the cell after the last cell of the cluster.

Definition at line 374 of file InPlaceClusterization.h.

                                                      {
  for_each_cluster(cells, [&ranges](cell_collection_t &all_cells,
                                    unsigned int idx_begin,
                                    unsigned int idx_end) {
    auto cluster_range =
        std::span(all_cells.begin() + idx_begin, all_cells.begin() + idx_end);
    using cell_t = typename cell_collection_t::value_type;
    std::ranges::sort(cluster_range, [](const cell_t &a, const cell_t &b) {
      return traits::getCellCoordinate(a, AXIS) <
             traits::getCellCoordinate(b, AXIS);
    });
    ranges.emplace_back(idx_begin, idx_end);
  });
}

clusterize()

template<unsigned int SORT_AXIS, std::unsigned_integral index_t = unsigned int, CellCollection cell_collection_t = std::span<Cell<int, 2, unsigned int> >, typename connection_helper_t = ConnectionHelper<Cell<int, 2, unsigned int> >>

void Acts::InPlaceClusterization::clusterize	(	cell_collection_t &	cells,
		connection_helper_t &&	connection_helper = ConnectionHelper<typename cell_collection_t::value_type, EConnectionType::CommonEdgeOrCorner>{} )

Sort the cell collection in such a way that cells of a cluster are adjacent.

Parameters

cells

the cell collection which will be sorted.

connection_helper

a helper object to test for cell connections. Will sort the cells first by the coordinate of the specified axis to accelerate connection tests. Then associate the same label to connected cells where the label corresponds to the smallest cell index (in the sorted cell collection) of a cluster, where the cells are in ascending order of one of the coordinates Finally will sort the cells by the label in ascending order. As a consequence cells which belong to one cluster are adjacent and have the same label. index_t must be large enough to fit the number of cells in the collection.

Definition at line 291 of file InPlaceClusterization.h.

                                                                       {}) {
  assert(cells.size() <= std::numeric_limits<index_t>::max());
  sortCellsByCoordinate<SORT_AXIS>(cells);
  labelSortedCells<SORT_AXIS, cell_collection_t, index_t>(cells,
                                                          connection_helper);
  groupCellsByLabel(cells);
}

countLabels()

template<CellCollection cell_collection_t, std::unsigned_integral index_t = unsigned int>

std::size_t Acts::InPlaceClusterization::countLabels

(

const cell_collection_t &

cells

)

determine the number of clusters.

It is assumed that clusterize was called previously for the given cell collection i.e. the cells are labeled and sorted by label. It will count the number of different labels do determine the number of clusters in the collection.

Definition at line 309 of file InPlaceClusterization.h.

                                                      {
  assert(cells.size() <= std::numeric_limits<index_t>::max());
  std::size_t nlabels = cells.empty() ? 0 : 1;
  for (index_t idx_a = 1; idx_a < cells.size(); ++idx_a) {
    nlabels +=
        traits::getLabel(cells[idx_a]) != traits::getLabel(cells[idx_a - 1]);
  }
  return nlabels;
}

defaultConnectionHelper()

template<EConnectionType connection_type = EConnectionType::CommonEdgeOrCorner, CellCollection cell_container_t = std::span<Cell<int, 2, unsigned int> >>

auto Acts::InPlaceClusterization::defaultConnectionHelper

(

const cell_container_t &

cells

)

Definition at line 169 of file InPlaceClusterization.h.

                                                                             {
  return ConnectionHelper<typename cell_container_t::value_type,
                          connection_type>{};
}

for_each_cluster()

template<CellCollection cell_collection_t, typename func_t>

void Acts::InPlaceClusterization::for_each_cluster	(	cell_collection_t &	cells,
		func_t	func )

call the given function for each cluster of a label sorted cell collection.

It is assumed that clusterize was called previously for the given cell collection i.e. the cells are labeled and sorted by label. Will call the given function for each cluster, where the function gets a reference to the full cell collection and the begin and end cell index which defines the cell range of a cluster.

Definition at line 326 of file InPlaceClusterization.h.

                                                             {
  if (cells.empty()) {
    return;
  }
  using index_t = decltype(traits::getLabel(cells[0]));
  index_t idx_begin = 0;
  index_t idx = 1;
  for (; idx < cells.size(); ++idx) {
    if (traits::getLabel(cells[idx]) != traits::getLabel(cells[idx - 1])) {
      func(cells, idx_begin, idx);
      idx_begin = idx;
    }
  }
  if (idx_begin < idx) {
    func(cells, idx_begin, idx);
  }
}

groupCellsByLabel()

template<CellCollection cell_collection_t>

void Acts::InPlaceClusterization::groupCellsByLabel

(

cell_collection_t &

cells

)

Sort the cells in ascending order of the asscoiated label.

Definition at line 266 of file InPlaceClusterization.h.

                                                 {
  using cell_t = typename cell_collection_t::value_type;
  // stable sort to retain coordinate ordering
  std::stable_sort(cells.begin(), cells.end(),
                   [](const cell_t &a, const cell_t &b) {
                     return traits::getLabel(a) < traits::getLabel(b);
                   });
}

isConnectedCommonEdge()

template<typename coordinates_t>

bool Acts::InPlaceClusterization::isConnectedCommonEdge

(

const coordinates_t &

coordinates_diff

)

test whether cells are connected considering common edges only.

Parameters

coordinates_diff

absolute values of the differences of the cell coordinates Test whether two cells with the given coordinate differences are connected either horizontally, vertically or are equal.

Definition at line 119 of file InPlaceClusterization.h.

                                                                  {
  int connections = 0;
  for (const auto &a_coordinate_diff : coordinates_diff) {
    connections += a_coordinate_diff;
  }
  return connections <= 1;
}

isConnectedCommonEdgeOrCorner()

template<typename coordinates_t>

bool Acts::InPlaceClusterization::isConnectedCommonEdgeOrCorner

(

const coordinates_t &

coordinates_diff

)

test whether cells are connected considering common corners and edges.

Parameters

coordinates_diff

absolute values of the differences of the cell coordinates Test whether two cells with the given coordinate differences are connected either horizontally, vertically, diagonally or are equal.

Definition at line 106 of file InPlaceClusterization.h.

                                                                          {
  bool connected = true;
  for (const auto &a_coordinate_diff : coordinates_diff) {
    connected &= a_coordinate_diff <= 1;
  }
  return connected;
}

labelSortedCells()

template<unsigned int SORT_AXIS, CellCollection cell_collection_t, std::unsigned_integral index_t = unsigned int, typename connection_helper_t>

void Acts::InPlaceClusterization::labelSortedCells	(	cell_collection_t &	cells,
		connection_helper_t &&	connection_helper )

Label cells which are in ascending order of the coordinate of the given axis.

Parameters

cells	the sorted cell collection that should be labeled.
connection_helper	a helper object to test for cell connections.

Definition at line 192 of file InPlaceClusterization.h.

                                                               {
  using cell_t = typename cell_collection_t::value_type;
  static constexpr std::size_t NDim = traits::getCellDimension<cell_t>();
  static_assert(NDim > 0);
  using label_t = std::remove_cvref_t<decltype(traits::getLabel(cells[0]))>;
  using coordinate_t =
      std::remove_cvref_t<decltype(traits::getCellCoordinate(cells[0], 0u))>;
  static_assert(std::numeric_limits<index_t>::max() >=
                std::numeric_limits<label_t>::max());
  // cells are sorted in the first coordinate
  // thus can stop searching for adjacent cells
  // if distance in the sorted coordinate is too large
  for (index_t idx_a = 0; idx_a < cells.size(); ++idx_a) {
    traits::setLabel(cells[idx_a], idx_a);
    for (index_t idx_b = idx_a; idx_b-- > 0;) {
      // Unnecessary default initialization to satisfy clang-tidy:
      std::array<coordinate_t, NDim> diff{};
      for (unsigned int axis_i = 0; axis_i < NDim; ++axis_i) {
        diff[axis_i] =
            absDifference(traits::getCellCoordinate(cells[idx_a], axis_i),
                          traits::getCellCoordinate(cells[idx_b], axis_i));
      }
 
      if (connection_helper.isConnected(diff)) {
        if (traits::getLabel(cells[idx_a]) < idx_a) {
          // Unnecessary default initialization to satisfy clang-tidy:
          label_t min_label{};
          label_t max_label{};
          if (traits::getLabel(cells[idx_a]) < traits::getLabel(cells[idx_b])) {
            min_label = traits::getLabel(cells[idx_a]);
            max_label = traits::getLabel(cells[idx_b]);
            traits::setLabel(cells[idx_b], min_label);
          } else {
            max_label = traits::getLabel(cells[idx_a]);
            min_label = traits::getLabel(cells[idx_b]);
            traits::setLabel(cells[idx_a], min_label);
          }
          // nothing will be done if the min and the max label are identical
          if (min_label != max_label) {
            // can only encounter cells with label max_label down to index
            // max_label
            for (index_t idx = idx_a; idx-- > max_label;) {
              if (traits::getLabel(cells[idx]) == max_label) {
                traits::setLabel(cells[idx], min_label);
              }
            }
          }
        } else {
          traits::setLabel(cells[idx_a], traits::getLabel(cells[idx_b]));
        }
      } else if (connection_helper.canAbortSearch(diff, SORT_AXIS)) {
        // difference too large in sorted coordinate, there won't be any more
        // candidates for merging. Can abort search for cell idx_a
        break;
      }
    }
  }
}

sortCellsByCoordinate()

template<unsigned int AXIS, CellCollection cell_collection_t, std::size_t NDim = 2, std::unsigned_integral index_t = unsigned int>

void Acts::InPlaceClusterization::sortCellsByCoordinate

(

cell_collection_t &

cells

)

Sort the cells in ascending order of the coordinate of the specified axis.

Definition at line 256 of file InPlaceClusterization.h.

                                                     {
  using cell_t = typename cell_collection_t::value_type;
  std::sort(cells.begin(), cells.end(), [](const cell_t &a, const cell_t &b) {
    return traits::getCellCoordinate(a, AXIS) <
           traits::getCellCoordinate(b, AXIS);
  });
}