k-means.cpp

struct Cluster
{
	Vector2 m_meanPosition;
	std::vector<Vector2> m_points;
	Color m_colour;
};

void InitializeClusters(std::vector<Vector2>& dataPoints, std::vector<Cluster>& clusters)
{
	// create clusters from the given data points.
	for (int i = 0; i < dataPoints.size(); i++)
	{
		Vector2& dataPointPosition = dataPoints[i];
		
		// find the closest cluster centroid.
		int clusterIndex;
		float closestDistance;
		for (int k = 0; k < clusters.size(); k++)
		{
			Cluster currentCluster = clusters[k];
			
			float distance = Vector2Distance(dataPointPosition, currentCluster.m_meanPosition);
			
			if (k == 0)
			{
				clusterIndex = k;
				closestDistance = distance;
			}
			else
			{
				if (distance < closestDistance)
				{
					clusterIndex = k;
					closestDistance = distance;
				}
			}
		}
		
		// add this point to the cluster.
		clusters[clusterIndex].m_points.push_back(dataPointPosition);
	}
}

void RunClustering(std::vector<Vector2>& dataPoints, std::vector<Cluster>& clusters)
{
	//
	// iteration 1
	//
	// create new mean positions.
	for (auto iter = clusters.begin(); iter != clusters.end();)
	{
		Vector2 centroid;
		centroid.x = 0.0;
		centroid.y = 0.0;
		
		for (int i = 0; i < iter->m_points.size(); i++)
		{
			centroid = Vector2Add(centroid, iter->m_points[i]);
		}
		
		Vector2 centroidPosition = Vector2Divide(centroid, iter->m_points.size());
		
		
		iter->m_points.clear(); // clear the positions at this cluster to re-use the array in the next block
		
		if (isnan(centroidPosition.x) || isnan(centroidPosition.y)) // if there are no points to cluster then remove it.
		{
			iter = clusters.erase(iter);
		}
		else
		{
			iter->m_meanPosition = centroidPosition;
			iter++;
		}
		
	}
	
	// re-create clusters again.
	for (int i = 0; i < dataPoints.size(); i++)
	{
		Vector2& dataPointPosition = dataPoints[i];
		
		// find the closest cluster centroid.
		int clusterIndex;
		float closestDistance;
		for (int k = 0; k < clusters.size(); k++)
		{
			Cluster currentCluster = clusters[k];
			
			float distance = Vector2Distance(dataPointPosition, currentCluster.m_meanPosition);
			
			if (k == 0)
			{
				clusterIndex = k;
				closestDistance = distance;
			}
			else
			{
				if (distance < closestDistance)
				{
					clusterIndex = k;
					closestDistance = distance;
				}
			}
		}
		
		// add this point to the cluster.
		clusters[clusterIndex].m_points.push_back(dataPointPosition);
	}
}