cluster method

List<List<LatLng>> cluster(List<LatLng> points)

Clusters points into k clusters. Returns a list of clusters, where each cluster is a list of LatLng points.

Implementation

List<List<LatLng>> cluster(List<LatLng> points) {
  if (points.isEmpty || k <= 0) return [];

  // Randomly initialize centroids from the points.
  List<LatLng> centroids = List.from(points)..shuffle();
  centroids = centroids.take(k).toList();

  List<List<LatLng>> clusters = List.generate(k, (_) => []);

  for (int iter = 0; iter < maxIterations; iter++) {
    // Clear clusters for current iteration.
    clusters = List.generate(k, (_) => []);

    // Assignment step: assign each point to the nearest centroid.
    for (var point in points) {
      int bestIndex = 0;
      double minDist = distance.as(LengthUnit.Meter, point, centroids[0]);
      for (int i = 1; i < centroids.length; i++) {
        double d = distance.as(LengthUnit.Meter, point, centroids[i]);
        if (d < minDist) {
          minDist = d;
          bestIndex = i;
        }
      }
      clusters[bestIndex].add(point);
    }

    // Update step: recalc centroids using spherical averaging.
    List<LatLng> newCentroids = [];
    for (var cluster in clusters) {
      if (cluster.isEmpty) {
        // If a cluster ends up empty, randomly reinitialize its centroid.
        newCentroids.add(points[Random().nextInt(points.length)]);
      } else {
        newCentroids.add(_computeCentroid(cluster));
      }
    }

    // Check for convergence.
    double maxShift = 0;
    for (int i = 0; i < k; i++) {
      double shift = distance.as(LengthUnit.Meter, centroids[i], newCentroids[i]);
      if (shift > maxShift) maxShift = shift;
    }

    centroids = newCentroids;
    if (maxShift < tolerance) break;
  }

  return clusters;
}