-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathdbscan.cpp
More file actions
90 lines (79 loc) · 2.75 KB
/
dbscan.cpp
File metadata and controls
90 lines (79 loc) · 2.75 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include "dbscan.h"
#include <stdexcept>
void DBSCAN::run()
{
int clusterID = 1;
for(auto iter = m_points.cbegin(); iter != m_points.cend(); ++iter)
{
if ( iter->clusterID == UNCLASSIFIED )
{
if ( expandCluster(*iter, clusterID) != FAILURE )
{
clusterID += 1;
}
}
}
}
int DBSCAN::expandCluster(Point point, const int clusterID)
{
vector<int> clusterSeeds = calculateCluster(point);
if ( clusterSeeds.size() < m_minPoints )
{
point.clusterID = NOISE;
return FAILURE;
}
else
{
int index = 0, indexCorePoint = 0;
for(auto iterSeeds = clusterSeeds.cbegin(); iterSeeds != clusterSeeds.cend(); ++iterSeeds)
{
m_points[*iterSeeds].clusterID = clusterID;
if (m_points[*iterSeeds].x == point.x && m_points[*iterSeeds].y == point.y )
{
indexCorePoint = index;
}
++index;
}
clusterSeeds.erase(clusterSeeds.begin()+indexCorePoint);
for( vector<int>::size_type i = 0, n = clusterSeeds.size(); i < n; ++i )
{
const vector<int> clusterNeighors = calculateCluster(m_points[clusterSeeds[i]]);
if ( clusterNeighors.size() >= m_minPoints )
{
for (auto iterNeighors = clusterNeighors.cbegin(); iterNeighors != clusterNeighors.cend(); ++iterNeighors )
{
if(clusterID > 10)
throw std::invalid_argument("Too many clusters! Stop here!\n");
if ( m_points[*iterNeighors].clusterID == UNCLASSIFIED || m_points[*iterNeighors].clusterID == NOISE )
{
if ( m_points[*iterNeighors].clusterID == UNCLASSIFIED )
{
clusterSeeds.push_back(*iterNeighors);
n = clusterSeeds.size();
}
m_points[*iterNeighors].clusterID = clusterID;
}
}
}
}
return SUCCESS;
}
}
const vector<int> DBSCAN::calculateCluster(const Point& point)const
{
int index = 0;
vector<int> clusterIndex;
for(auto iter = m_points.cbegin(); iter != m_points.cend(); ++iter)
{
if ( calculateDistance(point, *iter) <= m_epsilon )
{
clusterIndex.push_back(index);
}
index++;
}
return clusterIndex;
}
inline double DBSCAN::calculateDistance(const Point& pointCore,const Point& pointTarget )const
{
return pow(pointCore.x - pointTarget.x,2) + pow(pointCore.y - pointTarget.y,2);
}