Quadtree 3

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:

Quadtree 1
Quadtree 2
Quadtree 3

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="https://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; });

svg.append("g")
    .attr("class", "brush")
    .call(brush);

brushed();

// 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>

Modified http://d3js.org/d3.v3.min.js to a secure url

https://d3js.org/d3.v3.min.js