| | | 1 | | using System.Collections.Generic; |
| | | 2 | | using System.Linq; |
| | | 3 | | using UnityEngine; |
| | | 4 | | |
| | | 5 | | // The constrained k-means clusterer performs k-means clustering under size and radius constraints. |
| | | 6 | | public class ConstrainedKMeansClusterer : SizeAndRadiusConstrainedClustererBase { |
| | 18 | 7 | | public ConstrainedKMeansClusterer(int maxSize, float maxRadius) : base(maxSize, maxRadius) {} |
| | | 8 | | |
| | | 9 | | // Generate the clusters from the list of hierarchical objects. |
| | 6 | 10 | | public override List<Cluster> Cluster(IEnumerable<IHierarchical> hierarchicals) { |
| | 8 | 11 | | if (hierarchicals == null || !hierarchicals.Any()) { |
| | 2 | 12 | | return new List<Cluster>(); |
| | | 13 | | } |
| | | 14 | | |
| | 4 | 15 | | int numClusters = (int)Mathf.Ceil(hierarchicals.Count() / _maxSize); |
| | | 16 | | KMeansClusterer clusterer; |
| | | 17 | | List<Cluster> clusters; |
| | 16 | 18 | | while (true) { |
| | 8 | 19 | | clusterer = new KMeansClusterer(numClusters); |
| | 8 | 20 | | clusters = clusterer.Cluster(hierarchicals); |
| | | 21 | | |
| | | 22 | | // Count the number of over-populated and over-sized clusters. |
| | 8 | 23 | | int numOverPopulatedClusters = 0; |
| | 8 | 24 | | int numOverSizedClusters = 0; |
| | 78 | 25 | | foreach (var cluster in clusters) { |
| | 18 | 26 | | if (cluster.Size > _maxSize) { |
| | 0 | 27 | | ++numOverPopulatedClusters; |
| | 0 | 28 | | } |
| | 22 | 29 | | if (cluster.Radius() > _maxRadius) { |
| | 4 | 30 | | ++numOverSizedClusters; |
| | 4 | 31 | | } |
| | 18 | 32 | | } |
| | | 33 | | |
| | | 34 | | // If all clusters satisfy the size and radius constraints, the algorithm has converged. |
| | 12 | 35 | | if (numOverPopulatedClusters == 0 && numOverSizedClusters == 0) { |
| | 4 | 36 | | break; |
| | | 37 | | } |
| | | 38 | | |
| | 4 | 39 | | numClusters += |
| | | 40 | | (int)Mathf.Ceil(Mathf.Max(numOverPopulatedClusters, numOverSizedClusters) / 2f); |
| | 4 | 41 | | } |
| | 4 | 42 | | return clusters; |
| | 6 | 43 | | } |
| | | 44 | | } |