This example demonstrates how to take the size of objects into account when selecting objects efficiently with a quadtree. Selected objects are shown in red, visited but not selected objects are shown in yellow. The efficiency depends on the biggest width and biggest height among all object. It is assumed that all objects are rectangle-shaped.
Example series:
Based on Mike Bostock's quadtree example.
| <!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> | |
| var width = 960, | |
| height = 500, | |
| min_w = 5, max_w = 50, // half of maximum element width | |
| min_h = 5, max_h = 35; // half of maximum element height | |
| var data = d3.range(1000).map(function() { | |
| return [Math.random() * width, Math.random() * width | |
| ,min_w+Math.random()*(max_w-min_w) | |
| ,min_h+Math.random() * (max_h-min_h)]; | |
| }); | |
| var max_w = d3.max(data, function (d) { return d[2] }) | |
| ,max_h = d3.max(data, function (d) { return d[3] }); | |
| var quadtree = d3.geom.quadtree() | |
| .extent([[-1, -1], [width + 1, height + 1]]) | |
| (data); | |
| var brush = d3.svg.brush() | |
| .x(d3.scale.identity().domain([0, width])) | |
| .y(d3.scale.identity().domain([0, height])) | |
| .extent([[100, 100], [200, 200]]) | |
| .on("brush", brushed); | |
| 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.x; }) | |
| .attr("y", function(d) { return d.y; }) | |
| .attr("width", function(d) { return d.width; }) | |
| .attr("height", function(d) { return d.height; }); | |
| var point = svg.selectAll(".point") | |
| .data(data) | |
| .enter().append("rect") | |
| .attr("class", "point") | |
| .attr("x", function (d) { return d[0]-d[2]; }) | |
| .attr("y", function (d) { return d[1]-d[3]; }) | |
| .attr("width", function (d) { return d[2]*2; }) | |
| .attr("height", function (d) { return d[3]*2; }); | |
| svg.append("g") | |
| .attr("class", "brush") | |
| .call(brush); | |
| brushed(); | |
| function brushed() { | |
| var extent = brush.extent(); | |
| point.each(function(d) { d.scanned = d.selected = false; }); | |
| search(quadtree, extent[0][0], extent[0][1], extent[1][0], extent[1][1]); | |
| point.classed("scanned", function(d) { return d.scanned; }); | |
| point.classed("selected", function(d) { return d.selected; }); | |
| } | |
| // Collapse the quadtree into an array of rectangles. | |
| function nodes(quadtree) { | |
| var nodes = []; | |
| quadtree.visit(function(node, x1, y1, x2, y2) { | |
| nodes.push({x: x1, y: y1, width: x2 - x1, height: y2 - y1}); | |
| }); | |
| return nodes; | |
| } | |
| // Find the nodes within the specified rectangle. | |
| function search(quadtree, x0, y0, x3, y3) { | |
| quadtree.visit(function(node, x1, y1, x2, y2) { | |
| var p = node.point; | |
| if (p) { | |
| p.scanned = true; | |
| p.selected = (p[0]+p[2] >= x0) && (p[0]-p[2] < x3) && (p[1]+p[3] >= y0) && (p[1]-p[3] < y3); | |
| } | |
| return x1-max_w >= x3 || y1-max_h >= y3 || x2+max_w < x0 || y2+max_h < y0; | |
| }); | |
| } | |
| </script> |