D3 Marker Clustering

readme.md

This block demonstrates a clusterer. When zooming on the canvas the radius of each circle is increased/decreased. SCroll in to start clustering.

For a geographic demonstration see this block

Where circles overlap, circles are clustered into a larger circle with an area equal to the chldren. When a circle gets sufficiently large, the number of circles that were merged to form it is shown.

This block contains 10 000 nodes (reset at each zoom level) and uses canvas. I've had decent results up to 100 000 nodes.

Current Github Repository

__

More info:

I've been intrigued about making a d3 marker clusterer for some time.

My initial thoughts were to use a voronoi/delaunay approach, but I realized that a d3 force layout could do the job. The d3-cluster module is a stripped down and modified version of d3-force, which allows efficient calculations while still retaining the power to customize the visualization.

This block is the proof of concept, I hope to refine the module over the next few days to offer a number of refinements. These refinements include tracking nodes in the cluster; accessor functions for x,y,r and area; and a node reset method.

d3.cluster()

Creates a new cluster layout.

cluster.nodes()

Adds nodes to the cluster.

As with d3-force, nodes are positoined with node.x, node.y. These values must be provided as initial locations for the nodes. Currently the coordinates must be located at node.x, node.y, however I intend to add an accessor method for different properties or functions.

Nodes can include a node.a property which indicates node area/weight. Alternatively you can specify a node.r which specifies a node radius.

When nodes merge, the area/weight of the node is used to proportinatly center the node. Radius is calculated as a convience for marker generation.

When two nodes merge the one with the greater area/weight gains the area/weight of the smaller node. The small node's area/weight and radius is converted to zero. Nodes that have merged have their node.collided property set to true.

Nodes can also have a count property, this could be set to 1, as with areas/weights, larger nodes absorb the count of smaller nodes when clustering. This can allows the clustered node to indicate how many nodes are contained in the cluster.

cluster.alpha(), cluster.alphaDecay(), cluster.stop(), cluster.restart(), cluster.find(), cluster.on(), cluster.alphaTarget(), cluster.alphaMin()

These act the same as with d3-force. Alpha decay is set to 0.04 by default as compared with d3-force.

cluster.clusterer(clusterer)

Takes a d3.clusterer() which is a modified d3-force collide force. No name is provided as with d3-force forces. The default value is d3.clusterer().radius(function(d) { return d.r; })

d3.clusterer()

The clusterer handles the mechanics of the clustering and is a modified d3-force collide force.

d3.clusterer() has the same methods as a d3-force collide force, but has been altered internally. No vx or vy properties will be considered in positioning.

d3-cluster.js

// https://d3js.org/d3-force/ Version 1.1.0. Copyright 2017 Mike Bostock.
(function (global, factory) {
	typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports, require('d3-quadtree'), require('d3-collection'), require('d3-dispatch'), require('d3-timer')) :
	typeof define === 'function' && define.amd ? define(['exports', 'd3-quadtree', 'd3-collection', 'd3-dispatch', 'd3-timer'], factory) :
	(factory((global.d3 = global.d3 || {}),global.d3,global.d3,global.d3,global.d3));
}(this, (function (exports,d3Quadtree,d3Collection,d3Dispatch,d3Timer) { 'use strict';


var constant = function(x) {
  return function() {
    return x;
  };
};

var jiggle = function() {
  return (Math.random() - 0.5) * 1e-6;
};

function x(d) {
  return d.x;
}

function y(d) {
  return d.y;
}

var collide = function(radius) {
  var nodes,
      radii,
      strength = 1,
      iterations = 1;

  if (typeof radius !== "function") radius = constant(radius == null ? 1 : +radius);

  function force() {
    var i, n = nodes.length,
        tree,
        node,
        xi,
        yi,
        ri,
        ri2;

    for (var k = 0; k < iterations; ++k) {
      tree = d3Quadtree.quadtree(nodes, x, y).visitAfter(prepare);
      for (i = 0; i < n; ++i) {
        node = nodes[i];
        ri = radii[node.index], ri2 = ri * ri;
        xi = node.x;
        yi = node.y;
        tree.visit(apply);
      }
    }

    function apply(quad, x0, y0, x1, y1) {
      var data = quad.data, rj = quad.r, r = ri + rj;
      if (data) {
        if (data.index > node.index) {
          var x = xi - data.x,
              y = yi - data.y,
              l = x * x + y * y;
          if (l < r * r) {
			if (x == NaN) x = 0;
			if (y == NaN) y = 0;
			if (x === 0) x = jiggle(), l += x * x;
            if (y === 0) y = jiggle(), l += y * y;
            l = (r - (l = Math.sqrt(l))) / l * strength;
			node.collided = true;
			data.collided = true;
			
			if(data.a && node.a) {
				if(data.a > node.a) {
					data.x = (data.x * data.a + node.x * node.a)/(data.a + node.a);
					data.y = (data.y * data.a + node.y * node.a)/(data.a + node.a);
					
					data.count += node.count;
					data.a += node.a;
					data.r = Math.sqrt(data.a/Math.PI);
					
					node.a = 0;
					node.r = 0;

				}
				
				else {
					node.x = (data.x * data.a + node.x * node.a)/(data.a + node.a);
					node.y = (data.y * data.a + node.y * node.a)/(data.a + node.a)
					
					node.a += data.a;	
					node.count += data.count;
					node.r = Math.sqrt(node.a/Math.PI);
					
					data.a = 0;
					data.r = 0;
					
				}
			}

			
          }
        }
        return;
      }
	  
      return x0 > xi + r || x1 < xi - r || y0 > yi + r || y1 < yi - r;
    }
  }

  function prepare(quad) {
    if (quad.data) return quad.r = radii[quad.data.index];
    for (var i = quad.r = 0; i < 4; ++i) {
      if (quad[i] && quad[i].r > quad.r) {
        quad.r = quad[i].r;
      }
    }
  }

  function initialize() {
    if (!nodes) return;
    var i, n = nodes.length, node;
    radii = new Array(n);
    for (i = 0; i < n; ++i) node = nodes[i], radii[node.index] = +radius(node, i, nodes);
  }

  force.initialize = function(_) {
    nodes = _;
    initialize();
  };

  force.iterations = function(_) {
    return arguments.length ? (iterations = +_, force) : iterations;
  };

  force.strength = function(_) {
    return arguments.length ? (strength = +_, force) : strength;
  };

  force.radius = function(_) {
    return arguments.length ? (radius = typeof _ === "function" ? _ : constant(+_), initialize(), force) : radius;
  };

  return force;
};


var simulation = function(nodes) {
  var simulation,
      alpha = 1,
      alphaMin = 0.001,
      alphaDecay = 0.04,
      alphaTarget = 0,
	  force = collide().radius(function(d) { return d.r; }),
      stepper = d3Timer.timer(step),
      event = d3Dispatch.dispatch("tick", "end");

	  
	  
  if (nodes == null) nodes = [];

  function step() {
    tick();
    event.call("tick", simulation);
    if (alpha < alphaMin) {
      stepper.stop();
      event.call("end", simulation);
    }
  }
  
  var i = 0;

  function tick() {
    alpha += (alphaTarget - alpha) * alphaDecay;
	force(alpha);
  }

  function initializeNodes() {
    for (var i = 0, n = nodes.length, node; i < n; ++i) {
      node = nodes[i], node.index = i;
      if(node.collided == undefined) node.collided = false;
	  if(node.count == undefined) node.count = 1;
	  if(node.a == undefined) node.a = 1;
	  if(node.r == undefined) node.r = Math.sqrt(1/Math.PI);
    }
  }

  function initializeForce(force) {
    if (force.initialize) force.initialize(nodes);
    return force;
  }

  initializeNodes();

  return simulation = {
    tick: tick,

    restart: function() {
      return stepper.restart(step), simulation;
    },

    stop: function() {
      return stepper.stop(), simulation;
    },

    nodes: function(_) {
	  return arguments.length ? (nodes = _, initializeNodes(), initializeForce(force), simulation) : nodes;
    },

    alpha: function(_) {
      return arguments.length ? (alpha = +_, simulation) : alpha;
    },

    alphaMin: function(_) {
      return arguments.length ? (alphaMin = +_, simulation) : alphaMin;
    },

    alphaDecay: function(_) {
      return arguments.length ? (alphaDecay = +_, simulation) : +alphaDecay;
    },

    alphaTarget: function(_) {
      return arguments.length ? (alphaTarget = +_, simulation) : alphaTarget;
    },

    clusterer: function(_) {
	  return arguments.length ? (nodes.length > 0 ? force = initializeForce(_) : force = _, simulation) : force;
    },
	
	find: function(x, y, radius) {
      var i = 0,
          n = nodes.length,
          dx,
          dy,
          d2,
          node,
          closest;

      if (radius == null) radius = Infinity;
      else radius *= radius;

      for (i = 0; i < n; ++i) {
        node = nodes[i];
        dx = x - node.x;
        dy = y - node.y;
        d2 = dx * dx + dy * dy;
        if (d2 < radius) closest = node, radius = d2;
      }

      return closest;
    },

    on: function(name, _) {
      return arguments.length > 1 ? (event.on(name, _), simulation) : event.on(name);
    }

	
  };
};

exports.clusterer = collide;
exports.cluster = simulation;


Object.defineProperty(exports, '__esModule', { value: true });

})));

index.html

<!DOCTYPE html>
<meta charset="utf-8">
<canvas width="960" height="600"></canvas>
<script src="https://d3js.org/d3.v5.min.js"></script>
<script src="d3-cluster.js"></script>
<script>
var canvas = d3.select("canvas"),
  ctx = canvas.node().getContext("2d"),
  width = +canvas.attr("width"),
  height = +canvas.attr("height");
  
// Create nodes:
var nodes = d3.range(10000).map(function() {
   var node = {};
   node.x = Math.random()*width;
   node.y = Math.random()*height;
   node.y1 = node.y;  // y1,x1 = original placement.
   node.x1 = node.x;
   node.r = 1;
   node.a = Math.PI * node.r * node.r;
   return node;
})

// Set up cluster
var cluster = d3.cluster()
      .nodes(nodes)
      .on("tick", ticked);
	  
// Tick function:
function ticked() {
  // clear canvas:
  ctx.clearRect(0, 0, width, height);

  // Update cluster nodes:
  this.nodes(nodes.filter(function(d) { return d.r != 0; }))

  // draw still active nodes:
  nodes.filter(function(d) { return d.r != 0; })
    .forEach(drawCircle)

} 

// Modify circle radius with zoom scale:
var zoom = d3.zoom()
  .on("zoom", function() {
	// Reset nodes to restart cluster at each scale level:
	nodes.forEach(function(node) {
    node.r = 1 * Math.pow(d3.event.transform.k,0.3);
    node.a = Math.PI * node.r * node.r;	
    node.collided = false;
    node.x = node.x1;
    node.y = node.y1;
    node.count = 1;
  })
	
  // Restart the simulation
  cluster.stop();
  cluster.nodes(nodes)
    .alpha(1)
    .restart();
})
  
canvas.call(zoom);

// Drawing functions:
function drawCircle(d) {
    ctx.fillStyle = d.collided ? ( d.r > 20 ? "#a8ddb5" : "#43a2ca"  ) : "#0868ac";
    ctx.beginPath();
    ctx.moveTo(d.x, d.y);
    ctx.arc(d.x, d.y, d.r, 0, 2 * Math.PI);
    ctx.fill();
	
	if(d.r > 20) drawText(d);
}
function drawText(d) {
	ctx.font = d.r / 3 + "px Arial";
	ctx.textAlign = "center";
	ctx.fillStyle = "white";
	ctx.fillText(d.count,d.x,d.y+d.r/9); 
}
  

</script>

thumbnail.png