Changes in this fork:
point.each(function(d) { d.scanned = d.selected = false; }); This version only touches the nodes scanned by the quadtree (and the previous selection), resulting in faster responseSee original here
| <!DOCTYPE html> | |
| <meta charset="utf-8"> | |
| <title>Quadtree</title> | |
| <style> | |
| .point { | |
| fill: #999; | |
| stroke: #fff; | |
| } | |
| .point.scanned { | |
| fill: orange; | |
| fill-opacity: 1; | |
| stroke: brown; | |
| } | |
| .point.selected { | |
| fill: red; | |
| fill-opacity: 1; | |
| } | |
| .node { | |
| fill: none; | |
| stroke: #ccc; | |
| shape-rendering: crispEdges; | |
| } | |
| .brush .extent { | |
| stroke: #fff; | |
| fill-opacity: .125; | |
| shape-rendering: crispEdges; | |
| } | |
| </style> | |
| <body> | |
| <script src="http://d3js.org/d3.v3.min.js"></script> | |
| <script src="quadtree.js"></script> | |
| <script> | |
| var width = 960, | |
| height = 500, | |
| scanned=d3.select(); | |
| var data = d3.range(5000).map(function() { | |
| return {x: Math.random() * width, y: Math.random() * width}; | |
| }); | |
| var quadtree = d3.geom.quadtree(data, -1, -1, width + 1, height + 1); | |
| var brush = d3.svg.brush() | |
| .x(d3.scale.identity().domain([0, width])) | |
| .y(d3.scale.identity().domain([0, height])) | |
| .on("brush", brushed) | |
| .extent([[100, 100], [200, 200]]); | |
| var svg = d3.select("body").append("svg") | |
| .attr("width", width) | |
| .attr("height", height); | |
| svg.selectAll(".node") | |
| .data(nodes(quadtree)) | |
| .enter().append("rect") | |
| .attr("class", "node") | |
| .attr("x", function(d) { return d.x1; }) | |
| .attr("y", function(d) { return d.y1; }) | |
| .attr("width", function(d) { return d.x2-d.x1; }) | |
| .attr("height", function(d) { return d.y2-d.y1; }); | |
| svg.selectAll(".point") | |
| .data(data) | |
| .enter().append("circle") | |
| .attr("class", "point") | |
| .attr("cx", function(d) { return d.x; }) | |
| .attr("cy", function(d) { return d.y; }) | |
| .attr("r", 4) | |
| .each(function(d) { | |
| d.elem = this; | |
| }); | |
| svg.append("g") | |
| .attr("class", "brush") | |
| .call(brush); | |
| brushed(); | |
| function brushed() { | |
| scanned.attr("class","point"); | |
| var extent = brush.extent(); | |
| scanned = search(quadtree, extent[0][0], extent[0][1], extent[1][0], extent[1][1]) | |
| .attr("class",function(d) { | |
| return "point " + (d.selected ? "selected" : "scanned"); | |
| }); | |
| } | |
| // Collapse the quadtree into an array of rectangles. | |
| function nodes(quadtree) { | |
| var nodes = []; | |
| quadtree.visit(function(node) { | |
| nodes.push(node); | |
| }); | |
| return nodes; | |
| } | |
| // Find the nodes within the specified rectangle. | |
| function search(quadtree, x1, y1, x2, y2) { | |
| var res = []; | |
| quadtree.visit(function(n) { | |
| var p = n.point; | |
| if (p) { | |
| p.selected = ((p.x >= x1) && (p.x < x2) && (p.y >= y1) && (p.y < y2)); | |
| res.push(p.elem); | |
| } | |
| return n.x1 >= x2 || n.y1 >= y2 || n.x2 < x1 || n.y2 < y1; | |
| }); | |
| return d3.selectAll(res); | |
| } | |
| </script> |
| d3.geom.quadtree = function(points, x1, y1, x2, y2) { | |
| var p, | |
| i = -1, | |
| n = points.length; | |
| // Allow bounds to be specified explicitly. | |
| if (arguments.length < 5) { | |
| if (arguments.length === 3) { | |
| y2 = y1; | |
| x2 = x1; | |
| y1 = x1 = 0; | |
| } else { | |
| x1 = y1 = Infinity; | |
| x2 = y2 = -Infinity; | |
| // Compute bounds. | |
| while (++i < n) { | |
| p = points[i]; | |
| if (p.x < x1) x1 = p.x; | |
| if (p.y < y1) y1 = p.y; | |
| if (p.x > x2) x2 = p.x; | |
| if (p.y > y2) y2 = p.y; | |
| } | |
| } | |
| } | |
| // Squarify the bounds. | |
| var dx = x2 - x1, | |
| dy = y2 - y1; | |
| if (dx > dy) y2 = y1 + dx; | |
| else x2 = x1 + dy; | |
| // Recursively inserts the specified point p at the node n or one of its | |
| // descendants. The bounds are defined by [x1, x2] and [y1, y2]. | |
| function insert(n, p) { | |
| if (isNaN(p.x) || isNaN(p.y)) return; // ignore invalid points | |
| n.count +=1; | |
| if (n.leaf) { | |
| var v = n.point; | |
| if (v) { | |
| // If the point at this leaf node is at the same position as the new | |
| // point we are adding, we leave the point associated with the | |
| // internal node while adding the new point to a child node. This | |
| // avoids infinite recursion. | |
| if ((Math.abs(v.x - p.x) + Math.abs(v.y - p.y)) < .01) { | |
| insertChild(n, p); | |
| } else { | |
| n.point = null; | |
| insertChild(n, v); | |
| insertChild(n, p); | |
| } | |
| } else { | |
| n.point = p; | |
| } | |
| } else { | |
| insertChild(n, p); | |
| } | |
| } | |
| // Recursively inserts the specified point p into a descendant of node n. The | |
| // bounds are defined by [x1, x2] and [y1, y2]. | |
| function insertChild(n, p) { | |
| // Compute the split point, and the quadrant in which to insert p. | |
| var sx = (n.x1 + n.x2) * .5, | |
| sy = (n.y1 + n.y2) * .5, | |
| right = p.x >= sx, | |
| bottom = p.y >= sy, | |
| i = (bottom << 1) + right, | |
| x1,y1,x2,y2; | |
| // Recursively insert into the child node. | |
| n.leaf = false; | |
| // Update the bounds as we recurse. | |
| if (right) x1 = sx, x2 = n.x2; else x1 = n.x1, x2 = sx; | |
| if (bottom) y1 = sy, y2 = n.y2; else y1 = n.y1, y2 = sy; | |
| n = n.nodes[i] || (n.nodes[i] = d3_geom_quadtreeNode(n,x1,y1,x2,y2)); | |
| insert(n, p, x1, y1, x2, y2); | |
| } | |
| // Create the root node. | |
| var root = d3_geom_quadtreeNode(null,x1,y1,x2,y2); | |
| root.add = function(p) { | |
| insert(root, p, x1, y1, x2, y2); | |
| }; | |
| root.visit = function(f) { | |
| d3_geom_quadtreeVisit(f, root); | |
| }; | |
| // Insert all points. | |
| points.forEach(root.add); | |
| return root; | |
| }; | |
| function d3_geom_quadtreeNode(parent,x1,y1,x2,y2) { | |
| return { | |
| x1 : x1, | |
| x2 : x2, | |
| y1 : y1, | |
| y2 : y2, | |
| leaf: true, | |
| parent : parent, | |
| count : 0, | |
| nodes: [], | |
| point: null | |
| }; | |
| } | |
| function d3_geom_quadtreeVisit(f, node) { | |
| if (!f(node, node.x1, node.y1, node.x2, node.y2)) { | |
| node.nodes.forEach(function(child) { | |
| d3_geom_quadtreeVisit(f, child); | |
| }); | |
| } | |
| } |
