TrigVSI::DBScan< pointType > Class Template Reference

Class for operating DBSCAN clustering. More...

#include <DBScan.h>

Collaboration diagram for TrigVSI::DBScan< pointType >:

Public Types
using	RegionFunc = std::function< std::vector< pointType >(const pointType &, double)>
	Function type for region query function. More...

Public Member Functions
	DBScan (const std::unordered_set< pointType > &, RegionFunc)
	Normal Constructor. More...
	DBScan ()
	Default constructor. More...
	~DBScan ()
DBScan &	operator= (DBScan &&) noexcept=default
	Move assignment operator. More...
	DBScan (DBScan &&) noexcept=default
	Move constructor. More...
std::vector< Cluster< pointType > >	getClusters () const
	Retrun the list of clusters along with noise clusters. More...
size_t	nClusters () const
const Cluster< pointType > &	getCluster (size_t) const
	Retrieve cluster. More...
void	clusterize (double, size_t)
	Generate clusters with DBSCAN algorithim. More...

Private Attributes
RegionFunc	m_regionQuery
std::unordered_map< pointType, bool >	m_pointsVisited
std::vector< Cluster< pointType > >	m_clusters
std::unordered_set< pointType >	m_noises
std::vector< Cluster< pointType > >	m_noisesCluster

Detailed Description

template<typename pointType>
class TrigVSI::DBScan< pointType >

Class for operating DBSCAN clustering.

Pass set of points on construction, then execute clusterize() once. Set of points can only be read on construction so you need to make new DBSCAN instance when you want to add new points.

Definition at line 43 of file DBScan.h.

Member Typedef Documentation

RegionFunc

template<typename pointType >

using TrigVSI::DBScan< pointType >::RegionFunc = std::function<std::vector<pointType>(const pointType&, double)>

Function type for region query function.

Definition at line 45 of file DBScan.h.

Constructor & Destructor Documentation

DBScan() [1/3]

template<typename pointType >

TrigVSI::DBScan< pointType >::DBScan	(	const std::unordered_set< pointType > &	set,
		RegionFunc	regionQuery
	)

Normal Constructor.

Parameters

[in]	set	Set of points to be clustered.
[in]	regionQuery	Region query function, which defines the algorithm to pick points nearby.

Definition at line 83 of file DBScan.h.

                                                                                        :
m_regionQuery(regionQuery)
{
   m_pointsVisited.clear();
   for (const auto& point : set) {
      m_pointsVisited.emplace(point, false);
   }
}

DBScan() [2/3]

template<typename pointType >

TrigVSI::DBScan< pointType >::DBScan

Default constructor.

Definition at line 97 of file DBScan.h.

{
 
}

~DBScan()

template<typename pointType >

TrigVSI::DBScan< pointType >::~DBScan ( )

inline

Definition at line 48 of file DBScan.h.

{};

DBScan() [3/3]

template<typename pointType >

TrigVSI::DBScan< pointType >::DBScan ( DBScan< pointType > &&  )

defaultnoexcept

Move constructor.

Member Function Documentation

clusterize()

template<typename pointType >

void TrigVSI::DBScan< pointType >::clusterize	(	double	eps,
		size_t	minN
	)

Generate clusters with DBSCAN algorithim.

Parameters

[in]	eps	Radius of region to find neighbor points.
[in]	minN	Threshold to determine point as core.

Definition at line 142 of file DBScan.h.

{
   m_clusters.clear();
   m_noisesCluster.clear();
   for (auto& pair : m_pointsVisited) {
      const pointType& point = pair.first;
 
      if ( pair.second ) continue;  // Continue when the point is visited
      pair.second = true;           // Set the point as visited
      std::vector<pointType> neighbor_points = m_regionQuery(point, eps);
      if ( neighbor_points.size() < minN ) {
         m_noises.emplace(point);
         continue;
      }
 
      m_clusters.emplace_back( std::vector<pointType>{point} );
      Cluster<pointType>& cls = *(--m_clusters.end());
 
      for (size_t i = 0; i < neighbor_points.size(); i++) {
         const auto& q = neighbor_points[i];
 
         // Check if q is labeled as noise
         // If so, remove q from noise lists and add q to cluster
         auto q_itr_noise = m_noises.find(q);
         if ( q_itr_noise != m_noises.end() ) {
            m_noises.erase(q_itr_noise);
            cls.Points().emplace_back(q);
         }
 
         // Check if q had been visited before
         // If visited, q is already labeled as a noise or added to other cluster so skip it
         // If not visited, label q as visited and add it to cluster
         auto q_itr = m_pointsVisited.find(q);
         if ( q_itr == m_pointsVisited.end() ) continue;
         if ( q_itr->second ) continue;
         q_itr->second = true;
         cls.Points().emplace_back(q);
 
         std::vector<pointType> q_neighbor_points = m_regionQuery(q, eps);
         if ( q_neighbor_points.size() >= minN ) neighbor_points.insert( neighbor_points.end(), q_neighbor_points.begin(), q_neighbor_points.end() );
      }
 
   }
 
   // Convert noises to one point clusters
   for (const auto& q : m_noises) {
      m_noisesCluster.emplace_back( std::vector<pointType>{q} );
   }
}

getCluster()

template<typename pointType >

const Cluster< pointType > & TrigVSI::DBScan< pointType >::getCluster ( size_t  icls ) const

inline

Retrieve cluster.

Parameters

[in]

icls

Index of the cluster.

Return different type of clusters depending on icls.

• icls < size of cluster list; Return cluster
• size of cluster list <= icls < (size of cluster list) + (size of noise list); Return cluster made from (icls - size of cluster list)th noise.

Definition at line 128 of file DBScan.h.

{
   const Cluster<pointType>& cls_tmp = ( icls < m_clusters.size() )? m_clusters[icls] : m_noisesCluster[icls-m_clusters.size()];
   return cls_tmp;
}

getClusters()

template<typename pointType >

std::vector< Cluster< pointType > > TrigVSI::DBScan< pointType >::getClusters

inline

Retrun the list of clusters along with noise clusters.

Definition at line 107 of file DBScan.h.

{
   auto tmp = m_clusters;
   const auto& tmp_noise = m_noisesCluster;
   tmp.insert( tmp.end(), tmp_noise.begin(), tmp_noise.end() );
   return tmp;
}

nClusters()

template<typename pointType >

size_t TrigVSI::DBScan< pointType >::nClusters ( ) const

inline

Definition at line 54 of file DBScan.h.

{ return m_clusters.size() + m_noisesCluster.size(); };

operator=()

template<typename pointType >

DBScan& TrigVSI::DBScan< pointType >::operator= ( DBScan< pointType > &&  )

defaultnoexcept

Move assignment operator.

Member Data Documentation

m_clusters

template<typename pointType >

std::vector<Cluster<pointType> > TrigVSI::DBScan< pointType >::m_clusters

private

Definition at line 62 of file DBScan.h.

m_noises

template<typename pointType >

std::unordered_set<pointType> TrigVSI::DBScan< pointType >::m_noises

private

Definition at line 63 of file DBScan.h.

m_noisesCluster

template<typename pointType >

std::vector<Cluster<pointType> > TrigVSI::DBScan< pointType >::m_noisesCluster

private

Definition at line 64 of file DBScan.h.

m_pointsVisited

template<typename pointType >

std::unordered_map<pointType, bool> TrigVSI::DBScan< pointType >::m_pointsVisited

private

Definition at line 61 of file DBScan.h.

m_regionQuery

template<typename pointType >

RegionFunc TrigVSI::DBScan< pointType >::m_regionQuery

private

Definition at line 60 of file DBScan.h.

---

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

• DBScan.h