A quadtree recursively partitions two-dimensional space into squares, dividing each square into four equally-sized squares.

d3-quadtree-search.js

import {quadtree as d3_quadtree} from "d3-quadtree";
import {search} from "search.js";

// ...

// Create cluster points, i.e. an array of:
// [[cluster_x, cluster_y, [points_to_cluster], ...]
const nodes = [[0, 0, {id: 1, r: 10, name: "node-1"}], [10, 10, {id: 2, r: 10, name: "node-2"}]];
const clusterRange = 80;
const quadtree = d3_quadtree().addAll(nodes);
let clusterPoints = [];
for (let x = 0; x <= innerWidth; x += clusterRange) {
    for (let y = 0; y <= innerHeight; y += clusterRange) {
        let searched = search(quadtree, x, y, x + clusterRange, y + clusterRange);

        let centerPoint = searched.reduce((prev, current) => {
            return [prev[0] + current[0], prev[1] + current[1]];
        }, [0, 0]);

        centerPoint[0] = centerPoint[0] / searched.length;
        centerPoint[1] = centerPoint[1] / searched.length;
        centerPoint.push(searched);

        if (centerPoint[0] && centerPoint[1]) {
            clusterPoints.push(centerPoint);
        }
    }
}

search.js

export const search = (quadtree, x0, y0, x3, y3) => {
  // Find the nodes within the specified rectangle.
  // Inspired by https://bl.ocks.org/mbostock/4343214
  let validData = [];
  quadtree.visit((node, x1, y1, x2, y2) => {
      if (!node.length) {
          do {
              const d = node.data;
              d.scanned = true;
              if ((d[0] >= x0) && (d[0] < x3) && (d[1] >= y0) && (d[1] < y3)) {
                  validData.push(d);
              }
          } while (node = node.next);
      }
      return x1 >= x3 || y1 >= y3 || x2 < x0 || y2 < y0;
  });
  return validData;
};