Rendering points using D3 quadtree and data joins. A quadtree can significantly reduce the number of data point comparisons. The brush extent searches the quadtree for nearby points. Scanned points are marked orange. Selected points are marked red.
Press spacebar to toggle all points.
Press c to toggle the quadtree cells.
| <!DOCTYPE html> | |
| <html> | |
| <head> | |
| <meta charset='utf-8' /> | |
| <title>Quadtree XY</title> | |
| <script src='https://cdnjs.cloudflare.com/ajax/libs/d3/4.10.0/d3.min.js'></script> | |
| </head> | |
| <style> | |
| body { | |
| margin: 0; | |
| overflow: hidden; | |
| } | |
| #stats { | |
| position: absolute; | |
| top: 10px; | |
| left: 10px; | |
| pointer-events: none; | |
| text-shadow: #fc0 1px 0 10px; | |
| } | |
| .hidden { | |
| display: none; | |
| } | |
| .point { | |
| fill: blue; | |
| } | |
| .scanned.point { | |
| fill: orange; | |
| stroke: orange; | |
| stroke-width: 4px; | |
| } | |
| .selected.point { | |
| fill: red; | |
| stroke: red; | |
| stroke-width: 5px; | |
| } | |
| .node { | |
| fill: none; | |
| stroke: #ccc; | |
| stroke-width: 1px; | |
| } | |
| </style> | |
| <body> | |
| <div id="container"></div> | |
| <div id="stats"></div> | |
| <script> | |
| var width = window.innerWidth, | |
| height = window.innerHeight; | |
| var svg = d3.select('#container').append('svg') | |
| .attr('width', width) | |
| .attr('height', height); | |
| var g = svg.append('g'); | |
| var random = Math.random, | |
| data = d3.range(1000).map(d => [random() * width, random() * height]); | |
| var quadtree = d3.quadtree(data); | |
| var cellHide = false, | |
| spaceKey = false; | |
| g.selectAll('.node') | |
| .data(nodes(quadtree)) | |
| .enter().append('rect') | |
| .attr('class', 'node') | |
| .attr('x', d => d.x0) | |
| .attr('y', d => d.y0) | |
| .attr('width', d => d.x1 - d.x0) | |
| .attr('height', d => d.y1 - d.y0) | |
| .classed('hidden', cellHide); | |
| var brush = d3.brush() | |
| .on('brush', brushed); | |
| svg.append('g') | |
| .attr('class', 'brush') | |
| .call(brush) | |
| .call(brush.move, [[100, 100], [200, 200]]); | |
| document.addEventListener("keydown", keydown, false); | |
| function brushed() { | |
| if (spaceKey) return; | |
| let extent = d3.event.selection; | |
| let subset = search(quadtree, extent[0][0], extent[0][1], extent[1][0], extent[1][1]); | |
| let point = g.selectAll('.point') | |
| .data(subset, d => d); | |
| point.enter().append('circle') | |
| .attr('cx', (d => d[0])) | |
| .attr('cy', (d => d[1])) | |
| .attr('r', 3) | |
| .attr('class', 'point') | |
| .classed('scanned', d => d.scanned) | |
| .classed('selected', d => d.selected); | |
| point.classed('scanned', d => d.scanned); | |
| point.classed('selected', d => d.selected); | |
| point.exit().remove(); | |
| showStats(); | |
| } | |
| function search(quadtree, x0, y0, x3, y3) { | |
| let pts = []; | |
| quadtree.visit(function(node, x1, y1, x2, y2) { | |
| if (!node.length) { // is leaf | |
| do { | |
| let d = node.data; | |
| d.scanned = true; | |
| d.selected = (d[0] >= x0) && (d[0] < x3) && (d[1] >= y0) && (d[1] < y3); | |
| if (d.scanned) pts.push(d); | |
| } while (node = node.next); | |
| } | |
| return x1 >= x3 || y1 >= y3 || x2 < x0 || y2 < y0; | |
| }); | |
| return pts; | |
| } | |
| function showStats() { | |
| document.getElementById("stats").innerHTML = "Total data points: " + quadtree.size() + "<br>" | |
| + "Scanned points: " + d3.selectAll('.scanned').size() + "<br>" | |
| + "Selected points: " + d3.selectAll('.selected').size(); | |
| } | |
| function keydown(e) { | |
| if (e.keyCode === 32) { // spacebar key | |
| spaceKey = !spaceKey; | |
| let point = g.selectAll('.point') | |
| .data(data) | |
| .enter().append('circle') | |
| .attr('cx', (d => d[0])) | |
| .attr('cy', (d => d[1])) | |
| .attr('r', 3) | |
| .attr('class', 'point'); | |
| } | |
| if (e.keyCode === 67) { // c key | |
| cellHide = !cellHide; | |
| g.selectAll('.node').classed('hidden', cellHide); | |
| } | |
| showStats(); | |
| } | |
| function nodes(quadtree) { | |
| let nodes = []; | |
| quadtree.visit(function(node, x0, y0, x1, y1) { | |
| node.x0 = x0, | |
| node.y0 = y0, | |
| node.x1 = x1, | |
| node.y1 = y1; | |
| nodes.push(node); | |
| }); | |
| return nodes; | |
| } | |
| </script> | |
| </body> | |
| </html> |
