|
<!DOCTYPE html> |
|
<meta charset="utf-8"> |
|
<title>Quadtree 2</title> |
|
<style> |
|
.point { |
|
fill: #999; |
|
stroke: #fff; |
|
pointer-events: none; |
|
} |
|
|
|
.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 = 1800, |
|
height =1800; |
|
|
|
var data = d3.range(100000).map(function (i) { |
|
return { |
|
id : i, |
|
coord: [Math.random() * width, Math.random() * width] |
|
} |
|
}); |
|
|
|
var quadtree = d3.geom.quadtree(data.map( |
|
function (v, i) { |
|
return { |
|
x: v.coord[0], |
|
y: v.coord[1], |
|
all: v |
|
}; |
|
} |
|
) |
|
); |
|
|
|
|
|
|
|
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.append("g") |
|
.attr("class", "brush") |
|
.call(brush); |
|
|
|
brushed(); |
|
|
|
function brushed() { |
|
var extent = brush.extent(); |
|
var subset = search(quadtree, extent[0][0], extent[0][1], extent[1][0], extent[1][1]); |
|
var points = svg.selectAll(".point") |
|
.data(subset, function (d) { return d.id; }); |
|
|
|
points.enter().append("circle") |
|
.attr("class", "point") |
|
.attr("cx", function (d) { return d.coord[0]; }) |
|
.attr("cy", function (d) { return d.coord[1]; }) |
|
.attr("r", 4); |
|
|
|
points.exit().remove(); |
|
|
|
|
|
|
|
} |
|
|
|
|
|
|
|
// Find the nodes within the specified rectangle. |
|
function search(quadtree, x0, y0, x3, y3) { |
|
var pts = []; |
|
quadtree.visit(function (node, x1, y1, x2, y2) { |
|
var p = node.point; |
|
if ((p) && (p.x >= x0) && (p.x < x3) && (p.y >= y0) && (p.y < y3)) { |
|
pts.push(node.point.all); |
|
} |
|
return x1 >= x3 || y1 >= y3 || x2 < x0 || y2 < y0; |
|
}); |
|
|
|
return pts; |
|
|
|
} |
|
|
|
</script> |