`ArborX::dbscan`¶

Defined in header <ArborX_DBSCAN.hpp>

template <typename ExecutionSpace, typename Primitives, typename Labels>
void dbscan(ExecutionSpace const &space, Primitives const &primitives,
            double eps, int core_min_size, Labels &labels);

The free function ArborX::dbscan performs DBSCAN (Density-Based Spatial Clustering of Applications with Noise) clustering from a set of points.

Parameters¶

space: the execution space.
primitives: points to cluster, accessed through ArborX::AccessTraits.
eps: The eps parameter in the DBSCAN algorithm, corresponding to the maximum distance between two objects to be considered in the neighborhood of each other.
core_min_size: The minPts parameter in the DBSCAN algorithm, corresponding to the number of objects in the neighborhood for a point to be considered a core point.
labels: a one-dimensional Kokkos view of an integral type to store the labels

Returns¶

Example¶

#include <ArborX_DBSCAN.hpp>

#include <iostream>

int main(int argc, char *argv[])
{
  Kokkos::ScopeGuard guard(argc, argv);

  Kokkos::View<ArborX::Point<3> *> cloud("point_cloud", 9);
  auto cloud_host = Kokkos::create_mirror_view(cloud);
  //     0 1 2 3 4
  //    ----------
  // 3 |     0 7
  // 2 |     5 6
  // 1 | 4 3
  // 0 | 1 2     8
  cloud_host[0] = {3.f, 2.f, 0.f};
  cloud_host[1] = {0.f, 0.f, 0.f};
  cloud_host[2] = {0.f, 1.f, 0.f};
  cloud_host[3] = {1.f, 1.f, 0.f};
  cloud_host[4] = {1.f, 0.f, 0.f};
  cloud_host[5] = {2.f, 2.f, 0.f};
  cloud_host[6] = {2.f, 3.f, 0.f};
  cloud_host[7] = {3.f, 3.f, 0.f};
  cloud_host[8] = {4.f, 0.f, 0.f};
  Kokkos::deep_copy(cloud, cloud_host);

  using execution_space = decltype(cloud)::execution_space; // where to execute code
  Kokkos::View<int *> labels("labels", 0);
  ArborX::dbscan(execution_space{}, cloud, 1.2, 2, labels);

  auto labels_host = Kokkos::create_mirror_view_and_copy(Kokkos::HostSpace{}, labels);
  for (int i = 0; i < (int)labels_host.size(); ++i)
    std::cout << labels_host(i) << " ";
  std::cout << std::endl;

  return 0;
}

Output

0 1 1 1 1 0 0 0 -1

Notes¶

The resulting labels are not guaranteed to be identical between the runs. If a border point is connected to core points belonging to different clusters, it may be assigned to either of them.

References¶

Ester, M., H. P. Kriegel, J. Sander, and X. Xu, “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise”. In: Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, Portland, OR, AAAI Press, pp. 226-231. 1996

ArborX::dbscan¶