www.pudn.com > cluster_KM_DS.rar > Dbscan.cpp

// Dbscan.cpp: implementation of the Dbscan class. 
// 
////////////////////////////////////////////////////////////////////// 
 
#include "stdafx.h" 
#include "cluster.h" 
#include "Dbscan.h" 
 
#ifdef _DEBUG 
#undef THIS_FILE 
static char THIS_FILE[]=__FILE__; 
#define new DEBUG_NEW 
#endif 
 
////////////////////////////////////////////////////////////////////// 
// Construction/Destruction 
////////////////////////////////////////////////////////////////////// 
 
Dbscan::Dbscan() 
{ 
	dis = NULL; 
	C = NULL; 
	p = NULL; 
} 
 
void Dbscan::set(int _n,int _Eps,int _Minpts) 
{ 
    dis = new int * [_n]; 
	for(int i = 0; i < _n; i++) 
		dis[i] = new int [_n]; 
	for(int j = 0; j <_n; j++) 
		for(int k = 0; k <_n; k++) 
			dis[j][k] = 0 ; 
    Eps = _Eps; 
	N = _n; 
	Minpts = _Minpts; 
	p = new point[_n]; 
	C = new int[_n]; 
	for(int l = 0 ; l < _n ; l++) 
		C[l] = -2; 
	Class = 0; 
} 
 
void Dbscan::init_dis() 
{ 
	int i,j; 
	for(i = 0 ; i < N; i++) 
		for(j = 0 ; j < N; j++) 
			if( distance(p[i],p[j]) <= Eps*Eps ) 
				dis[i][j] = 1; 
} 
 
Dbscan::~Dbscan() 
{ 
	if( p ) 
		delete [] p; 
	if( C ) 
		delete [] C; 
	if( dis ) 
	{ 
		for(int i = 0; i < N; i++) 
			delete []dis[i]; 
		delete [] dis; 
	} 
} 
 
long Dbscan::distance(point p1,point p2) 
{ 
	long dis =  
		(p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y); 
	return dis; 
} 
 
bool Dbscan::Core(int i) 
{ 
	int sum = 0 ; 
	for(int j = 0 ; j < N; j++) 
		sum += dis[i][j]; 
	if(sum >= Minpts ) 
		return true; 
	return false; 
} 
 
int Dbscan::visit_next() 
{ 
	for(int i = 0; i < N ; i++) 
		if( C[i] == -2 ) 
			return i; 
	return -1 ; 
} 
 
void Dbscan::Db_scan() 
{ 
	init_dis(); 
	time_t t;   
	srand((unsigned) time(&t));   
	int p = rand()%N; 
	C_n q(N); 
	do{ 
		if( Core(p) ) 
		{ 
			q.i = 0;  
			q.j = 0 ; 
			q.Id[ q.j++ ] = p; 
			C[p] = Class; 
			for(int i = 0 ; i < N ; i ++) 
				if( dis[p][i] == 1 && C[i] < 0 ) 
				{ 
					q.Id[ q.j++ ] = i; 
					C[i] = Class; 
				}  
			while( q.i < q.j ) 
			{ 
				if( Core( q.Id[ q.i ] ) ) 
					for( int j = 0 ; j < N; j++) 
						if( dis[ q.Id[ q.i ] ][j] == 1 && C[ j ]< 0 ) 
						{ 
							q.Id[ q.j++ ] = j; 
							C[ j ] = Class; 
						} 
				q.i++; 
			} 
			Class++; 
		} 
		else 
			C[ p ] = -1;  //noise point 
		p = visit_next(); 
		if( p < 0 ) 
			break; 
	}while( true ); 
}