|
1 <!DOCTYPE html> |
|
2 <html> |
|
3 <head> |
|
4 <title>Quadtree</title> |
|
5 <script type="text/javascript" src="../../d3.js"></script> |
|
6 <script type="text/javascript" src="../../d3.geom.js"></script> |
|
7 <style type="text/css"> |
|
8 |
|
9 svg { |
|
10 padding: 2px; |
|
11 } |
|
12 |
|
13 circle { |
|
14 fill: lightsteelblue; |
|
15 stroke: steelblue; |
|
16 stroke-width: 1.5px; |
|
17 } |
|
18 |
|
19 rect { |
|
20 fill: none; |
|
21 stroke: #000; |
|
22 stroke-opacity: .3; |
|
23 } |
|
24 |
|
25 </style> |
|
26 </head> |
|
27 <body> |
|
28 <script type="text/javascript"> |
|
29 |
|
30 var w = 500; |
|
31 |
|
32 // Generate random points. |
|
33 var data = d3.range(500).map(function() { |
|
34 return { |
|
35 x: Math.random() * w, |
|
36 y: Math.random() * w |
|
37 }; |
|
38 }); |
|
39 |
|
40 // Generate a quadtree of the specified data. |
|
41 var quadtree = d3.geom.quadtree(data, 0, w); |
|
42 |
|
43 var vis = d3.select("body").append("svg:svg") |
|
44 .attr("width", w) |
|
45 .attr("height", w) |
|
46 .style("pointer-events", "all"); |
|
47 |
|
48 vis.selectAll("rect") |
|
49 .data(nodes(quadtree)) |
|
50 .enter().append("svg:rect") |
|
51 .attr("x", function(d) { return d.x; }) |
|
52 .attr("y", function(d) { return d.y; }) |
|
53 .attr("width", function(d) { return d.width; }) |
|
54 .attr("height", function(d) { return d.height; }); |
|
55 |
|
56 vis.selectAll("circle") |
|
57 .data(data) |
|
58 .enter().append("svg:circle") |
|
59 .attr("cx", function(d) { return d.x; }) |
|
60 .attr("cy", function(d) { return d.y; }) |
|
61 .attr("r", 4.5); |
|
62 |
|
63 // Highlight selected nodes using the quadtree. |
|
64 vis.on("mousedown", function() { |
|
65 var m0 = d3.svg.mouse(this); |
|
66 |
|
67 var rect = d3.select(this).append("svg:rect") |
|
68 .style("fill", "#999") |
|
69 .style("fill-opacity", .5); |
|
70 |
|
71 d3.select(window).on("mousemove", function() { |
|
72 var m1 = d3.svg.mouse(rect.node()), |
|
73 x0 = Math.min(w, m0[0], m1[0]), |
|
74 y0 = Math.min(w, m0[1], m1[1]), |
|
75 x1 = Math.max(0, m0[0], m1[0]), |
|
76 y1 = Math.max(0, m0[1], m1[1]); |
|
77 |
|
78 data.forEach(function(d) { d.z = 0; }) |
|
79 find(quadtree, x0, y0, x1, y1).forEach(function(d) { d.z = 1; }); |
|
80 vis.selectAll("circle").style("fill", function(d) { return d.z ? "red" : null; }); |
|
81 rect.attr("x", x0).attr("y", y0).attr("width", x1 - x0).attr("height", y1 - y0); |
|
82 }); |
|
83 |
|
84 d3.select(window).on("mouseup", function() { |
|
85 rect.remove(); |
|
86 d3.select(window).on("mousemove", null).on("mouseup", null); |
|
87 }); |
|
88 |
|
89 d3.event.preventDefault(); |
|
90 }); |
|
91 |
|
92 // Collapse the quadtree into an array of rectangles. |
|
93 function nodes(quadtree) { |
|
94 var nodes = []; |
|
95 quadtree.visit(function(node, x1, y1, x2, y2) { |
|
96 nodes.push({x: x1, y: y1, width: x2 - x1, height: y2 - y1}); |
|
97 }); |
|
98 return nodes; |
|
99 } |
|
100 |
|
101 // Find the nodes within the specified rectangle. |
|
102 function find(quadtree, x0, y0, x3, y3) { |
|
103 var points = []; |
|
104 quadtree.visit(function(node, x1, y1, x2, y2) { |
|
105 var p = node.point; |
|
106 if (p && (p.x >= x0) && (p.x < x3) && (p.y >= y0) && (p.y < y3)) points.push(p); |
|
107 return x1 >= x3 || y1 >= y3 || x2 < x0 || y2 < y0; |
|
108 }); |
|
109 return points; |
|
110 } |
|
111 |
|
112 </script> |
|
113 </body> |
|
114 </html> |