The brushing in this scatterplot is optimized to use a quadtree, reducing the amount of searching needed to find the data points selected by the brush. Click "Reveal the quadtree" to see a slowed down animation of how the quadtree is traversed during brushing.
xxxxxxxxxx<head> <meta charset="utf-8"> <script src="https://d3js.org/d3.v4.min.js"></script> <style> body { margin:0;position:fixed;top:0;right:0;bottom:0;left:0; } #vis-container { font-family: 'Proxima Nova', 'proxima-nova', 'helvetica neue', sans-serif; } button { background: #fff; border: 2px solid #e7e8e9; color: #333; text-transform: uppercase; letter-spacing: 2px; padding: 10px; font-size: 0.75em; cursor: pointer;} </style></head><div> <button id="reveal-quadtree">Reveal quadtree</button></div><div id="vis-container"></div><body> <script>// generate random datavar data = d3.range(50).map(function (d, i) { return ({ x: Math.random(), y: Math.random(), id: i, label: ("Point " + i),}); });// ----------------------------------------------------// Build a basic scatterplot// ----------------------------------------------------// outer svg dimensionsvar width = 600;var height = 400;// padding around the chart where axes will govar padding = { top: 20, right: 20, bottom: 40, left: 50,};// inner chart dimensions, where the dots are plottedvar plotAreaWidth = width - padding.left - padding.right;var plotAreaHeight = height - padding.top - padding.bottom;// radius of points in the scatterplotvar pointRadius = 3;// initialize scalesvar xScale = d3.scaleLinear().domain([0, 1]).range([0, plotAreaWidth]);var yScale = d3.scaleLinear().domain([0, 1]).range([plotAreaHeight, 0]);var colorScale = d3.scaleLinear().domain([0, 1]).range(['#06a', '#0bb']);// select the root container where the chart will be addedvar container = d3.select('#vis-container');// initialize main SVGvar svg = container.append('svg') .attr('width', width) .attr('height', height);// the main <g> where all the chart content goes insidevar g = svg.append('g') .attr('transform', ("translate(" + (padding.left) + " " + (padding.top) + ")"));// add in axis groupsvar xAxisG = g.append('g').classed('x-axis', true) .attr('transform', ("translate(0 " + (plotAreaHeight + pointRadius) + ")"));// x-axis labelg.append('text') .attr('transform', ("translate(" + (plotAreaWidth / 2) + " " + (plotAreaHeight + (padding.bottom)) + ")")) .attr('dy', -4) // adjust distance from the bottom edge .attr('class', 'axis-label') .attr('text-anchor', 'middle') .text('X Axis');var yAxisG = g.append('g').classed('y-axis', true) .attr('transform', ("translate(" + (-pointRadius) + " 0)"));// y-axis labelg.append('text') .attr('transform', ("rotate(270) translate(" + (-plotAreaHeight / 2) + " " + (-padding.left) + ")")) .attr('dy', 12) // adjust distance from the left edge .attr('class', 'axis-label') .attr('text-anchor', 'middle') .text('Y Axis');// set up axis generating functionsvar xTicks = Math.round(plotAreaWidth / 50);var yTicks = Math.round(plotAreaHeight / 50);var xAxis = d3.axisBottom(xScale) .ticks(xTicks) .tickSizeOuter(0);var yAxis = d3.axisLeft(yScale) .ticks(yTicks) .tickSizeOuter(0);// draw the axesyAxisG.call(yAxis);xAxisG.call(xAxis);// add in circlesvar circles = g.append('g').attr('class', 'circles');var binding = circles.selectAll('.data-point').data(data, function (d) { return d.id; });binding.enter().append('circle') .classed('data-point', true) .attr('r', pointRadius) .attr('cx', function (d) { return xScale(d.x); }) .attr('cy', function (d) { return yScale(d.y); }) .attr('fill', function (d) { return colorScale(d.y); });// ----------------------------------------------------// Add in brushing// ----------------------------------------------------// generate a quadtree for faster lookups for brushingvar quadtree = d3.quadtree() .x(function (d) { return xScale(d.x); }) .y(function (d) { return yScale(d.y); }) .addAll(data);var brushOutput = container.append('ul') .attr('class', 'brush-output list-inline') .style('padding-left', ((padding.left) + "px")) .style('min-height', '50px');var brushedCircles = g.append('g').attr('class', 'circles-brushed');var brushedColor = 'tomato';function highlightBrushed(brushedNodes) { // output the labels of the selected points var lis = brushOutput.selectAll('li').data(brushedNodes, function (d) { return d.id; }); lis.enter() .append('li') .text(function (d) { return d.label; }); lis.exit().remove(); // overlap colored circles to indicate the highlighted ones in the chart var circles = brushedCircles.selectAll('circle').data(brushedNodes, function (d) { return d.id; }); circles.enter() .append('circle') .classed('data-point brushed', true) .attr('r', pointRadius) .attr('cx', function (d) { return xScale(d.x); }) .attr('cy', function (d) { return yScale(d.y); }) .attr('fill', brushedColor); circles.exit() .remove();}// The following two functions taken from vis-utils: https://github.com/pbeshai/vis-utilsvar X = 0;var Y = 1;var TOP_LEFT = 0;var BOTTOM_RIGHT = 1;/** * Determines if two rectangles overlap by looking at two pairs of * points [[r1x1, r1y1], [r1x2, r1y2]] for rectangle 1 and similarly * for rectangle2. */function rectIntersects(rect1, rect2) { return (rect1[TOP_LEFT][X] <= rect2[BOTTOM_RIGHT][X] && rect2[TOP_LEFT][X] <= rect1[BOTTOM_RIGHT][X] && rect1[TOP_LEFT][Y] <= rect2[BOTTOM_RIGHT][Y] && rect2[TOP_LEFT][Y] <= rect1[BOTTOM_RIGHT][Y]);}/** * Determines if a point is inside a rectangle. The rectangle is * defined by two points [[rx1, ry1], [rx2, ry2]] */function rectContains(rect, point) { return rect[TOP_LEFT][X] <= point[X] && point[X] <= rect[BOTTOM_RIGHT][X] && rect[TOP_LEFT][Y] <= point[Y] && point[Y] <= rect[BOTTOM_RIGHT][Y];}// callback when the brush updates / endsfunction updateBrush() { var ref = d3.event; var selection = ref.selection; // if we have no selection, just reset the brush highlight to no nodes if (!selection) { highlightBrushed([]); return; } // begin an array to collect the brushed nodes var brushedNodes = []; // traverse the quad tree, skipping branches where we do not overlap // with the brushed selection box quadtree.visit(function (node, x1, y1, x2, y2) { // check that quadtree node intersects var overlaps = rectIntersects(selection, [[x1, y1], [x2, y2]]); // skip if it doesn't overlap the brush if (!overlaps) { return true; } // if this is a leaf node (node.length is falsy), verify it is within the brush // we have to do this since an overlapping quadtree box does not guarantee // that all the points within that box are covered by the brush. if (!node.length) { var d = node.data; var dx = xScale(d.x); var dy = yScale(d.y); if (rectContains(selection, [dx, dy])) { brushedNodes.push(d); } } // return false so that we traverse into branch (only useful for non-leaf nodes) return false; }); // update the highlighted brushed nodes highlightBrushed(brushedNodes);}// create the d3-brush generatorvar brush = d3.brush() .extent([[0, 0], [plotAreaWidth, plotAreaHeight]]) .on('brush end', updateBrush);// attach the brush to the chartvar gBrush = g.append('g') .attr('class', 'brush') .call(brush);// update the styling of the select box (typically done in CSS)gBrush.select('.selection') .style('stroke', 'skyblue') .style('stroke-opacity', 0.4) .style('fill', 'skyblue') .style('fill-opacity', 0.1);// ----------------------------------------------------// Add a fun click handler to reveal the details of what is happening// ----------------------------------------------------function quadtreeRect(rect, x1, y1, x2, y2) { var width = x2 - x1; var height = y2 - y1; // clip to the edges of the plot area if (x1 + width > plotAreaWidth) { width = plotAreaWidth - x1; } if (y1 + height > plotAreaHeight) { height = plotAreaHeight - y1; } return rect .attr('class', 'quadtree-node') .attr('x', x1) .attr('y', y1) .attr('width', width) .attr('height', height) .style('fill', 'none') .style('stroke', '#ccc');}function toggleQuadtreeDebug() { // remove if there if (g.select('.quadtree').size()) { g.select('.quadtree').remove(); g.select('.quadtree-brushed').remove(); d3.select('#reveal-quadtree').text('Reveal the Quadtree'); // otherwise, add in } else { d3.select('#reveal-quadtree').text('Hide the Quadtree'); var gQuadtree = g.insert('g', '.circles') .attr('class', 'quadtree'); // add in a group for the brushed parts g.insert('g', '.circles').attr('class', 'quadtree-brushed'); // traverse the quadtree, drawing a rectangle for each node quadtree.visit(function (node, x1, y1, x2, y2) { quadtreeRect(gQuadtree.append('rect'), x1, y1, x2, y2); }); }}// animation ID for making sure we keep our animations consistent when// animating in the brushed points in the quadtreevar animationId;// function that animates the quadtree nodes that are searched// this is basically a copy of the code from above since it isn't// intended to be used outside of the demo, otherwise I could have// integrated it there.function showBrushedQuadtreeNodes() { // if no quadtree, ignore if (g.select('.quadtree').empty()) { return; } var ref = d3.event; var selection = ref.selection; // if we have no selection, remove the quadtree highlighting if (!selection) { g.select('.quadtree-brushed').selectAll('*').remove(); return; } // begin an array to collect the brushed nodes var brushedNodes = []; // traverse the quad tree, skipping branches where we do not overlap // with the brushed selection box. Set a skip flag to true to skip the // root node. var skip = true; quadtree.visit(function (node, x1, y1, x2, y2) { // check that quadtree node intersects var overlaps = rectIntersects(selection, [[x1, y1], [x2, y2]]); // skip if it doesn't overlap the brush if (!overlaps) { return true; } // skip the root node if (!skip) { brushedNodes.push({ x1: x1, y1: y1, x2: x2, y2: y2, node: node }); } skip = false; // return false so that we traverse into branch (only useful for non-leaf nodes) return false; }); // update the highlighted brushed nodes var rects = g.select('.quadtree-brushed').selectAll('rect').data(brushedNodes); var entering = rects.enter().append('rect'); var brushedDataPoints = []; // update animation ID but keep a local copy for the closure checking. animationId = Math.random(); var localAnimationId = animationId; highlightBrushed(brushedDataPoints); // add in rects, update their positions and animate them entering.merge(rects) .each(function updateQuadtreeBrushedRects(d) { quadtreeRect(d3.select(this), d.x1, d.y1, d.x2, d.y2) .style('fill', '#bbb') .style('fill-opacity', 0) .style('stroke', '#aaa') .style('stroke-opacity', 0); }) .transition() .delay(function (d, i) { return i * 30; }) .style('fill-opacity', 0.2) .style('stroke-opacity', 0.5) .on('start', function (d) { // only run if we are still active if (animationId !== localAnimationId) { return; } // check if we should add this to the brushed nodes if (!d.node.length) { var datum = d.node.data; var dx = xScale(datum.x); var dy = yScale(datum.y); if (rectContains(selection, [dx, dy])) { brushedDataPoints.push(datum); highlightBrushed(brushedDataPoints); } } }); rects.exit().remove();}// add namespaced handlers to the brush for the quadtree animationsbrush.on('brush.quadtree end.quadtree', showBrushedQuadtreeNodes);// add a click listener to the reveal buttond3.select('#reveal-quadtree').on('click', function () { return toggleQuadtreeDebug(); });// ----------------------------------------------------// Bonus! Add in voronoi on top of the brushing// ----------------------------------------------------// Code taken from https://github.com/pbeshai/pbeshai.github.io/blob/master/vis/scatterplot-voronoi/scatterplot-voronoi.js// add in interaction via voronoi// initialize text output for highlighted pointsvar highlightOutput = container.append('div') .attr('class', 'highlight-output') .style('padding-left', ((padding.left) + "px")) .style('min-height', '100px');// create a voronoi diagram based on the data and the scalesvar voronoiDiagram = d3.voronoi() .x(function (d) { return xScale(d.x); }) .y(function (d) { return yScale(d.y); }) .size([plotAreaWidth, plotAreaHeight])(data);// limit how far away the mouse can be from finding a voronoi sitevar voronoiRadius = plotAreaWidth / 10;// add a circle for indicating the highlighted point. we insert it// before the brush so the brush stays on top of everythingg.insert('circle', '.brush') .attr('class', 'highlight-circle') .attr('r', pointRadius + 2) // slightly larger than our points .style('fill', 'none') .style('display', 'none');// callback to highlight a pointfunction highlight(d) { // no point to highlight - hide the circle and clear the text if (!d) { d3.select('.highlight-circle').style('display', 'none'); highlightOutput.text(''); // otherwise, show the highlight circle at the correct position } else { d3.select('.highlight-circle') .style('display', '') .style('stroke', colorScale(d.y)) .attr('cx', xScale(d.x)) .attr('cy', yScale(d.y)); // format the highlighted data point for inspection highlightOutput.html(JSON.stringify(d) .replace(/([{}])/g, '') .replace(/"(.+?)":/g, '<strong style="width: 40px; display: inline-block">$1:</strong> ') .replace(/,/g, '<br>')); }}// callback for when the mouse moves across the overlayfunction mouseMoveHandler() { // get the current mouse position var ref = d3.mouse(this); var mx = ref[0]; var my = ref[1]; // use the new diagram.find() function to find the voronoi site closest to // the mouse, limited by max distance defined by voronoiRadius var site = voronoiDiagram.find(mx, my, voronoiRadius); // highlight the point if we found one, otherwise hide the highlight circle highlight(site && site.data);}// now *here* is where we attach the voronoi listener to the already existing// brush overlay, allowing us to get the benefit of brushing and voronoi// hover behavior at the same time.gBrush .on('mousemove.voronoi', mouseMoveHandler) .on('mouseleave.voronoi', function () { // hide the highlight circle when the mouse leaves the chart highlight(null); }); </script></body> https://d3js.org/d3.v4.min.js