ComputeDBSCANClustering Module

Module contents

template<class SearchBoxT, class PointIteratorT, class OutputIteratorT>
int tracktable::cluster_with_dbscan(PointIteratorT input_begin, PointIteratorT input_end, SearchBoxT search_box_half_span, int minimum_cluster_size, OutputIteratorT output_sink)

Generate cluster labels for a set of points.

This function runs DBSCAN on a list of points and returns its results as a vector of integers, one for each input point.

When you call cluster_with_dbscan you must indicate the type of point (and thus the coordinate space) that you want to use for the clustering. This lets you choose (for example) to run in Cartesian space rather than longitude/latitude space if you’re sure your points don’t run into the poles or the longitude discontinuity at +/= 180.

Example:

typedef tracktable::cartesian2d::BasePoint point2d;
std::vector<tracktable::cartesian2d::BasePoint> my_points;
std::vector<std::pair<int, int>> cluster_labels;
point2d search_box(0.5, 0.5);
int min_cluster_size = 10;


int num_clusters = cluster_with_dbscan<point2d>(
   my_points.begin(),
   my_points.end(),
   search_box,
   min_cluster_size,
   std::back_inserter(cluster_labels)
);

The search box must be specified in the coordinate system in which you want to do the clustering.

You can also pass in points as a std::pair<MyPoint, Foo> where Foo is your own arbitrary ID. In that case, the returned labels will be (Foo, int).

Parameters:

• input_begin – [in] Iterator for beginning of input points

• input_end – [in] Iterator for end of input points

• search_box_half_span – [in] Distance defining “nearby” in all dimensions

• minimum_cluster_size – [in] Minimum number of neighbors for core points

• output_sink – [out] (Vertex ID, Cluster ID) for each point

Returns:

Number of clusters discovered

template<typename ClusterLabelIteratorT, typename OutputIteratorT>
int tracktable::build_cluster_membership_lists(ClusterLabelIteratorT label_begin, ClusterLabelIteratorT label_end, OutputIteratorT output_membership_lists)

Convert cluster labels into cluster membership lists

The label output from cluster_with_dbscan is a list of (vertex_id, cluster_id) pairs. It is often useful to have cluster membership represented instead as lists of the vertices that belong to each cluster. This function converts a list of IDs to a list of members. The output will be saved as a sequence of std::vectors written in order of ascending cluster ID.

Example:

typedef std::pair<my_point, my_id> labeled_point_type;
tyepdef std::pair<my_id, int> cluster_label_type;
std::vector<labeled_point_type> my_labeled_points;
std::vector<cluster_label_type> cluster_labels;

int num_clusters = tracktable::cluster_with_dbscan(
   my_labeled_points.begin(),
   my_labeled_points.end(),
   search_box,
   minimum_cluster_size,
   std::back_inserter(cluster_labels)
);

typedef std::vector<my_id> cluster_member_list_type;
std::vector<cluster_member_list_type> membership_lists;

tracktable::build_cluster_membership_lists(
  cluster_labels.begin(),
  cluster_labels.end(),
  std::back_inserter(membership_lists)
);

Parameters:

• label_begin – [in] Iterator for beginning of DBSCAN cluster labels

• label_end – [in] Iterator for end of DBSCAN cluster labels

• output_membership_lists – [out] (Vertex ID, Cluster ID) for each point

Returns:

Number of clusters discovered