XdCxRhDW54/Service/CgDbScan/Dbsacn/Dbscan.cs

using System.Collections.Generic;
using System.Linq;

namespace Dbscan
{

	/// <summary>
	/// Contains static methods to run the DBSCAN algorithm.
	/// </summary>
	public static class Dbscan
	{
		/// <summary>
		/// Run the DBSCAN algorithm on a collection of points, using the default index
		/// (<see cref="T:Dbscan.ListSpatialIndex`1" />).
		/// </summary>
		/// <typeparam name="T">The type of elements to cluster.</typeparam>
		/// <param name="data">The collection of elements to cluster.</param>
		/// <param name="epsilon">The epsilon parameter to use in the algorithm; used to determine the radius of the circle to find neighboring points.</param>
		/// <param name="minimumPointsPerCluster">The minimum number of points required to create a cluster or to add additional points to the cluster.</param>
		/// <returns>A <see cref="T:Dbscan.ClusterSet`1" /> containing the list of <see cref="T:Dbscan.Cluster`1" />s and a list of unclustered points.</returns>
		/// <remarks>This method is an O(N^2) operation, where N is the Length of the dataset</remarks>
		public static ClusterSet<T> CalculateClusters<T>(IEnumerable<T> data, double epsilon, int minimumPointsPerCluster) where T : IPointData
		{
			return CalculateClusters(new ListSpatialIndex<PointInfo<T>>(data.Select((T p) => new PointInfo<T>(p)).ToList()), epsilon, minimumPointsPerCluster);
		}

		/// <summary>
		/// Run the DBSCAN algorithm on a collection of points, the specified pre-filled <see cref="T:Dbscan.ISpatialIndex`1" />.
		/// </summary>
		/// <typeparam name="T">The type of elements to cluster.</typeparam>
		/// <param name="index">The collection of elements to cluster.</param>
		/// <param name="epsilon">The epsilon parameter to use in the algorithm; used to determine the radius of the circle to find neighboring points.</param>
		/// <param name="minimumPointsPerCluster">The minimum number of points required to create a cluster or to add additional points to the cluster.</param>
		/// <returns>A <see cref="T:Dbscan.ClusterSet`1" /> containing the list of <see cref="T:Dbscan.Cluster`1" />s and a list of unclustered points.</returns>
		public static ClusterSet<T> CalculateClusters<T>(ISpatialIndex<PointInfo<T>> index, double epsilon, int minimumPointsPerCluster) where T : IPointData
		{
			List<PointInfo<T>> list = index.Search().ToList();
			List<Cluster<T>> list2 = new List<Cluster<T>>();
			foreach (PointInfo<T> item in list)
			{
				if (!item.Visited)
				{
					item.Visited = true;
					IPointData p2 = item;
					IReadOnlyList<PointInfo<T>> readOnlyList = index.Search(in p2, epsilon);
					if (readOnlyList.Count >= minimumPointsPerCluster)
					{
						list2.Add(BuildCluster(index, item, readOnlyList, epsilon, minimumPointsPerCluster));
					}
				}
			}
			return new ClusterSet<T>
			{
				Clusters = list2,
				UnclusteredObjects = (from p in list
									  where !p.Clustered
									  select p.Item).ToList()
			};
		}

		private static Cluster<T> BuildCluster<T>(ISpatialIndex<PointInfo<T>> index, PointInfo<T> point, IReadOnlyList<PointInfo<T>> neighborhood, double epsilon, int minimumPointsPerCluster) where T : IPointData
		{
			List<T> list = new List<T> { point.Item };
			point.Clustered = true;
			Queue<PointInfo<T>> queue = new Queue<PointInfo<T>>(neighborhood);
			while (queue.Any())
			{
				PointInfo<T> pointInfo = queue.Dequeue();
				if (!pointInfo.Visited)
				{
					pointInfo.Visited = true;
					IPointData p = pointInfo;
					IReadOnlyList<PointInfo<T>> readOnlyList = index.Search(in p, epsilon);
					if (readOnlyList.Count >= minimumPointsPerCluster)
					{
						foreach (PointInfo<T> item in readOnlyList)
						{
							queue.Enqueue(item);
						}
					}
				}
				if (!pointInfo.Clustered)
				{
					pointInfo.Clustered = true;
					list.Add(pointInfo.Item);
				}
			}
			return new Cluster<T>
			{
				Objects = list
			};
		}
	}
}