| | | 1 | | using System.Collections.Generic; |
| | | 2 | | using System.Linq; |
| | | 3 | | using UnityEngine; |
| | | 4 | | |
| | | 5 | | // The agglomerative clusterer performs agglomerative clustering with the stopping condition given |
| | | 6 | | // by the size and radius constraints. |
| | | 7 | | public class AgglomerativeClusterer : SizeAndRadiusConstrainedClustererBase { |
| | 21 | 8 | | public AgglomerativeClusterer(int maxSize, float maxRadius) : base(maxSize, maxRadius) {} |
| | | 9 | | |
| | | 10 | | // Generate the clusters from the list of hierarchical objects. |
| | 7 | 11 | | public override List<Cluster> Cluster(IEnumerable<IHierarchical> hierarchicals) { |
| | 7 | 12 | | var clusters = new List<Cluster>(); |
| | 9 | 13 | | if (hierarchicals == null || !hierarchicals.Any()) { |
| | 2 | 14 | | return clusters; |
| | | 15 | | } |
| | | 16 | | |
| | 75 | 17 | | foreach (var hierarchical in hierarchicals) { |
| | 20 | 18 | | var cluster = new Cluster { Centroid = hierarchical.Position }; |
| | 20 | 19 | | cluster.AddSubHierarchical(hierarchical); |
| | 20 | 20 | | clusters.Add(cluster); |
| | 20 | 21 | | } |
| | | 22 | | |
| | | 23 | | // Create a set containing all valid cluster indices. |
| | 5 | 24 | | var validClusterIndices = new HashSet<int>(); |
| | 70 | 25 | | for (int i = 0; i < clusters.Count; ++i) { |
| | 20 | 26 | | validClusterIndices.Add(i); |
| | 20 | 27 | | } |
| | | 28 | | |
| | | 29 | | // Find the pairwise distances between all clusters. |
| | | 30 | | // Only the lower triangular part of the distances matrix is used, i.e., row index > column |
| | | 31 | | // index. |
| | 5 | 32 | | var distances = new float[clusters.Count, clusters.Count]; |
| | 70 | 33 | | for (int i = 0; i < clusters.Count; ++i) { |
| | 130 | 34 | | for (int j = 0; j < i; ++j) { |
| | 30 | 35 | | distances[i, j] = Vector3.Distance(clusters[i].Centroid, clusters[j].Centroid); |
| | 30 | 36 | | } |
| | 20 | 37 | | } |
| | | 38 | | |
| | 32 | 39 | | while (true) { |
| | | 40 | | // Find the minimum distance between two clusters. |
| | 16 | 41 | | float minDistance = Mathf.Infinity; |
| | 16 | 42 | | int clusterIndex1 = -1; |
| | 16 | 43 | | int clusterIndex2 = -1; |
| | | 44 | | // Invariant: clusterIndex1 > clusterIndex2. |
| | 216 | 45 | | foreach (int i in validClusterIndices) { |
| | 355 | 46 | | for (int j = 0; j < i; ++j) { |
| | 102 | 47 | | if (validClusterIndices.Contains(j) && distances[i, j] < minDistance) { |
| | 21 | 48 | | minDistance = distances[i, j]; |
| | 21 | 49 | | clusterIndex1 = i; |
| | 21 | 50 | | clusterIndex2 = j; |
| | 21 | 51 | | } |
| | 81 | 52 | | } |
| | 56 | 53 | | } |
| | | 54 | | |
| | | 55 | | // Check whether the minimum distance exceeds the maximum cluster radius, in which case the |
| | | 56 | | // algorithm has converged. This produces a conservative solution because the radius of a |
| | | 57 | | // merged cluster is less than or equal to the sum of the original cluster radii. |
| | 21 | 58 | | if (minDistance == Mathf.Infinity || minDistance > _maxRadius) { |
| | 5 | 59 | | break; |
| | | 60 | | } |
| | | 61 | | |
| | | 62 | | // Check whether merging the two clusters would violate the size constraint. |
| | 17 | 63 | | if (clusters[clusterIndex1].Size + clusters[clusterIndex2].Size > _maxSize) { |
| | 6 | 64 | | distances[clusterIndex1, clusterIndex2] = Mathf.Infinity; |
| | 6 | 65 | | continue; |
| | | 66 | | } |
| | | 67 | | |
| | | 68 | | // Merge the two clusters together and keep the cluster with the smaller index, i.e., |
| | | 69 | | // clusterIndex2. |
| | 5 | 70 | | clusters[clusterIndex2].Merge(clusters[clusterIndex1]); |
| | 5 | 71 | | clusters[clusterIndex2].Recenter(); |
| | 5 | 72 | | validClusterIndices.Remove(clusterIndex1); |
| | | 73 | | |
| | | 74 | | // Update the distances matrix using the distance between the cluster centroids. |
| | | 75 | | // TODO(titan): Change the distance metric to use average or maximum linkage. |
| | 51 | 76 | | foreach (int i in validClusterIndices) { |
| | 17 | 77 | | if (i == clusterIndex2) { |
| | 5 | 78 | | continue; |
| | | 79 | | } |
| | 7 | 80 | | float distance = Vector3.Distance(clusters[clusterIndex2].Centroid, clusters[i].Centroid); |
| | 10 | 81 | | if (i < clusterIndex2) { |
| | 3 | 82 | | distances[clusterIndex2, i] = distance; |
| | 11 | 83 | | } else if (i > clusterIndex2) { |
| | 4 | 84 | | distances[i, clusterIndex2] = distance; |
| | 4 | 85 | | } |
| | 7 | 86 | | } |
| | 5 | 87 | | } |
| | | 88 | | |
| | | 89 | | // Select only the valid clusters. |
| | 70 | 90 | | for (int i = clusters.Count - 1; i >= 0; --i) { |
| | 25 | 91 | | if (!validClusterIndices.Contains(i)) { |
| | 5 | 92 | | clusters.RemoveAt(i); |
| | 5 | 93 | | } |
| | 20 | 94 | | } |
| | 5 | 95 | | return clusters; |
| | 7 | 96 | | } |
| | | 97 | | } |