greedy agglomerative merging

clusterPoints.js

/**
 * Clusters 2D points so each cluster can be enclosed in a circle of radius <= d.
 * Uses greedy agglomerative merging: repeatedly merge the pair of clusters whose
 * merged centroid distance is smallest, as long as the merged cluster's max
 * distance from its centroid <= d.
 *
 * @param {Array<[number, number]>} points - array of [x, y] pairs
 * @param {number} d - maximum allowed radius for any cluster
 * @returns {Array<Array<[number, number]>>} clusters
 */
function clusterPoints(points, d) {
  if (!Array.isArray(points)) throw new TypeError('points must be an array')
  if (typeof d !== 'number' || d < 0)
    throw new TypeError('d must be a non-negative number')

  // helpers
  const dist = ([ax, ay], [bx, by]) => {
    const dx = ax - bx
    const dy = ay - by
    return Math.hypot(dx, dy)
  }

  const centroid = (cluster) => {
    let sumX = 0
    let sumY = 0
    for (const [x, y] of cluster) {
      sumX += x
      sumY += y
    }
    return [sumX / cluster.length, sumY / cluster.length]
  }

  const maxRadius = (cluster, center) => {
    let max = 0
    for (const point of cluster) {
      const r = dist(point, center)
      if (r > max) max = r
    }
    return max
  }

  // init clusters: one point per cluster
  let clusters = points.map((p) => [p])

  // try merging until no valid merge remains
  while (true) {
    let best = null
    let bestCentroidDist = Infinity

    // precompute centroids for speed
    const centroids = clusters.map((c) => centroid(c))

    for (let i = 0; i < clusters.length; i++) {
      for (let j = i + 1; j < clusters.length; j++) {
        // compute merged centroid (weighted by sizes)
        const a = clusters[i],
          b = clusters[j]
        const size_a = a.length,
          size_b = b.length,
          merged_size = size_a + size_b
        const centroid_a = centroids[i],
          centroid_b = centroids[j]
        const merged_centroid = [
          (centroid_a[0] * size_a + centroid_b[0] * size_b) / merged_size,
          (centroid_a[1] * size_a + centroid_b[1] * size_b) / merged_size
        ]

        // check radius constraint
        const merged = a.concat(b)
        if (maxRadius(merged, merged_centroid) <= d) {
          const cdist = dist(centroid_a, centroid_b)
          if (cdist < bestCentroidDist) {
            bestCentroidDist = cdist
            best = [i, j, merged]
          }
        }
      }
    }

    if (!best) break

    // apply best merge
    const [i, j, merged] = best
    // remove j then i (j>i) and push merged
    clusters.splice(j, 1)
    clusters.splice(i, 1)
    clusters.push(merged)
  }

  return clusters
}

module.exports = clusterPoints