D3 Marker Clustering - Shipwrecks

readme.md

A more practical geographic use of a clustering module than my initial demonstration.

Each shipwreck is represented with a circle 2 px in radius. Overlapping circles are combined and new centroids are calculated based on a weighted average of their areas. Because of the wandering centroid, the merger of larger circles can result in the clearing of a neighborhood around larger circles - this effect is most noticeable when combining thousands of circles.

Scroll to zoom in/out. Drag to pan.

I'm working on developing the clusterer a bit more, but you can find some initial documentation and source on github.

Shipwreck data hosted by ESRI here.

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(node.a/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">
<style>
  svg, canvas {
    position: absolute;
    top: 0px;
    left: 0px;
  }
  rect {
    fill: white;
  }	
</style>
<svg width="960" height="500"></svg>
<canvas width="960" height="500"></canvas>


<script src="https://d3js.org/d3.v5.min.js"></script>
<script src="https://d3js.org/d3-tile.v0.0.min.js"></script>
<script src="d3-cluster.js"></script>
<script>
// Canvas and SVG:
var canvas = d3.select("canvas");
var ctx = canvas.node().getContext("2d");
var svg = d3.select("svg");
// Basic parameters:
var width = +canvas.attr("width");
var height = +canvas.attr("height");
var tau = 2 * Math.PI;
var baseScale = 960/tau;
var center = [-75.5, 38];

// Tiles Projection Setup:
var tileProjection = d3.geoMercator()
  .scale(1/tau)
  .translate([0,0]);
  
var tileCenter = tileProjection(center);  
  
// Geographic Projection Setup:
var geoProjection = d3.geoMercator()
  .scale(baseScale)
  .center(tileProjection.invert([0,0]))
  .translate([0,0]);
  
// Set up tiles:
var tile = d3.tile()
    .size([width, height]);
	
// Create a g for the tiles:
var raster = svg.append("g");  

var controls = svg.append("g");

d3.csv("shipwrecks.csv").then(function(data) {
  // Set up nodes:
  resetNodes(data); // initialize
	
  // Set up clusterer
  var cluster = d3.cluster()
    .nodes(data)
    .on("tick", ticked);
	
  // Set up zoom.
  var zoom = d3.zoom()
    .on("zoom",zoomed)
    .scaleExtent([1 << 14, 1 << 17])
	
  // Call the zoom:
  canvas.call(zoom)
    .call(zoom.transform, d3.zoomIdentity
    .translate(width / 2, height / 2)
    .scale(1 << 15)
    .translate(-tileCenter[0], -tileCenter[1]));
	
  //
  // Zoom Functionality:
  //
  function zoomed() {
    // stop cluster:
    cluster.stop();
		  
    // Scale values:
    var kt = d3.event.transform.k; // tile scale factor
    var k = kt/width;  // projection scale factor
		
    // Translate values:
    var x = d3.event.transform.x
    var y = d3.event.transform.y;
    var t0 = geoProjection.translate();
    var t = [x,y];
		
    // Update the cluster:
	
    // If translated only:
    if(geoProjection.scale() == k * baseScale) {
	  // Update the projection:
      geoProjection.translate([x,y])
      clear();
	  
      // Adjust cluster nodes:
      data.forEach(function(node) {
        node.x += t[0] - t0[0];
        node.y += t[1] - t0[1];
        drawCircle(node);
      })		
    }
    
   // If scaled:
   else {
      // Update Projection:
      geoProjection.translate([x,y])
      geoProjection.scale(baseScale * k);
	  
	  // Update the cluster:
      resetNodes(data);
      cluster.nodes(data)
        .alpha(1)

    }
	
    cluster.restart();
		
    // Update the tiles:
    var tiles = tile
      .scale(kt)
      .translate([x, y])();
	  
    var image = raster
      .attr("transform", stringify(tiles.scale, tiles.translate))
      .selectAll("image")
      .data(tiles, function(d) { return d; });

    image.exit().remove();
  
    image.enter().append("image")
      .attr("xlink:href", function(d) { return "https://server.arcgisonline.com/ArcGIS/rest/services/Ocean_Basemap/MapServer/tile/" + d[2] + "/" + d[1] + "/" + d[0] + ".png"; })
      .attr("x", function(d) { return d[0] * 256; })
      .attr("y", function(d) { return d[1] * 256; })
      .attr("width", 256)
      .attr("height", 256);  
	  
  }

  // 
  // Tick functionality
  //
  function ticked(x,y) {
    clear();
		
    // Update cluster nodes:
    this.nodes(data.filter(function(d) { return d.r != 0; }))

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

  
// Helper functions:
function resetNodes(nodes) {
	nodes.forEach(function(node) {
		var p = geoProjection([+node.long,+node.lat]);
		node.x = p[0];
		node.y = p[1];
		node.r = 2;
		node.a = Math.PI * node.r * node.r;	
		node.collided = false;
		node.count = 1;				
	})	
}
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); 
}
function clear() {
	ctx.clearRect(0, 0, width, height);
}
function attribute() {
	ctx.font = "10px Arial";
	ctx.textAlign = "left";
	ctx.fillStyle = "black";
	ctx.fillText("Tiles \u00A9 Esri - Sources: GEBCO, NOAA, CHS, OSU, UNH, CSUMB, National Geographic, DeLorme, NAVTEQ, and Esri", 4, height-4);
}
function stringify(scale, translate) {
  var k = scale / 256, r = scale % 1 ? Number : Math.round;
  return "translate(" + r(translate[0] * scale) + "," + r(translate[1] * scale) + ") scale(" + k + ")";
}
</script>

shipwrecks.csv