Acts::DBScan< kDims, scalar_t, kLeafSize > Class Template Reference

A general implementation of an N dimensional DBScan clustering algorithm. More...

#include <Acts/Utilities/DBScan.hpp>

Public Types
using	Pair = std::pair<Point, std::size_t>
	Type alias for pair of point coordinates with unique identifier.
using	Point = std::array<scalar_t, kDims>
	Type alias for coordinates of points in N-dimensional space.
using	Tree = KDTree<kDims, std::size_t, scalar_t, std::array, kLeafSize>
	Type alias for KDTree used for neighbor search during clustering.
using	VectorPairs = std::vector<Pair>
	Type alias for vector of coordinate-ID pairs.
using	VectorPoints = std::vector<Point>
	Type alias for vector of coordinate points.

Public Member Functions
	DBScan ()=delete
	DBScan (scalar_t epsilon=1.0, std::size_t minPoints=1, bool onePointCluster=false)
	Construct the DBScan algorithm with a given epsilon and minPoints.
int	cluster (const VectorPoints &inputPoints, std::vector< int > &clusteredPoints)
	Cluster the input points.

Detailed Description

template<std::size_t kDims, typename scalar_t = double, std::size_t kLeafSize = 4>
class Acts::DBScan< kDims, scalar_t, kLeafSize >

A general implementation of an N dimensional DBScan clustering algorithm.

This is a general implementation of an N dimensional DBScan clustering algorithm. The DBScan algorithm uses density information to cluster together points that are close to each other.

For each point, we will look for the neighbours that are within the epsilon radius. If the number of neighbours is greater than the minimum number of points, we will start a new cluster and assign the current point to it. We will then look for the neighbours of the neighbours and assign them to the current cluster if they are not already assigned to a cluster. If the neighbours have itself more than the minimum number of points as neighbours, we will repeat the process on those neighbours.

To speed up the search for the neighbours, we use the KDTree implemented in ACTS. It performs a range search in the orthogonal hypercube with a length of 2 epsilon. An extra cut is used to only keep the neighbours that are within the epsilon radius.

Template Parameters

kDims	The number of dimensions.
scalar_t	The scalar type used to construct position vectors.
kLeafSize	The maximum number of points in a leaf node of the KDTree.

Member Typedef Documentation

Pair

template<std::size_t kDims, typename scalar_t = double, std::size_t kLeafSize = 4>

using Acts::DBScan< kDims, scalar_t, kLeafSize >::Pair = std::pair<Point, std::size_t>

Type alias for pair of point coordinates with unique identifier.

Point

template<std::size_t kDims, typename scalar_t = double, std::size_t kLeafSize = 4>

using Acts::DBScan< kDims, scalar_t, kLeafSize >::Point = std::array<scalar_t, kDims>

Type alias for coordinates of points in N-dimensional space.

Tree

template<std::size_t kDims, typename scalar_t = double, std::size_t kLeafSize = 4>

using Acts::DBScan< kDims, scalar_t, kLeafSize >::Tree = KDTree<kDims, std::size_t, scalar_t, std::array, kLeafSize>

Type alias for KDTree used for neighbor search during clustering.

VectorPairs

template<std::size_t kDims, typename scalar_t = double, std::size_t kLeafSize = 4>

using Acts::DBScan< kDims, scalar_t, kLeafSize >::VectorPairs = std::vector<Pair>

Type alias for vector of coordinate-ID pairs.

VectorPoints

template<std::size_t kDims, typename scalar_t = double, std::size_t kLeafSize = 4>

using Acts::DBScan< kDims, scalar_t, kLeafSize >::VectorPoints = std::vector<Point>

Type alias for vector of coordinate points.

Constructor & Destructor Documentation

DBScan() [1/2]

template<std::size_t kDims, typename scalar_t = double, std::size_t kLeafSize = 4>

Acts::DBScan< kDims, scalar_t, kLeafSize >::DBScan ( )

delete

DBScan() [2/2]

template<std::size_t kDims, typename scalar_t = double, std::size_t kLeafSize = 4>

Acts::DBScan< kDims, scalar_t, kLeafSize >::DBScan ( scalar_t epsilon = 1.0, std::size_t minPoints = 1, bool onePointCluster = false )

explicit

Construct the DBScan algorithm with a given epsilon and minPoints.

Parameters

epsilon	The epsilon radius used to find the neighbours.
minPoints	The minimum number of points to form a cluster.
onePointCluster	If true, all the noise points are considered as individual one point clusters.

Member Function Documentation

cluster()

template<std::size_t kDims, typename scalar_t = double, std::size_t kLeafSize = 4>

int Acts::DBScan< kDims, scalar_t, kLeafSize >::cluster	(	const VectorPoints &	inputPoints,
		std::vector< int > &	clusteredPoints )

Cluster the input points.

This function implements the main loop of the DBScan algorithm. It loops over all the point and will try to start new cluster if it finds points that have yet to be clustered.

Parameters

inputPoints	The input points to cluster.
clusteredPoints	Vector containing the cluster ID of each point.

Returns

The number of clusters (excluding noise if onePointCluster==False).