HitOrderer Class Reference

Sorts CDC hits spatially using KD-tree nearest neighbor traversal. More...

#include <Utils.h>

Public Member Functions
	HitOrderer ()=default
	Constructor.
	~HitOrderer ()=default
	Destructor.

Static Public Member Functions
static std::vector< int >	orderHits (const double startingX, const double startingY, std::vector< KDTHit > kdtHits)
	Sort hits spatially based on proximity to a starting position.

Static Private Member Functions
static KDTNode *	buildKDTree (std::vector< KDTHit >::iterator begin, std::vector< KDTHit >::iterator end, const int depth, KDTNodePool &pool, const size_t insertionSortThreshold=10)
	Recursively builds a balanced KD-tree from a range of KDTHits.
template<typename Iterator, typename Compare>
static void	insertionSort (Iterator begin, Iterator end, Compare cmp)
	Sorts a small range using insertion sort for performance.
static void	freeKDTree (KDTNode *node)
	Recursively frees all nodes in a KD-tree.
static void	nearestNeighbor (const KDTNode *node, const KDTHit &query, KDTHit &best, double &bestDist)
	Finds the closest unused neighbor to a query hit in the KD-tree.
static bool	markUsed (KDTNode *node, const KDTHit &hit)
	Marks a KD-tree node as used if its hit index matches the given hit.

Detailed Description

Sorts CDC hits spatially using KD-tree nearest neighbor traversal.

Constructs a 2D KD-tree from hit coordinates and performs iterative nearest-neighbor selection starting from a reference point to obtain a spatially coherent hit ordering.

Definition at line 123 of file Utils.h.

Member Function Documentation

buildKDTree()

KDTNode * buildKDTree ( std::vector< KDTHit >::iterator begin, std::vector< KDTHit >::iterator end, const int depth, KDTNodePool & pool, const size_t insertionSortThreshold = 10 )

staticprivate

Recursively builds a balanced KD-tree from a range of KDTHits.

The KD-tree is built by recursively selecting median splits along alternating axes (x, y), using either std::nth_element or insertion sort for small partitions.

Parameters

begin	Iterator to the beginning of the KDTHit range.
end	Iterator to the end of the KDTHit range.
depth	Current tree depth, used to alternate axis.
pool	Object pool used to allocate KD-tree nodes.
insertionSortThreshold	Switch to insertion sort for small ranges.

Returns

Pointer to the root node of the constructed KD-tree.

Definition at line 57 of file Utils.cc.

{
  if (begin >= end)
    return nullptr;
 
  // Alternate splitting dimension with each level of recursion
  const int dim = depth % 2;
  const auto cmp = [dim](const KDTHit & a, const KDTHit & b) {
    return (dim == 0) ? a.x < b.x : a.y < b.y;
  };
 
  const size_t n = std::distance(begin, end);
  const auto mid  = begin + n / 2;  // Median element becomes the node's pivot
 
  if (n < insertionSortThreshold) {
    // Full sort for small ranges: cheaper than nth_element + recursion overhead
    HitOrderer::insertionSort(begin, end, cmp);
  } else {
    // Partial sort: guarantees *mid is the true median, rest unsorted
    std::nth_element(begin, mid, end, cmp);
  }
 
  // Claim a node from the pool and populate it with the median hit
  KDTNode* node = pool.allocate();
  node->hit = *mid;
  node->used = false;  // Will be set to true once this hit is added to the track
  node->dim = dim;
 
  // Recurse on the left (< median) and right (> median) sub-ranges
  node->left =  HitOrderer::buildKDTree(begin, mid, depth + 1, pool);
  node->right = HitOrderer::buildKDTree(mid + 1, end, depth + 1, pool);
 
  return node;
}

freeKDTree()

void freeKDTree ( KDTNode * node )

staticprivate

Recursively frees all nodes in a KD-tree.

Parameters

node	Root node of the KD-tree to deallocate.

Definition at line 150 of file Utils.cc.

{
  if (!node)
    return;
  HitOrderer::freeKDTree(node->left);
  HitOrderer::freeKDTree(node->right);
  delete node;
}

insertionSort()

template<typename Iterator, typename Compare>

void insertionSort ( Iterator begin, Iterator end, Compare cmp )

inlinestaticprivate

Sorts a small range using insertion sort for performance.

Template Parameters

Iterator	Type of iterator.
Compare	Comparison function type.

Parameters

begin	Iterator to the beginning of the range.
end	Iterator to the end of the range.
cmp	Comparator function for sorting.

Definition at line 47 of file Utils.cc.

{
  for (Iterator i = begin; i != end; ++i) {
    // Bubble element i leftward until the sequence is locally sorted
    for (Iterator j = i; j != begin && cmp(*j, *(j - 1)); --j) {
      std::iter_swap(j, j - 1);
    }
  }
}

markUsed()

bool markUsed ( KDTNode * node, const KDTHit & hit )

staticprivate

Marks a KD-tree node as used if its hit index matches the given hit.

Used to ensure that hits are not reused in subsequent nearest-neighbor queries.

Parameters

node	Root of the KD-tree.
hit	Hit to match by index.

Returns

True if a matching node was found and marked as used.

Definition at line 126 of file Utils.cc.

{
  if (!node)
    return false;
 
  // Found the matching node: mark and return
  if (node->hit.hitIndex == hit.hitIndex) {
    node->used = true;
    return true;
  }
 
  // Descend into the child whose partition contains the hit's coordinate
  const int    dim  = node->dim;
  const double hVal = (dim == 0) ? hit.x      : hit.y;
  const double nVal = (dim == 0) ? node->hit.x : node->hit.y;
 
  KDTNode* first  = (hVal < nVal) ? node->left  : node->right;
  KDTNode* second = (hVal < nVal) ? node->right : node->left;
 
  // If the primary branch fails (e.g. due to equal coordinates on the
  // splitting axis), fall back to the other child rather than giving up
  return markUsed(first, hit) or markUsed(second, hit);
}

nearestNeighbor()

void nearestNeighbor ( const KDTNode * node, const KDTHit & query, KDTHit & best, double & bestDist )

staticprivate

Finds the closest unused neighbor to a query hit in the KD-tree.

The function recursively traverses the KD-tree and updates the best match and distance if a closer unused hit is found.

Parameters

node	Root of the KD-tree.
query	Query hit to compare against.
best	Best match found so far (output).
bestDist	Squared distance to the best match (output).

Definition at line 93 of file Utils.cc.

{
  if (!node)
    return;
 
  // Evaluate the current node if it hasn't been assigned to the track yet
  if (!node->used) {
    const double d = query.squaredDistanceTo(node->hit);
    if (d < bestDist) {
      bestDist = d;
      best = node->hit;
    }
  }
 
  // Determine which child subtree lies on the same side as the query point
  const int dim = node->dim;
  const double qVal = (dim == 0) ? query.x : query.y;
  const double nVal = (dim == 0) ? node->hit.x : node->hit.y;
 
  KDTNode* near = (qVal < nVal) ? node->left : node->right;
  KDTNode* far  = (qVal < nVal) ? node->right : node->left;
 
  // Always descend into the near subtree first (more likely to improve bestDist)
  nearestNeighbor(near, query, best, bestDist);
 
  // Pruning: search only the "far" side if the distance to the
  // splitting plane is less than the best distance found so far
  const double diff = qVal - nVal;
  if ((diff * diff) < bestDist) {
    nearestNeighbor(far, query, best, bestDist);
  }
}

orderHits()

std::vector< int > orderHits ( const double startingX, const double startingY, std::vector< KDTHit > kdtHits )

static

Sort hits spatially based on proximity to a starting position.

Builds a KD-tree from the input position and performs an iterative nearest-neighbor traversal to generate a spatially ordered list of hit indices.

Parameters

startingX	Starting X position
startingY	Starting Y position
kdtHits	Vector of hits to order

Returns

Vector of hit indices sorted by spatial proximity to the start position.

Definition at line 159 of file Utils.cc.

{
  // Return an empty vector if kdtHits is empty
  if (kdtHits.empty())
    return std::vector<int> {};
 
  // Build a KD-tree over the hits; pool size equals number of hits (one node per hit)
  KDTNodePool pool(kdtHits.size());
  KDTNode* root = buildKDTree(kdtHits.begin(), kdtHits.end(), 0, pool);
 
  // Define the starting hit (-1 here means it's not a real hit)
  const KDTHit startingHit{startingX, startingY, -1};
 
  // Linear scan to find the real hit closest to the starting position.
  // A KD-tree query is not used here because the starting position is not in the tree,
  // and the list is typically short enough that a scan is negligible.
  const KDTHit& firstHit = *std::min_element(kdtHits.begin(), kdtHits.end(),
  [&startingHit](const KDTHit & a, const KDTHit & b) {
    return a.squaredDistanceTo(startingHit) < b.squaredDistanceTo(startingHit);
  });
 
  // Mark the first hit as consumed so it won't be returned by nearestNeighbor
  markUsed(root, firstHit);
 
  // Prepare the output
  std::vector<int> sortedIndices;
  sortedIndices.reserve(kdtHits.size());
  sortedIndices.push_back(firstHit.hitIndex);
 
  // Greedy chain: at each step find the nearest unused hit to the current one
  KDTHit currentHit = firstHit;
  for (size_t i = 1; i < kdtHits.size(); ++i) {
    KDTHit bestNeighbor;
    double bestNeighborDist = std::numeric_limits<double>::max();
    nearestNeighbor(root, currentHit, bestNeighbor, bestNeighborDist);
 
    // If no unused hit was found (all remaining are marked used), stop early
    if (bestNeighborDist == std::numeric_limits<double>::max())
      break;
 
    currentHit = bestNeighbor;
    sortedIndices.push_back(currentHit.hitIndex);
    markUsed(root, currentHit);  // Prevent this hit from being selected again
  }
 
  return sortedIndices;
}

---

The documentation for this class was generated from the following files:

• tracking/gnnFinder/include/Utils.h
• tracking/gnnFinder/src/Utils.cc